AIM : Compute the transitive closure of a given directed graph using Warshall's algorithm.

DESCRIPTION :

Warshall's algorithm determines whether there is a path between any two nodes in the graph. It does not give the number of the paths between two nodes. According to Warshall's algorith,a path exists between two vertices i, j, iff there is a path from i to j or there is a path from i to j through 1,..,k intermadiate nodes.

ALGORITHM:

    n = |V|
    t(0) = the adjacency matrix for G

    for i in 1..n do
        t(0)[i,i] = True
    end for

    for k in 1..n do
        for i in 1..n do
            for j in 1..n do
                t(k)[i,j] = t(k-1)[i,j] OR
                    (t(k-1)[i,k] AND t(k-1)[k,j])
            end for
        end for
    end for
    return t(n)

CODE :

#include<stdio.h>
const int MAX = 100;

void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert);
int main(void)
{
    int i, j, numVert;
    int graph[MAX][MAX];

    printf("Warshall's Transitive Closure\n");
    printf("Enter the number of vertices : ");
    scanf("%d",&numVert);

    printf("Enter the adjacency matrix :-\n");
    for (i=0; i<numVert; i++)
        for (j=0; j<numVert; j++)
            scanf("%d",&graph[i][j]);

    WarshallTransitiveClosure(graph, numVert);

    printf("\nThe transitive closure for the given graph is :-\n");
    for (i=0; i<numVert; i++)
    {
        for (j=0; j<numVert; j++)
        {
            printf("%d\t",graph[i][j]);
        }
        printf("\n");
    }

    return 0;
}

void WarshallTransitiveClosure(int graph[MAX][MAX], int numVert)
{
    int i,j,k;

    for (k=0; k<numVert; k++)
    {
        for (i=0; i<numVert; i++)
        {
            for (j=0; j<numVert; j++)
            {
                if (graph[i][j] || (graph[i][k] && graph[k][j]))
                    graph[i][j] = 1;
            }
        }
    }
}

OUTPUT

Enter the number of vertices : 4 Enter the adjacency matrix :- 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0

The transitive closure for the given graph is :- 1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1

Warshall's Transitive Closure Enter the number of vertices : 4 Enter the adjacency matrix :-

0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

The transitive closure for the given graph is :- 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1