Graphs – Traversal Algorithms

To search a graph G, we need to visit all vertices in a systematic order. We can choose any vertex as a starting point. Then we will systematically enumerate all vertices accessible from it. Because of a graph might contain cycles, we need some way for marking a vertex as having been visited. To do so we will have a boolean array visited with all elements initially set to false. We will set a correspondent element to true as soon as we visit a particular vertex. Also, we need to keep in mind that the graph might be disconnected. We need to have a container where we will store all unvisited adjacent vertices.

Here is an algorithm:

• remove a vertex from a container;
• print it;
• find all adjacent vertices;
• mark them as visited;
• enter them into a container;
• repeated as long as the container is not empty.

The algorithm runs in O(|V| + |E|) time.

There are two the most common traversals: depth-first order (DFT) and breadth-first order (BFT) traversals. On each step of DFT you go deeper and deeper into the graph. On each step of BFT you first visit all siblings and then their children. In case of BFT, we will use a queue and for DFT we will use a stack.

The stack-container version (depth-first order). Let us trace the algorithm using this graph:

We start with pushing 1 into the stack S = {1}. Set visited[1] = true. Then we pop 1 and push all unvisited adjacent vertices to S. We also mark those vertices as visited: visited[2] = true; visited[3] = true; visited[4] = true. The stack is S={4,3,2}, where the top is 4 and the bottom is 2. Observe that the order of pushing vertices to S is not important, however we chose an increasing order.

Since S is not empty, we pop 4 and then push all unvisited vertices to S, which gives S = {8, 7, 3, 2}. We also mark them as visited visited[7] = true; visited[8] = true.

We pop 8 and push all unvisited vertices (visited[6] = true) to S, which gives S = {6, 7, 3, 2}.

We pop 6 and push all unvisited vertices (visited[5] = true) to S, which gives S = {5, 7, 3, 2}.

We pop 5 and push all unvisited vertices (there are none) to S, which gives S = {7, 3, 2}.

We pop 7 and push all unvisited vertices (there are none) to S, which gives S = {3, 2}.

We pop 3 and push all unvisited vertices (there are none) to S, which gives S = {2}.

We pop 2 and push all unvisited vertices (there are none) to S, which gives S = {}.The order in which we traverse the graph is 1, 4, 8, 6, 5, 7, 3, 2

This is called a depth-first order traversal. Depth-first search (DFS ) in an undirected graph is analogous to wandering in a labyrinth with a string and a can of paint.

Remark. DFT in the above description will visit all vertices in the connected component of a graph.

Exercise. Perform a DFS on the following graph (starting at vertex 1):

 
 1-------2------3------4
 | \ | | /|
 | \ | | / |
 | \ | | / |
 5-------6 7 8
 | / / | \ |
 | / / | \ |
 | / / | \|
 9------10-----11 12
 | \  / | |
 | \ / | |
 | \ / | |
 13-----14 15-----16

Observe that the result of traversal gives a spanning tree:

1 2 3 4 7 10 9 5 6 13 14 11 15 16 12 8

See Graph.java for the iterative and recursive implementations of the DFT.

The queue-container version (breadth-first order). We replace the container by the queue. We will add unvisited vertices at the end and remove them from the front. We again start with Q = {1}, set visited[1] = true. Then we pop 1, and enqueue all unvisited adjacent vertices to Q. We also mark those vertices as visited: visited[2] = true; visited[3] = true; visited[4] = true. The queue is Q = {2, 3, 4}, where 2 is the front and 4 is the back. We enqueue vertices in an increasing order.

Since Q is not empty, we dequeue 2 and enqueue all unvisited vertices (visited[5] = true; visited[6] = true) to Q, which gives Q = {3, 4, 5, 6}.

We dequeue 3 and enqueue all unvisited vertices (there are none) to Q, which gives Q = {4, 5, 6}.

We dequeue 4 and enqueue all unvisited vertices (visited[7] = true; visited[8] = true) to Q, which gives Q = {5, 6, 7, 8}.

We dequeue 5 and enqueue all unvisited vertices (there are none) to Q, which gives Q = {6, 7, 8}.

We dequeue 6 and enqueue all unvisited vertices (there are none) to Q, which gives Q = {7, 8}.

We dequeue 7 and enqueue all unvisited vertices (3 is visited) to Q, which gives Q = {8}.

We dequeue 8 and enqueue all unvisited vertices (6 is visited) to Q, which gives Q = {}.

The order in which we traverse the graph is

1, 2, 3, 4, 5, 6, 7, 8

This is called a breadth-first order traversal.

The following algorithms are based on the depth-first and breadth-first searches:

• Computing the connected component;
• Reporting that a graph has no cycles;
• Computing a path between two given vertices;
• Computing a spanning tree (the BFS tree is typically "short and bushy", the DFS tree is typically "long and stringy")

Topological sorting

A topological sort of a DAG is a listing of its vertices in such an order that if vertex W reachable from vertex V (it means there is a path V->W), then W is listed after V.

Algorithm: count in-degree of each vertex and repeatedly number and remove in-degree 0 vertex along with its out-going edges:

 public ArrayList topologicalSort() throws GraphException
 {
 ArrayList V = new ArrayList();
 Graph clone = (Graph) clone();
 boolean[] marked = new boolean[numVertices];
 
 int count = 0;
 while(V.size() < numVertices && count < numVertices)
 {
 for(int i = 0; i < numVertices; i++)
 {
 if(!marked[i] && clone.inDegree(i) == 0)
 {
 //
 // remove outgoing edges
 //
 }
 }
 count++;
 }
 
 if(V.size() != numVertices)
 {
 throw new GraphException("Graph has a cycle.\n");
 }
 
 return V;
 }

