This is the second part of article names GRAPH. Click on graph and read that article first.

Graph Traversals

A graph traversal means visiting all the nodes of the graph. There are two main graph traversal methods:

1.    Breadth First Search
2.    Depth First Search

Breadth First Search

In breadth first search, one node is selected as the start position. It is visited first and marked and then all adjacent nodes to that node are visited and marked in some sequential order. Once this is done, all remaining unvisited nodes immediately adjacent to these nodes are visited and marked. This process goes on until the entire graph has been traversed.

Consider the graph shown in figure-10. Initially all the nodes are assigned False (0) then the initial state will look like, as shown in figure-11. Let we start with A. Its adjacent nodes are B, C and D. We visit all one by one. Let we pick B. The unvisited adjacent to B is E. We visit E and go back to the remaining unvisited nodes of A and let we pick C. The unvisited adjacent to C is F. We visit F and go back to the remaining unvisited nodes of A. Finally we pick D and visited the unvisited adjacent to D, that is F. Thus the sequence so generated is A, B, E, C, F, D, G

Figure 10

For this we need a queue and add unvisited nodes adjacent to the one just visited at the rear and read at front to find the next node to visit. Figure-11 shows the step-by-step procedure.

Figure 11

Here is the algorithm that performs this task.

Algorithm : BreadthFirstSearch

Here is the ‘C’ implementation of this algorithm:

BreadthFirstSearch(adj[], n, s)

Here ‘adj’ is an array of graph nodes, ‘n’ is th total number of nodes in a graph and ‘s’ is the source node from which the traversal is being started.

Step-1 : Initialize  Visited[s]=True
Step-2 : Initialize front = NULL and rear = NULL
Step-3 : Call InsertQueue(&front, &rear, s);
Step-4 : Repeat through step-14 while (!(front==NULL))
Step-5 :     Set u = front node of the queue
Step-6 : Set current=adj[u]
Step-7 : Repeat through step-12 while (current!=NULL)
Step-8 : Initialize     v=current->vertex
Step-9 : Check if (Visited[v]==False) then go to step-10
Otherwise go to step-12
Step-10 : Set Visited[v]=True
Step-11 : Call InsertQueue(&front, &rear, v)
Step-12 : Update the value of ‘current’ as current=current->link
Step-13 : Delete the front node of the queue and assign it to ‘u’ as u=DeleteQueue(&front, &rear);
Step-14 : Print the value of ‘u’
Step-15 : Exit

Implementation : BreadthFirstSearch

BreadthFirstSearch(GraphNode *adj[], int n, int s)
{
 GraphNode *current, *front, *rear;
 int u, v;
 Visited[s]=True;
 front = rear = NULL;
 InsertQueue(&front, &rear, s);
 while (!(front==NULL))
 {
 u = FrontElement(front);
 current=adj[u];
 while (current!=NULL)
 {
 v=current->vertex;
 if (Visited[v]==False)
 {
 Visited[v]=True;
 InsertQueue(&front, &rear, v);
 current=current->link;
 }
 else
 current=current->link;
 }
 u=DeleteQueue(&front, &rear);
 printf("\n%d",u);
 }
}

In this function we have used three function InsertQueue(), DeleteQueue() and FrontElement().

Depth First Search

In depth first search, the first node is visited initially and then the unvisited node which is adjacenct to first node is visited and a depth first search is initiated from the adjacent node. If all the adjacent nodes have been visited then the process back tracks to the last node visited and find another adjacent node and initiate the depth first search from the adjacent one. This process continues until all nodes have been visited.

Here is the algorithm that traverses a graph using dpeth first search technique. 

Algorithm : DepthFirstSearch

DepthFirstSearch(adj[], n, s)

Here ‘adj’ is an array of graph nodes, ‘n’ is th total number of nodes in a graph and ‘s’ is the source node from which the traversal is being started.

