Is this a breadth-first search algorithm?

1
votes

So, I have this graph and I want to use the breadth-first search algorithm to see if there is a path from a vertex to another.

Cool sketch of a graph

So, I implemented a function in python which returns true or false, depending on the existence of a path and it works. Well, it worked for the tests I made. What I want to know is if this is indeed a breath-first search algorithm. I haven't seen any BFS algorithm before and I only know its base idea. I heard that BFS is implemented recursively, though I implemented it iteratively and that's why I have doubts about it.So, here are both the function and the representation of my graph:

outb = {1: [2, 3],
  2: [4, 5],
  3: [5, 11, 12],
  4: [6, 7],
  5: [7],
  6: [9, 10],
  7: [8],
  11: [3],
  12: [15, 14, 13],
  13: [17],
  14: [17],
  15: [12, 5, 8, 16],
  17: [18]}

def BFS(v1, v2):
    parsed = []
    toParse = [v1]
    current = v1

    while len(toParse) > 0:

        while current in parsed:
            current = toParse.pop(0)

        if current not in outb:
            return False

        if v2 in outb[current]:
            return True

        toParse += outb[current]
        parsed.append(current)

    return False

And the last questions I have is: Is BFS, by its nature, finding the shortest path from a vertex to another? I read this thing on the internet and I want to be sure.

3
pythongraph-theorybreadth-first-search
Read the wikipedia page. It looks like your code implements the algorithm there, and it states that BFS finds the shortest path. - Barmar
Comparing your code to the pseudocode in the wikipedia, S == parsed, Q == toParse, current == current. - Barmar
Your code is a BFS, but it's also wrong, because current not in outb doesn't mean there is no path, and you try to do toParse.pop(0) without considering whether toParse actually has any elements. Also, lists are not an efficient choice for most of the data structures used. - user2357112 supports Monica
@user2357112 current not in outb is error checking to make sure you're not looking for a path from a node not in the graph. Also, the code DOES check whether toParse has any elements. The pop call happens in a while loop with that as a condition. - De Novo
@DanHall: There are nodes in the graph that aren't in outb, because someone made the choice to omit keys from outb if they don't have outgoing edges. If the search reaches such a node before it reaches the destination, the search will wrongly output False. - user2357112 supports Monica

3 Answers

1
votes

This is a breadth-first search. It follows a fairly typical structure with the search frontier treated as a queue (although lists are an inefficient choice for a queue), and it considers nodes in order of distance from the root, like a standard breadth-first search.

However, it's also wrong. The current not in outb termination condition causes it to wrongly output False for searches like BFS(1, 18), and the while current in parsed: current = toParse.pop(0) loop can exhaust toParse and throw an exception when it tries to pop from an empty list, demonstrated here with a slightly different graph. Also, your outb doesn't match the picture of the graph it's supposed to represent; it's missing a bunch of back edges, such as 6->4.

1
votes

This is a BFS algorithm, written to find whether a path exists, but it doesn't tell you what that path is, and doesn't account for the way your dictionary is structured to represent the graph.

Here's an example of a BFS for the above graph that can deal with the way your dictionary represents the graph. It returns the path when it finds one, and False when a path doesn't exist. If you just want it to return True when it finds a path, edit line 19 to return True

def BFS2(graph, v1, v2):
    '''
    graph: a dictionary representing an unweighted graph
    v1: a key in graph, representing the start node
    v2: a key and value in graph, representing the end node
    returns: a shortest path from v1 to v2, False if there is no path.
    '''
    if v1 not in graph:
        return False
    path_start = [v1]
    paths = [path_start]
    while len(paths):
        test_path = paths.pop(0)
        last_node = test_path[-1]

        for next_node in graph[last_node]:
            if next_node not in test_path:
                next_path = test_path + [next_node]
                if next_node == v2:
                    paths.append(next_path)
                    return next_path
                elif next_node in graph:
                    paths.append(next_path)
    return False