Breadth first search problem 154
Back to General discussions forum
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!
-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
-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:
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
#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
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)
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!
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
i did that too! i thought i was doing dfs or something