Step-1 : Initialize Visited[s]=True
Step-2 : Initialize top = NULL 
Step-3 : Call PushNode(&top, s);
Step-4 : Repeat through step-16 while (!(top==NULL))
Step-5 :     Set u = top node of the queue
Step-6 : Set current=adj[u]
Step-7 : Repeat through step-14 while (current!=NULL)
Step-8 : Initialize     v=current->vertex
Step-9 : Check if (Visited[v]==False) then go to step-10
Otherwise go to step-12
Step-10 : Set Visited[v]=True
Step-11 : Call PushNode(&top, v)
Step-12 : Set u = current->vertex
Step-13 : Update the value of ‘current’ as current=adj[u]
Step-14 : Update the value of ‘current’ as current as
Current = current->link;               
Step-15 : Delete the top node of the stack and assign it to ‘u’ as u=PopNode(&top);
Step-16 : Print the value of ‘u’
Step-17 : Exit

The ‘C’ implementation of this algorithm is as:

Implementation : DepthFirstSearch

DepthFirstSearch(GraphNode *adj[], int n, int s)
{
 GraphNode *current, *top;
 int u, v;

 Visited[s]=True;
 top=NULL;
 PushNode(&top, s);

 while (top!=NULL)
 {
 u = StackTopNode(top);
 current=adj[u];

 while (current!=NULL)
 {
 v=current->vertex;
 if (Visited[v]==False)
 {
 Visited[v]=True;
 PushNode(&top, v);
 u=current->vertex;
 current=adj[u];
 }
 else
 current=current->link;
 }

 u=PopNode(&top);
 printf("\n%d",u);
 }
}

In this function we have used three function PushNode(), PopNode() and StackTopNode().

Topological Sort

If G is a directed graph with no direct cycles then a topological order of G is a linear ordering of all the vertices in G such that if G contains an edge from v to w (v, w), then v appears before w in the linear ordering. Such a graph is also known as directed acyclic graph (DAG) or simple DAG. Remember that if G contains any cycle then the graph G is not DAG and thus no linear ordering is possible.

DAGs are used in many applications to indicate precedence among events. For example, consider the courses available at a university as the vertices of a graph G, where there is an edge from one course to another, if the first is a prerequisite from the second.

In topological sort we perform depth first traversal on each vertex. As each vertex is finished we insert it at front of the linked list, say first. And finally we print the elements of the linked list in order. Consider the DAG as shown in figure-12.

Figure 12

The adjacency list of graph, shown in figure-12, is as shown in figure-13

Figure 13

Figure-14 shows the step-by-step procedure of finding the topological order of a DAG of figure-12

Figure 14

Now let us develop algorithms that produce a topological ordering of the vertices of a DAG.

Algorithm : TopologicalSort

TopologicalSort(adj, n, first)

Here adj is the adjacency list of ‘n’ number of vertices and first is a pointer to a pointer to a list of nodes which contains the list of vertices in topological order. 

Step-1 : Initialize i=1
Step-2 : Repeat through step-4 while (i<=n)
Step-3 : Set Visited[i] = false
Step-4 : Increment the value of i as i=i+1
Step-5 : Initialize i=1
Step-6 : Repeat through step-8 while (i<=n)
Step-7 : Call DFSModified() algorithm if (Visited[i] == false)
Step-8 : Increment the value of i as i=i+1
Step-9 : Exit

This algorithm calls DFSModified(). The working of DFSModified() algorithm is as:

DFSModified(adj, n, first)

Here adj is the adjacency list of ‘n’ number of vertices and first is a pointer to a pointer to a list of nodes which contains the list of vertices in topological order.

Step-1 : Set Visited[v] = 1
Step-2 : Initialize     ptr = adj[v]
Step-3 : Repeat through step-6 while (ptr != NULL)
Step-4 : Set w = ptr->vertex
Step-5 : If (Visited[w] == false) then Call DFSModified(adj, w, first)
Step-6 : Update the value of ptr as ptr = ptr->link
Step-7 : Create a temporary node ‘temp’
Step-8 :     Set temp->vertex = v
Step-9 : Set temp->link = (*first)
Step-10 : Update the value of first as (*first) = temp
Step-11 : Exit

