CODEWITHSUNDEEP
pythongraph-theorybreadth-first-search
Xyntell
Xyntell

Reputation: 155

Is this a breadth-first search algorithm?

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.

Upvotes: 1

Views: 679

Answers (3)

De Novo
De Novo

Reputation: 7600

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

Upvotes: 1

user2357112
user2357112

Reputation: 280251

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.

Upvotes: 1

Harry B
Harry B

Reputation: 61

No, This isn't a BFS algorithm. This image will show you how a BFS algorithm would work

Upvotes: -1

Related Questions