Breadth first search problem 154

Back to General discussions forum

Franz_Nilsson     2016-06-06 07:43:10

Hallo!

Im having a bit trouble with problem 145. My program gives the correct answer when I try the example, but when I submit for the larger data set I get a completly different answer!

My output:

-1 0 0 0 0 0 8 8 8 8 8 12 12 12 12 18 18 18 18 28 35 35 35 20 27 27 31 31 31 32 41 41 41 41 6 16 16 16 29 9 17 26 39 39 48 3 24 37 15

Answer:

-1 48 37 35 35 31 12 41 0 18 6 3 0 29 17 41 12 18 0 26 8 15 20 41 35 16 18 8 0 12 39 8 8 27 12 0 9 31 24 18 31 8 16 16 39 27 41 32 28

As you can see, they are completly different! But I dont understand what I've done wrong. The given answer seems strange to, since the search should start at node 0 but seems to start at node 48?

My code is as follows:

class Node(object):

def __init__(self,idnr):

    self.ID=idnr
    self.next=[]
    self.state=False      

def add(self,neighboor):

    i=0

    while i<len(self.next) and int(self.next[i].ID)<int(neighboor.ID):
        i+=1
    if i==len(self.next):
        self.next.append(neighboor)
    else:
        self.next=self.next[0:i]+[neighboor]+self.next[i:]

def seen(self):

    self.state=True

def __str__(self):

    ret='Node '+str(self.ID)+'---> '
    ret+=' '.join(str(i.ID) for i in self.next)
    return ret

if name=='main':

#N: Amount of nodes
#M: Amount of edges

N,M=raw_input().split()

nodes=dict()

for i in range(0,int(M)):

    #Get all the edges

    n1 , n2 = raw_input().split()

    if n1 not in nodes.keys():

        nodes[n1]=Node(n1)

    if n2 not in nodes.keys():

        nodes[n2]=Node(n2)

    nodes[n1].add(nodes[n2])
    nodes[n2].add(nodes[n1])

q=[]    #Create a FIFO que:

#Step 1:

nodes['0'].seen()

q.append(nodes['0'])

answer=['-1']   #Output for the script

while len(q)>0:

    #Step 2:

    curr=q.pop(0)

    for nxt in curr.next:

        #Step 3:

        if not nxt.state:

            #Step 4:

            nxt.seen()
            q.append(nxt)

            answer.append(curr.ID)

print ' '.join( i for i in answer )

Any help is appreciated!

Best regards // Franz. N

JamBoltheads     2016-06-13 21:13:33
User avatar

Hi Franz. I had a similar problem to you so I hope I can be helpful and explain how I resolved it. I think the issue comes with this bit of code :


if not nxt.state:

        #Step 4:

        nxt.seen()
        q.append(nxt)

answer.append(curr.ID)

The problem here is your adding the curr.id to the answer as you "see" the node which is what i did. What the question actually wants you is to for the answer id's to be in order of the node ids.

for example. the first number in the answer should be the ID of the node that lead to node 0 being seen. In this special case we use -1 the second number should be the ID of the node that lead to the node with ID of 1 being seen. so in terms of your answers: Node1 was first discovered when node 48 was the current. not when node 0 was the current which is what you put. In short youve ordered your answer in terms of when nodes are "seen" during the code NOT in order of the increasing NODE IDS. Hope i've been useful, if not ill try again. Good Luck!

Franz_Nilsson     2016-06-17 21:28:46

Hallo JamBoltheads!

Yes I understand your answer. I changed my code now by your description and it was right! I guess I didn't really understand the given instructions from the problem.

Thank you very much for your help and taking your time helping me! You're the best!

Best regards // Franz N

smwentum     2016-12-31 23:21:21

i did that too! i thought i was doing dfs or something

Please login and solve 5 problems to be able to post at forum