Dijkstra's Algorithm

Consider directed or undirected graph where each edge has a nonnegative weight. One of the nodes is designated as a source s. The length of the path is the sum of the edges' weights. The problem is to find the shortest existing path between s and any of the other vertices in the graph. By shortest path we mean a set of edges with the minimum possible sum of their weights.

How to tackle this problem? The first idea that comes to mind is to use the BFS. As we know the BFS gives the shortest path between any two vertices of an unweighted graph. We can easily adapt this idea to weighted graphs whose edges' weights are all positive integers. All that is required is to replace each edge of weight W by (W-1) vertices of weight 1.

We cannot apply this idea if weights are not integer. In such cases we will use Dijkstra's algorithm. The basic idea behind the algorithm is as follows:

All vertices are divided into two sets:

D (discovered vertices) and U (undiscovered yet vertices).

At the very beginning, D contains only the source. At each step we choose a

vertex from U whose weight to the source is least.

Let L(x) denote the length of a shortest path from s to a vertex x. L(x) will always store the length of the best path (so far discovered) from s to x. Procedure in pseudo-code

• Set L(s) = 0
• Set L(x) = infinity for all vertices x != s
• Let T be the set of all vertices in graph including s
• while T is not empty
1. choose vertex v in T with minimum length L(v) from s to v
2. Edge Relaxation: for each x in T and adjacent to v

L(x) = min( L(x), L(v) + w(v,x) )

3. remove v from T:

T = T - {v}

Example:

 b 5 d 
 o-------o 
 /| /|\
 4 / | 8/ | \ 6 
 / | / | \ 
a o 1| / 2| o z
 \ | / | /
 2 \ | / | / 3
 \|/ |/
 o-------o
 c 10 e
 
Procedure:
 
L(a)=0 L(b)=inf L(c)=inf L(d)=inf L(e)=inf L(z)=inf 
T={a,b,c,d,e,z}
 
min is L(a)
L(a)=0 L(b)=4 L(c)=2 L(d)=inf L(e)=inf L(z)=inf 
Remove a. T={b,c,d,e,z}
 
min is L(c)
L(a)=0 L(b)=3 L(c)=2 L(d)=10 L(e)=12 L(z)=inf
Remove c. T={b,d,e,z}
 
min is L(b)
L(a)=0 L(b)=3 L(c)=2 L(d)=8 L(e)=12  L(z)=inf
Remove b. T={d,e,z}
min is L(d)
L(a)=0 L(b)=3 L(c)=2 L(d)=8 L(e)=10 L(z)=14
Remove d. T={e,z}
 
min is L(e)
L(a)=0 L(b)=3 L(c)=2 L(d)=8 L(e)=10 L(z)=13
Remove e. T={z}
 
L(a)=0 L(b)=3 L(c)=2 L(d)=8 L(e)=10 L(z)=13
T={}
 
Output: L(z) = 13
 

vector T	a	b	c	d	e	z
{a, b, c, d, e, z}	0	inf	inf	inf	inf	inf
{ b, c, d, e, z }		4	2
{ b, d, e, z }		3		10	12
{ d, e, z }				8
{ e, z}					10	14
{ z}		3	2	8	10	13

If we explore the whole graph we will find the minimal distances from s to all other vertices. Dijkstra's algorithm is an example of greedy algorithms -- finding a locally optimal solution. The greedy method may not necessarily find the best solution.

We should be careful and not to introduce a negative weight cycles. Because in this case anyone can build an arbitrary low cost path! In the example below, (c, d, b) is a cycle with negative weight.

 b 5 d 
 o-------o 
 /| /|\
 4 / | -8/ | \ 6 
 / | / | \ 
a o 1| / 2|  o z
 \ | / | /
 2 \ | / | / 3
 \|/ |/
 o-------o
 c 10 e

The solution which we fond before (a,c,b,d,e,z) is not optimal now , (a,c,b,d,c,b,d,e,z) is much lower 11. If we add 8 to all edges and then apply the algorithm we will get a different path:

	A	B	C	D	E	Z
{A, B, C, D, E, Z }	0	inf	inf	inf	inf	inf
{ B, C, D, E, Z }	0	12	10
{ B, D, E, Z }	0			10	28
{ B, E, Z }	0				20	24
{ E, Z }	0
{ Z}	0

Exercise 2.

Perform Dijkstra’s shortest path algorithm starting from vertex A.

	A	B	C	D	E	F	G	H
{A, B, C, D, E, F, G ,H}	0	inf	inf	inf	inf	inf	inf	inf
{ B, C, D, E, F, G ,H}	0	5	4		6			25
{ B, D, E, F, G ,H}	0			7		6
{ D, E, F, G ,H}	0							9
{ D, F, G ,H}	0						40
{ F, G ,H}	0						11
{ G ,H}	0						8
{ H}		5	4	7	6	6	8	9

Complexity:

· while T is not empty

1. find min and remove O(|V|)

2. for each x in T adjacent to v (this process is called relaxing the edge)
L(x) = min( L(x), L(v) + w(v,x) ) O(Adj)

----

 \

> |V| + | Adj | = O(|V|^2 + |E|) = O(|V|^2 )

/

----

all vertices