CmSc 250 Intro to Algorithms
Elementary Graph Algorithms
Given a graph with N vertices and a selected vertex A:
for(i = 1; there are unvisited vertices ; i++)
(i is the length of the shortest path between A and currently processed vertices)
As we saw, the algorithm for single source shortest path uses breadth-first search
For a graph with N vertices the shortest path between two vertices can be
1. Store source vertex S in a queue and mark as processed
2. While queue is not empty
Read vertex v from the queue
Append in the queue
Record the parent of w to be v
(parent is necessary only if we need the shortest path tree)
We can use a distance table to mark vertices as processed by storing the distance to the source vertex.
A: B, C, E
Let's select A as the starting node.
1. After reading A from the queue and processing its neighbors:
Queue: B, C, E
2. Read B. Its neighbors are A, C and E. All are processed.
Queue: C, E
3. Read C. Its neighbors are A, B and D. A and B are processed. D is not. After processing D we have;
Queue: E, D
4. Read E. Its neighbors are processed
5. Read D. Its neighbors are processed
The queue is empty and the algorithm ends.
Question: Is there a more efficient way to organize the ‘while’ loop above?
Consider the distance table:
The table defines the shortest path tree, rooted at A.
Consider the algorithm’s basic loop:
While queue is not empty:
2. For all neighbors w:
Append w in the queue
In step 1 we read a node from the queue. The question to be answered is: how many nodes are stored in the queue? The answer is: each node is stored only once – if it is not processed. Thus the reading step will be performed O(V) times, where V is the number of the nodes in the graph.
In step 2 we examine all neighbors, i.e. we examine all edges of the currently read node. Since the graph is not oriented, we will examine 2*E edges, where E is the number of the edges in the graph.
Hence the complexity of BFS is O(V + 2*E)
Attention: a typical error in determining the complexity is to multiply the number of the nodes by the number of the edges. Why we should not multiply the number of the edges by the number of the nodes?
For a selected vertex A let B1, B2, .. Bm be adjacent vertices. For all adjacent vertices, if Bk is not visited, visit Bk and all vertices reachable from Bk before proceeding with Bk+1.
for each neighbor w of s
DFS builds a DFS tree T which shows how the vertices are visited.
The non-recursive implementation uses a stack
BFS and DFS are very closely related to each other. The difference is that BFS uses a queue while DFS uses a stack. Queues can be described as lists where we write at the end and read from the beginning. Stacks can be described as lists where we write at the end and read from the end. Thus we can describe BFS and DFS in the following way:
bfs(G) list L = empty tree T = empty choose a starting vertex x visit(x) while(L nonempty) remove edge (v,w) from beginning of L if w not visited add (v,w) to T visit(w) dfs(G) list L = empty tree T = empty choose a starting vertex x visit(x) while(L nonempty) remove edge (v,w) from end of L if w not visited add (v,w) to T visit(w) visit(vertex v) mark v as visited for each edge (v,w) add edge (v,w) to end of L
Back to Contents page
Created by Lydia Sinapova