Breadth-first search algorithm

Question

Like a previous problem I had earlier, I am trying to create a breadth-first search algorithm that takes a graph and outputs the vertex visit order. It takes an adjacency matrix (representing the graph) as its input and here is what I have so far.

import sys
import Queue

# Input has to be adjacency matrix or list
graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

# NEED TO FIX:
# - Final graphAL2v print is only displaying key values as 1, not iterating
# through graph and visiting each vertex

def main():
    count = 0
    graphAL2v = {}

    for key, value in graphAL2.items():
        graphAL2v[key] = 0

    print(graphAL2v)

    for key in graphAL2v: # each vertex v in V
        if graphAL2v[key] == 0: # is marked with 0
            bfs(key, count, graphAL2, graphAL2v)
    print(graphAL2v)

def bfs(v, count, graphal, graphv):
    count = count + 1
    print('Visiting', v)

    # Mark v with count and initialize queue with v
    graphv[v] = count
    visited = Queue.Queue()

    while not visited.empty(): #queue not empty:
        print('queue is not empty')
        for element in graphal[v]: # each vertex w in V adjacent to front vertex
            if element == 0:
                count = count + 1
                # mark w with count
                graphal[v] = count
                visited.put()
        visited.get()

if __name__ == '__main__':
    sys.exit(main())

The problem that I am running into is that my output

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
('Visiting', 0)
('Visiting', 1)
('Visiting', 2)
('Visiting', 3)
('Visiting', 4)
('Visiting', 5)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1}

displays the visit order as 1 for all vertices in the list when it should be displaying the visit order as a different number for each vertex as it traverses the "graph." I believe that this error is stemming from within the while loop of the bfs() function. Any suggestions for trying to fix the code so I can achieve the desired output? I'm also not that familiar with queues in Python so any help is appreciated.

Answer 1

There are lots of issues in your code -

1. First of all, you are never putting anything in the Queue that you create, so its always empty, you need to put the v inside the queue before the while loop , that is the starting point.

2. Secondly, in the for loop, you are checking element == 0 , which is wrong, you need to check if graphv[element] == 0 , that is whether the element has been already visited or not.

3. Thirdly, in the for loop, you need to set graphv[element] = count , that signifies that you vivisted element .

4. You are not putting anything inside the queue with - visited.put() , you need to pass the element to put inside the Queue as parameter.

5. When getting back the element from the Queue, you need to assign it back to v, otherwise v would never change, v signifies the current element being iterated.

Example code -

import sys
import Queue

# Input has to be adjacency matrix or list
graphAL2 = {0 : [1,2,3],
        1 : [0,3,4],
        2 : [0,4,5],
        3 : [0,1,5],
        4 : [1,2],
        5 : [2,3] }

# NEED TO FIX:
# - Final graphAL2v print is only displaying key values as 1, not iterating
# through graph and visiting each vertex

def main():
    count = 0
    graphAL2v = {}

    for key, value in graphAL2.items():
        graphAL2v[key] = 0

    print(graphAL2v)

    for key in graphAL2v: # each vertex v in V
        if graphAL2v[key] == 0: # is marked with 0
            bfs(key, count, graphAL2, graphAL2v)
    print(graphAL2v)

def bfs(v, count, graphal, graphv):
    count = count + 1
    print('Visiting', v)

    # Mark v with count and initialize queue with v
    graphv[v] = count
    visited = Queue.Queue()
    visited.put(v)
    while not visited.empty(): #queue not empty:
        print('queue is not empty')
        for element in graphal[v]: # each vertex w in V adjacent to front vertex
            if graphv[element] == 0:
                count = count + 1
                # mark w with count
                graphv[element] = count
                visited.put(element)
        v = visited.get()
    return count

if __name__ == '__main__':
    sys.exit(main())

---

Demo (after above changes) -

{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
Visiting 0
queue is not empty
queue is not empty
queue is not empty
queue is not empty
queue is not empty
queue is not empty
{0: 1, 1: 2, 2: 3, 3: 4, 4: 5, 5: 6}