The implementation of these algorithms is as:
Implementation : TopologicalSort

TopologicalSort(GraphNode *adj[], int n, GraphNode **first)
{
 int i;
 for(i=1; i<=n; i++)
 Visited[i] = False;

 for(i=1; i<=n; i++)
 {
 if (Visited[i] == False)
 DFSModified(adj, i, first);
 }
}
DFSModified(GraphNode *adj[], int v, GraphNode **first)
{
 int w;
 GraphNode *ptr, *temp;
 Visited[v] = True;
 ptr = adj[v];

 while (ptr != NULL)
 {
 w = ptr->vertex;
 if (Visited[w] == False)
 DFSModified(adj, w, first);
 ptr = ptr->link;
 }
 temp = getnode();
 temp->vertex = v;
 temp->link = (*first);
 (*first) = temp;
}

Minimum Spanning Trees

A graph is said to be spaning tree if it has (n-1) edges for ‘n’ vertices. A spanning tree ‘T’ for a connected weighted graph ‘G’ is said to be minimum if the sum of the weights of the tree edges in T is as small as possible. A minimum spanning tree represents the cheapest way of connected all the nodes in ‘G’. In general, a weighted graph may have more than one minimum spanning tree, that is the minimum spanning tree of a graph is not necessarily unique.

There are numbers of algorithms for creating a minimum spanning tree for a weighted graph. But here we will study two familiar algorithms – Kruskal and Prim, to compute minimum cost spanning tree of a weighted graph.

Kruskal’s Algorithm

Kruskal’s algorithm was designed by J.Kruskal in 1957. This algorithm works on a list of edges of a graph (the list is sorted in order of increasing weights (costs) of the edges). A list of edges can be easily created from adjacency matrix or adjacency list of a graph. Once this list of edges is created, we sort this list in increasing order of their weights.

Initially the nodes of a graph are considered as ‘n’ distinct partial trees with one node each. At each step of algorithm two distinct partial trees are connected into a single partial tree by an edge from the sorted list. The edge is added only if its inclusion does not form a cycle, that is an edge with the smallest weight is inserted without introducing a cycle. After the inclusion of an edge, it is deleted from the sorted list. This process goes on until (n-1) edges are inserted or the list of edges is exhausted. When only one partial tree exists (after ‘n-1’ insertions) it is a minimum spanning tree. One main point to remember in Kruskal algorithm is to determine whether the insertion of a new edge introduces a cycle in a forest or not.

Let us understand this process by considering an undirected weighted graph as shown in figure-15.

Figure 15

Initially we will create a list of edges in a list ‘EdgeList’ and then we will sort this EdgeList according to their increasing weights. The list of sorted edges of graph, shown in figure-15, is as:

(1, 2)    (1, 3)    (2, 3)    (2, 4)    (2, 5)    (5, 6)    (3, 4)    (3, 6)

Initially we have 6 distinct partial trees with one node each as shown in figure-16(a). We take the first edge from the sorted list and connect two partial tree of vertices 1 and 2 as shown in figure-16(b). Next we take second edge from the list and connect vertices 1 and 3 as shown in figure-16(c). Figure-16 shows step-by-step procedure to creating a minimum spanning tree.

Figure 16

Now let us write an algorithm, which form a minimum spanning tree from a weighted undirected graph. Input to this algorithm is a list of edges ‘EdgeList’ which is being sorted in increasing order of their weights and ‘n’ number of vertices in the graph. However the definition of nodes of EdgeList and MainList is slightly different than GraphNode.

The definition of an EdgeNode is as follows:

struct EdgeNode
{
 int v;
 int w;
 int weight;
 struct EdgeNode *link;
};
typedef struct EdgeNode EdgeNode;

This algorithm arranges the edges in MainList in the order in which they are connected to partial minimum spanning tree.

Algorithm : KruskalMinSpanningTree

KruskalMinSpanningTree(EdgeList, n, MainList)

Here EdgeList contains the address of the edges of the graph in increasing order of their weights, ‘n’ is total number of nodes and MainList is passed as pointer to a pointer. 

Step-1 : Initialize    i=1
Step-2 : Repeat through step-4 while (i<=n)
Step-3 : Set parent[i] = i
Step-4 : Increment the value of i as i=i+1
Step-5 : Initialize edgecount=1
Step-6 : Repeat through step-12
while ((edgecount < n)&&(EdgeList != NULL))
Step-7 : Set current = EdgeList
Step-8 : Update the value of EdgeList = EdgeList->link
Step-9 : If current does not form a cycle in MainList then go to step-10; otherwise go to step-6
Step-10: Check if ((*MainList) == NULL) then
Set (*MainList) = current and temp = (*MainList)
Otherwise Set temp->link = current and  temp = temp->link
Step-11:    Set temp->link = NULL
Step-12 : Increment the value of edgecount as
edgecount = edgecount+1
Step-12 :Exit

The implementation of this function is as:

Implementation : KruskalMinSpanningTree

KruskalMinSpanningTree(EdgeNode *EdgeList, int n, EdgeNode **MainList)
{
 EdgeNode *current, *temp;
 int parent[Size];
 int i, x, y, wt, edgecount;
 edgecount=1;
 for(i=1; i<=n; i++)
 parent[i] = i;
 while ((edgecount < n)&&(EdgeList != NULL))
 {
 current = EdgeList;
 EdgeList = EdgeList->link;
 x = find((current->v), parent);
 y = find((current->w), parent);

 if (x != y)
 {
 parent[x] = y;
 edgecount++;
 if ((*MainList) == NULL)
 {
 (*MainList) = current;
 temp = (*MainList);
 }
 else
 {
 temp->link = current;
 temp = temp->link;
 }
 temp->link = NULL;
 }
 }
}

This algorithm makes use of another function find() in order to find whether the addition of specific edge introduces a cycle or not. Here is the definition of find() function:

find(int i, int parent[])
{
 int j;
 j=i;
 while (parent[j] != j)
 j = parent[j];
 return (j);
}

The time complexity of creating a sorted list of edges is O(e*loge), where ‘e’ is the number od edges in the graph and O(logn) is the time complexity of detecting whether an edge forms a cycle or not. Thus the overall time complexity of this algorithm is O(e*loge) + O(e*logn).

Prim’s Algorithm

In this an arbitrary node of graph ‘G’ is chosen initially from ‘n’ number of nodes as the tree root of the partial minimum spanning tree ‘T’. The nodes of the graph ‘G’ are then appended to the tree one at a time until all nodes of the Graph ‘G’ are included. In each iteration, one edge (v, w) is added to this partial tree ‘T’ so that one end of this edge belongs to the set of vertices in ‘T’, of all such possible edges the edge having the minimum weight is selected.

In other words each iteration the node (vertex) of the graph added to the tree is that node adjacent to a node of the tree by an edge of minimum weight. The edge of minimum weight becomes a tree edge connected a new node to the tree. Finally when all the nodes of the graph ‘G’ have been added to the tree, a minimum spanning tree ‘T’ has been constructed for the graph ‘G’.

In order to implement this we maintain one array Visited[] and two linked lists – EdgeList and MainList. The array Visited maintains the vertices which are included in the minimum spanning tree. The list EdgeList contains those edges which are have exactly one end belonging to the partial minimum spanning tree. The list MainList contains those edges which are chosen to form minimum spanning tree.

Let we have a graph as shown in figure-15. The illustration of the working of Prim’s algorithm is shown in figure-17.

Figure 17

Shortest Path Problems

Graphs are more frequently used to represent the highway structure of a district, state or country with vertices representing the area (city or state) and edges representing sections of highway. The edges may then assigned weights which may represent distance, cost, time or some other quantity. If somebody wants to go from one place, say Delhi, to another place, say Moscow, then he would be interested in answers to the following questions:

(i)    Is there any path from Delhi to Moscow
(ii)    If there is more than one path from Delhi to Moscow then which is the shortest one

These problems are special types of path problems that we shall be studying in this section. In this section we will study shortest path problems in weighted graphs. In a general weighted graph, G, it is frequently desired to find the shortest path between two nodes (vertices). A path from source vertex ‘v’ to destination ‘w’ is said to be shortest path from ‘v’ to ‘w’ if the sum of weights on the path is as small as possible. In fact there could be more than one path between a pair of specified vertices, say ‘v’ and ‘w’. The shortest path need are not necessarily unique.

Note that the weights can be either positive or negative. But unfortunately applications using negative weights are very-very rare. Therefore for the sake of simplicity we will consider the cases where edges have positive values. Consider the weighted graph as shown in figure-18. The shortest path from vertex 1 to vertex 5 goes via vertex 3 and 6 and has a cost of 17, compared to the cost of 24 for the path via vertex 2.

Figure 18

There are many different variations of the shortest path problems, but here we will study only two – the shortest path from a specified source vertex to every other vertex (single source all destinations) and the shortest paths between all possible source and destination vertices (all pairs shortest paths).

Single Source All Destinations

Consider the graph G = (V,E) which contains ‘n’ vertices 1, 2, 3,…., n. Let Wij denotes the weight (cost) of the edge Eij which connects vertex ‘i’ to vertex ‘j’. If the value of Wij is greater than 0 then it means that there is a path from vertex ‘i’ to vertex ‘j’ and if Wij is infinity then it means that there is no path from vertex ‘i’ to vertex ‘j’. Usually shortest paths are defined on weighted directed graph. An edge from a directed graph (v, w) has to be interpreted as two edges (v, w) and (w, v). For the further discussion of finding shortest path problems we will consider weighted undirected graph.

Dijkstra’s Algorithm (Greedy Algorithm)

One popular algorithm for solving single source all destinations problem is due to Dijkstra. This algorithm is called greedy algorithm. This algorithm takes the source vertex 1 and it finds the shortest path from vertex 1 to every vertex in the graph. In this algorithm we keep a set ‘S’ of those vertices whose shortest distance from vertex 1 is known. Initially it contains only vertex 1. At each step we add to ‘S’ remaining vertex for which the shortest path from vertex 1 has been calculated.

The main point to keep in mind is to find out which vertex to add to ‘S’ at each step. To facilitate this we will use an array, called d[], to keep track the current shortest distance for any vertex from the vertex 1. The value of d[i] is initialized to W0j for all ‘i’, 1 ≤ i ≤ n. The array d[] is maintained in such a way that d[i] gives the shortest distance from vertex 1 to vertex ‘i’ provides i € S. However if ‘i’ is not in ‘S’ then d[i] gives the length of the path from vertex 1 to some other vertex ‘k’ in S plus the weight of the edge from ‘k’ to ‘i’, and all the edges of this path except the last one are marked.

Now let us try to prove that d[i] actually gives the shortest distance between vertex 1 to vertex ‘i’. For this suppose that d[i] is not the shortest distance between vertex 1 to vertex ‘i’ as the shortest path from vertex 1 to vertex ‘i’ consists of a vertex ‘k’ which is not currently included in ‘S’. If it is so then this algorithm will choose ‘k’ rather than ‘i’ for this as the next vertex to add to ‘S’. But the vertex ‘k’ lies on the shortest path from vertex 1 to vertex ‘i’. Thus d[k] < d[i]. After this we must update the entries of d[] by checking, for each vertex k not in ‘S’, whether a path through ‘i’ and then directly to k is shorter than the previous recorded distance to ‘k’. That is we replace d[k] by d[i] plus the weight of the edge from ‘i’ to ‘k’ if later one is shorter.

