- #1
Vespero
- 28
- 0
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:
return traversed
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[v] = 0
while (queue != []):
print distance
return distance
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[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)
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.
Last edited: