Breadth first search problem 154

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

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