12. Graph Algorithms
Now we have the tools to see some graph algorithms.
12.1. Topological Sort
A topological sort is an ordering of nodes in a directed acyclic graph.
If there is a path from \(v_i\) to \(v_j\).
Then \(v_j\) appears after \(v_i\) in the ordering.
Example
Following an acyclic graph.
An example of a topological ordering: \(v_1, v_2, v_5, v_4, v_7, v_3, v_6\).
Activity
Give another topological ordering.
12.1.1. A Simple Algorithm
We define the indegree of a node \(v\), as the number of edges \((u,v)\).
A simple algorithm to find topological ordering is:
Find any vertex with an indegree of 0.
Remove it along with its edges.
Apply the strategy with another vertex.
We obtain the following pseudocode:
1void topsort()
2{
3 for (int counter = 0; counter < NUM_VERTICES; counter++){
4 Vertex v = findNewVertexOfIndegreeZero();
5 if (v == NOT_A_VERTEX){
6 throw CycleFoundException();
7 }
8 v.topNum = counter;
9 for each Vertex w adjacent to v{
10 w.indegree--;
11 }
12 }
13}
Where
findNewVertexOfIndegreeZero()
scans the array of vertices looking for a vertex with indegree 0.If it returns
NOT_A_VERTEX
it indicates that the graph has a cycle.The complexity of this algorithm \(O(|V|^2)\).
12.1.2. A Second Algorithm
The graph could be parsed, so checking each vertex could be a waste of time.
A second way to make a topological sort is to place every vertex of indegree 0 in a queue.
While the queue is not empty we remove one vertex.
All the adjacent vertices have their indegree decremented.
Following a pseudo-code of the algorithm:
1void topsort()
2{
3 Queue<Vertex> q;
4 int counter = 0;
5
6 q.makeEmpty( );
7 for each Vertex v
8 if( v.indegree == 0 )
9 q.enqueue( v );
10
11 while( !q.isEmpty( ) )
12 {
13 Vertex v = q.dequeue( );
14 v.topNum = counter++; // Assign next number
15 for each Vertex w adjacent to v
16 w.indegree--;
17 if(w.indegree == 0 )
18 q.enqueue( w );
19 }
20
21 if( counter != NUM_VERTICES )
22 throw CycleFoundException();
23}
The running time of this algorithm is \(O(|E|+|V|)\).
Activity
Can you explain the running time?
Apply this algorithm to the previous graph.
12.2. Graph Traversal Algorithms
Sometimes we need to traverse all the nodes of a graph.
12.2.1. Breadth-First Search
A very simple algorithm is breadth-first search.
The idea is to process nodes in layers.
Example
Consider the previous unweighted directed graph.
We want to apply breadth first from \(v_1\).
We obtain the following steps:
We start with the first node \(v_1\).
We check each arc leaving \(v_2\).
We check each arc leaving \(v_4\).
Finally, the arcs leaving \(v_3\).
Activity
Apply the algorithm to find the shortest path from \(v_4\) to \(v_1\).
12.2.1.1. Implementation
First we create a table that will keep track of the algorithm progress.
The table will keep track for each node it was visited or marked.
The pseudo-code is given below:
function BFS(Graph, source):
Create a queue Q.
Q.insert(s).
while Q not empty:
u = Q.pop()
visit(u)
for all v adjacent to u:
if v not marked or visited:
Mark v
Q.insert(v)
The complexity of this algorithm is \(O(|E|)\).
Activity
Is the algorithm efficient?
12.2.2. Depth-First Search
Another way of traversing a graph is depth-first search (DFS).
In contrary of BFS, DFS go in depth first.
You start in a vertex \(v_i\).
You visit an adjacent node \(v_j\).
Then you visit an adjacent node of \(v_j\).
When no other adjacent node can be visited, we back up and check if an unvisted node can be visited.
Example
Consider the following unweighted graph.
We want to apply depth-first search.
We start with the first node \(0\).
We pick an edge leaving \(0\), and visit \(1\).
We pick an edge leaving \(1\), and visit \(3\).
We pick an edge leaving \(3\), and visit \(4\).
There is no unvisited node adjacent to \(4\), so we mark it.
There is no unvisited node adjacent to \(3\), so we mark it.
There is no unvisited node adjacent to \(1\), so we mark it.
There is an unvisited node adjacent to \(0\), so we visit it.
We pick an edge leaving \(6\), and visit \(5\).
We pick an edge leaving \(5\), and visit \(2\).
Now we can mark the nodes, and we are done.
12.2.2.1. Implementation
First we create a table that will keep track of the algorithm progress.
The table will keep track for each node it was visited or marked.
The pseudo-code is given below:
function DFS(Graph, v):
label v as discovered
for all v adjacent to u:
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
The complexity of this algorithm is \(O(|V|+|E|)\).
Activity
Is the algorithm efficient?