Before writing an algorithm for computing shortest paths for single source, say vertex 1, to all destinations, let us go through the graph shown in figure-18. Initially the set ‘S’ consists of 1 alone, and the entries of the distance array d[] are shown besides the other vertices. The shortest distance from vertex 1 is from 1 to 3, so 3 is added to S as shown in figure-9(c). Next closest vertex to 1 is vertex 2. Since the distance from vertex 1 to 2 via vertex 3 is smaller than the direct distance from vertex 1 to vertex 2, therefore its distance is updated. These steps are shown one-by-one in figure-19.

Now let us write an algorithm for this.

Algorithm : DijkstraShortPath

DijkstraShortPath(adj, n, d, t, source)

Here ‘adj’ is the adjacency list of ‘n’ number of vertices and source is the starting vertex from where we have to find the shortest paths to all destinations. This algorithm will produce the distances in an array d[] and their paths in array t[].

Step-1 : Initialize i=1
Step-2 : Repeat through step-3 while (i<=n)   
Step-3 : Set d[i] = Infinity, t[i] = source and sd[i] = 0
Step-4 : Increment the value of ‘i’ as i=i+1
Step-5 : Initialize with source vertex alone in the set.
Step-6 : Update the value of ‘d’ according to the source vertex
Step-7 : Set t[source] = -1 and sd[source] = 1
Step-8 : Set d[source] = 0
Step-9 : Initialize x=1
Step-10 : Set min = Infinity
Step-11 : Repeat through step-14 while (x < n)
Step-12 : We will find the closest vertex ‘v’ to source vertex and add it to set
Step-13 : Update the value of remaining distances one by one.
Step-14 : Increment the value of x as x=x+1
Step-15 : Exit

All Pairs Shortest Paths

The all pairs shortest path problems invites the call for finding the shortest paths as well as their weights (costs) between every pair of vertices vi and vj of a graph such that i  ≠ j. Of course we can apply the DijkstraShortPath algorithm ‘n’ times, once with each vertex of the graph ‘G’ as the source vertex. In such case the total complexity of the algorithm will be O(n³). However we can achieve this in same computing time, O(n³), with much simpler way using Floyd-Warshall algorithm. The Floyd-Warshall algorithm also runs in O(n³) time.

Floyd-Warsahl’s Algorithm

Let an adjacency matrix ‘a’ of ‘n’ number vertices, such that there is self-loop, represents a directed weighted graph ‘G’. In this for any pair of vertices, say vertices v_i and v_j, if there is direct shortest path between them without any other intermediate vertex then aij is the shortest distance between vertices v_i and v_j . However there is any shortest path between vertices v_i and v_j using any intermediate vertex, say v1, then a shorter distance between the vertices vi and vj may be recalculated. In other words we have to find the minimum of aij and (a_i1 + a_1j). And this process goes on for more vertices from 1 to k to be used as intermediate vertices and discover even shorter paths.  Now we can easily formalize it.

Let A^k[i,j] denotes the shortest path between the vertices vi and vj of a graph ‘G’ provided that there is no intermediate vertex of index greater than k, say (k+1), (k+2), (k+3),…n. In a generalize way we can say that A_ⁿ[i,j] represents the shortest distance between the vertices vi and vj of a graph ‘G’ since G contains no vertex greater than ‘n’. The basic idea behind this algorithm is to successively generate the matrices A^0, A¹, A²,…,Aⁿ. We can easily generate Ak from A^k-1.

We can generate A^k using A^k-1 by realizing the fact that for any pair of vertices v_i and v_j either – the shorter path from vertices vi to vj going through no vertex with index greater than k does not go through the vertex with index k, or the shortest path from vertices vi to vj go through vertex v^k. In later case the shortest path is divided into two subpaths – p1 and p2. The subpath p1 is from from vertices vⁱ to v^k and p² is from vertices vj to vk. Paths p1 and p2 must be the shortest paths from vertices vi to vk and from vertices vk to vj going through no vertex with index greater than k-1. Based on the above observations, we can define recursive formulation of shortest path for Ak as:

Ak[i, j]= min (Ak-1 [i, j], Ak-1 [i, k]+ Ak-1 [k, j]) for k≥ 1
Or
A0[i, j]= aij

Similarly we can compute the path matrix. Specifically the sequence of the path matrices P0, P1, P2,…., Pn. the elements of Pkij is defined to be predecessor of vertex vj on a shortest path from vertex vi with all intermediate vertices in the set {1, 2, 3, …., k}. Now its recursive definition can be easily written as:

P0[i, j] = 0 (for i=j) or I (if≠ j)
and
Pk [i, j] = Pk-1 [i, j] if Ak-1 [i, j]  Ak-1 [i, k]+ Ak-1 [k, j]) or
= Pk-1 [k, j] if Ak-1 [i, j] > Ak-1 [i, k]+ Ak-1 [k, j])

Let us understand this algorithm by using the weighted graph shown in figure-20.

Figure 20

The following matrices are the sequence of matrices A and P, generated by using above formulas.

FloydWarshalAllPairPath(adj, n, dist, path)

Here ‘adj’ is an adjacency table of ‘n’ number of vertices. The array dist[] is used to contain the distances between every pair of vertices and the array path contains the shortest path for every pair of vertices. {

Step-1 : Initialize i=1
Step-2 : Repeat through step-7 while (i<=n)
Step-3 :     Initialize j=1
Step-4 : Repeat through step-6 while (j<=n)
Step-5 : Check if (adj[i][j] == 0) then
set path[i][j] = 0 and dist[i][j] = Infinity
else set dist[i][j] = adj[i][j] and path[i][j] = i
Step-6 : Increment the value of j as j=j+1               
Step-7 : Increment the value of i as i=i+1               
Step-8 : Initialize k=1
Step-9 : Repeat through step-18 while (k<=n)
Step-10 : Initializei=1
Step-11 : Repeat through step-17 while (i<=n)
Step-12 : Initialize j=1
Step-13 : Repeat through step-16 while (j<=n)
Step-14 : If (i != j) then go to step-15; otherwise go to step-16
Step-15 : If ((dist[i][j]) > (dist[i][k] + dist[k][j])) then
Set dist[i][j] = dist[i][k] + dist[k][j] and
path[i][j] = path[k][j]
Else set dist[i][j] = dist[i][j] and path[i][j] = path[i][j];
Step-16 : Increment the value of j as j=j+1               
Step-17 : Increment the value of i as i=i+1               
Step-18 : Increment the value of k as k=k+1               
Step-19 : Exit

Transitive Closure of a Directed Graph

Let we have a directed graph G = (V, E) where V is the set of vertices and E is the set of edges. The adjacency matrix ‘A’ of the graph ‘G’ is said to be the transitive closure matrix A+ of the graph ‘G’ if it has the following property:

A+[i, j] = 1 if there is a path in ‘G’ from vertex ‘i’ to vertex ‘j’; 0 otherwise

The simplest way to compute the transitive closure is to assign a weight of 1 to each edge of E in the Floyd-Warshall and use the Floyd-Warshall algorithm. If there exists a path from vertex ‘i’ to vertex ‘j’ then dist[i][j] =1; otherwise dist[i][j]= ∞. However we can even simplify it by slightly modifying the algorithm using the logical operations ν (OR) and Λ (AND) as:

For k=0        Ak[i, j] = 1 if dist[i][j] is not  and 0 if dist[i][j] is 
For k>0        Ak[i, j] = Ak-1[i, j]   (Ak-1[i, k]  Ak-1[k, j])

Here is the algorithm for finding the transitive closure of a directed Graph ‘G’.

Algorithm : TransitiveClosure

TransitiveClosure (adj, n, trans)

Here ‘adj’ is an adjacency table of ‘n’ number of vertices. This algorithm computes the transitive closure and stires the result in matrix ‘trans’.  

Step-1 : Initialize i=1
Step-2 : Repeat through step-7 while (i<=n)
Step-3 :     Initialize j=1
Step-4 : Repeat through step-6 while (j<=n)
Step-5 : Check if (adj[i][j] == 1) then
set trans[i][j] = 1
else set trans[i][j] = 0
Step-6 : Increment the value of j as j=j+1               
Step-7 : Increment the value of i as i=i+1               
Step-8 : Initialize k=1
Step-9 : Repeat through step-17 while (k<=n)
Step-10 : Initializei=1
Step-11 : Repeat through step-16 while (i<=n)
Step-12 : Initialize j=1
Step-13 : Repeat through step-15 while (j<=n)
Step-14 : Set trans[i][j] = trans[i][j]  trans[i][k]  trans[k][j]
Step-15 : Increment the value of j as j=j+1               
Step-16 : Increment the value of i as i=i+1               
Step-17 : Increment the value of k as k=k+1               
Step-18 : Exit

A graph ‘G’ consists of a set of vertices ‘V’ and a set of edges ‘E’ such that G = (V,E) where V={v1, v2, …., vn) and E={e1, e2, …., en). Graphs can be either directed or undirected. In a directed graph, each edge is represented in an ordered pair of vertices, that is e=(v,w) is an edge having ‘v’ as initial vertex and ‘w’ as final vertex. On the other hand, in an undirected graph  the elements of ‘E’ are unordered.

The number of edges incident on a vertex determines its degree. However if you have a directed graph then its degree can be of two types indegree and outdegree. For a directed graph, degree of a vertex is equal to indegree plus outdegree. If a vertex has no edge then it is called as an isolated vertex. An isolated vertex has zero degree. A graph is said to be complete or fully connected if there is path from every vertex to every other vertex. A graph is said to be weighted if every edge in the graph is assigned some weight or value. This weight can represent any positive value. A path from a vertex vi to vj is a sequence of vertices v1, v2, …. such that (vi, vi+1) is an edge where i varies from 1 to j-1 and all edges are distinct.

Two most familiar implementating ways of graphs are adjacency matrix and adjacency list. In an adjacency matrix, each element aijof it is either 0 or 1. If the value of aij is 1 then it means that there is an edge from vertex ‘i’ to vertex ‘j’. Adjacency list of a graph isa linked list representation of it.

Graphs can be traversed in various different ways. Two familiar ones are depth first search and breadth first search. In depth first traversal we start traversing from a vertex, say f, and then explore new vertices by initiating the same process from any of the unvisited vertices adjacent to the starting vertex ‘f’. In breadth first traversal, we start traversing from any vertex, say ‘f’, and visits all unvisited vertices adjacenct to the start vertex ‘f’.

If G is directed graph with no direct cycles then a topological order of G is a linear ordering of all the vertices in G such that if G contains an edge from v to w (v, w), then v appears before w in the linear ordering. Such a graph is also known as directed acyclic graph (DAG) or simple DAG. Remember that if G contains any cycle then the graph G is not DAG and thus no linear ordering is possible. 

A spanning tree ‘T’ for a connected weighted graph ‘G’ is said to be minimum if the sum of the weights of the tree edges in T is as small as possible. There are two familiar algorithms – Kruskal and Prim, to compute minimum cost spanning tree of a weighted graph. Kruskal algorithm works on a sorted list of edges and forms a spanning tree by starting with a forest on ‘n’ vertices. On the other hand, Prim algorithm starts with a vertex and goes on adding edges to an already formed partial minimal spanning tree. This algorithm inserts that minimum cost edge which has exactly one end belonging to the already formed minimal spanning tree.

Finding shortest paths is another important type of problem. A path from source vertex ‘v’ to vertex ‘w’ is said to be shortest path from ‘v’ to ‘w’ if there is no path from ‘v’ to ‘w’ with minimum cost. Two main ways of finding shortest paths are Dijkstra and Floyd-Warshal. Dijkstra algorithm is used for solving single source and all destinations and Floyd-Warshal is used for solving all pair shortest path problem.

 

---

Like it on Facebook, Tweet it or share this article on other bookmarking websites.