BFS Shortest Distance of Graph Calculation in Python

[Vespero]

Homework Statement

I have this problem essentially figured out. There's just one tiny problem that I can't seem to solve. I'm supposed to write a function bfs(G, v) which takes a graph G stored as a dictionary, and a starting vertex v. The function bfs performs a breadth-first-search while storing the distance from the starting vertex to each of the other vertices in a dictionary labeled distance{} and then prints and returns distance. On all of the test graphs I've run so far, the distance from the starting vertex v to all other vertices is correct. However, the value listed for the distance from vertex v to itself is being returned as 2, while it should be 0.

Homework Equations

My code so far is the following:

import sys

H = {1:[2], 2:[1,3], 3:[2,4], 4:[3,5,7],
5:[4,6], 6:[5,7], 7:[4,6]}

def build_traversed_dict(D):

"""Builds a dictionary that stores whether a vertex been reached."""
traversed = {}
for i in D:

traversed=False​

return traversed​

def bfs(G, v):

"""Performs a breadth first traversal of G, starting at v."""
traversed = build_traversed_dict(G)
queue = [v]
distance = {}
for i in G:

distance=-1​

distance[v] = 0
while (queue != []):

curr_v = queue.pop(0)
for i in G[curr_v]:

for i in G.get(curr_v):

if (traversed == False):

print str(i)
traversed = True
distance = distance[curr_v]+1
queue.append(i)​

​

print distance
return distance​

​

The Attempt at a Solution

In the sample graph provided, choosing a couple of vertices at random gave the following results:

bfs(H, 2):

1
3
2
4
5
7
6
{1: 1, 2: 2, 3: 1, 4: 2, 5: 3, 6: 4, 7: 3}

bfs(H, 5):

4
6
3
5
7
2
1
{1: 4, 2: 3, 3: 2, 4: 1, 5: 2, 6: 1, 7: 2}

As you can see, it's returning the value 2 for the distance from vertex v to itself, which should be 0. I can't figure out why this is happening despite looking through the code repeatedly.

 

[Vespero]

Never mind, I got it. I needed to declare traversed[v] = True so that it wouldn't examine the starting vertex. Problem solved.