Data Structures with Generic Types in Python/

...

/

Graph Traversal

Graph Traversal

Learn about BFS and DFS searching algorithms.

We'll cover the following...

In this lesson we present two algorithms for exploring a graph, starting at one of its vertices, i, and finding all vertices that are reachable from i. Both of these algorithms are best suited to graphs represented using an adjacency list representation. Therefore, when analyzing these algorithms we will assume that the underlying representation is an AdjacencyLists.

Breadth-first-search

The breadth-first-search algorithm starts at a vertex i and visits, first the neighbors of i, then the neighbors of the neighbors of i, then the neighbors of the neighbors of the neighbors of i, and so on. This algorithm is a generalization of the breadth-first traversal algorithm for binary trees, and is very similar; it uses a queue, q, that initially contains only i. It then repeatedly extracts an element from q and adds its neighbours to q, provided that these neighbours have never been in q before. The only major difference between the breadth-first-search algorithm for graphs and the one for trees is that the algorithm for graphs has to ensure that it does not add the same vertex to q more than once. It does this by using an auxiliary boolean array, seen, that tracks which vertices have already been discovered.

Press + to interact
def bfs(g, r):

    seen = new_boolean_array(n)

    q = SLList()

    q.add(r)

    seen[r] = True

    while q.size() > 0:

        i = q.remove()

        for j in g.out_edges(i):

            if seen[j] is False:

                q.add(j)

                seen[j] = True

Visual demonstration of breadth-first-search

An example of running bfs(g, 0) on the graph is shown in below illustration.

An example of bread-first-search starting at node 00. Nodes are labelled with the order in which they are added to q. Edges that result in nodes being added to q are drawn in black, other edges are drawn in gray.

Press + to interact
Breadth-first search
Breadth-first search

Analyzing the running time of the bfs(g, i) routine is fairly straightforward. The use of the seen array ensures that no vertex is added to q more than once. Adding (and later removing) each vertex from q takes constant time per vertex for a total of O(n)O(n) time. Since each vertex is processed by the inner loop at most once, each adjacency list is processed at most once, so each edge of GG is processed at most once. ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy