1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

BFS Shortest Distance of Graph Calculation in Python

  1. Nov 20, 2012 #1
    1. The problem statement, all variables and given/known data

    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.

    2. Relevant 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



    3. 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: Nov 20, 2012
  2. jcsd
  3. Nov 20, 2012 #2
    Never mind, I got it. I needed to declare traversed[v] = True so that it wouldn't examine the starting vertex. Problem solved.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: BFS Shortest Distance of Graph Calculation in Python
Loading...