C Program to Find the Transitive Closure of a Graph using Warshall’s Algorithm

This is a C Program to find Transitive Closure. Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights but with no negative cycles and also for finding transitive closure of a relation R.

Here is source code of the C Program to Construct Transitive Closure Using Warshall’s Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<math.h>
```
```
int max(int, int);
```
```
void warshal(int p[10][10], int n) {
```
```
    int i, j, k;
```
```
    for (k = 1; k <= n; k++)
```
```
        for (i = 1; i <= n; i++)
```
```
            for (j = 1; j <= n; j++)
```

                p[i][j] = max(p[i][j], p[i][k] && p[k][j]);

```
}
```
```
int max(int a, int b) {
```
```
    ;
```
```
    if (a > b)
```
```
        return (a);
```
```
    else
```
```
        return (b);
```
```
}
```
```
void main() {
```

    int p[10][10] = { 0 }, n, e, u, v, i, j;

    printf("\n Enter the number of vertices:");

```
    scanf("%d", &n);
```

    printf("\n Enter the number of edges:");

```
    scanf("%d", &e);
```
```
    for (i = 1; i <= e; i++) {
```

        //printf("\n Enter the end vertices of edge %d:", i);

```
        scanf("%d%d", &u, &v);
```
```
        p[u][v] = 1;
```
```
    }
```

    printf("\n Matrix of input data: \n");

```
    for (i = 1; i <= n; i++) {
```
```
        for (j = 1; j <= n; j++)
```
```
            printf("%d\t", p[i][j]);
```
```
        printf("\n");
```
```
    }
```
```
    warshal(p, n);
```

    printf("\n Transitive closure: \n");

```
    for (i = 1; i <= n; i++) {
```
```
        for (j = 1; j <= n; j++)
```
```
            printf("%d\t", p[i][j]);
```
```
        printf("\n");
```
```
    }
```
```
    getch();
```
```
}
```

Output:

$ gcc WarshallTransitiveClosure.c
$ ./a.out
 
Enter the number of vertices: 5
Enter the number of edges: 11
Enter the end vertices of edge 1: 1 1
Enter the end vertices of edge 2: 1 4
Enter the end vertices of edge 3: 3 2
Enter the end vertices of edge 4: 3 3
Enter the end vertices of edge 5: 3 4
Enter the end vertices of edge 6: 4 2
Enter the end vertices of edge 7: 4 4 
Enter the end vertices of edge 8: 5 2
Enter the end vertices of edge 9: 5 3
Enter the end vertices of edge 10: 5 4
Enter the end vertices of edge 11: 5 5
 
Matrix of input data: 
1	0	0	1	0	
0	0	0	0	0	
0	1	1	1	0	
0	1	0	1	0	
0	1	1	1	1	
 
Transitive closure: 
1	1	0	1	0	
0	0	0	0	0	
0	1	1	1	0	
0	1	0	1	0	
0	1	1	1	1

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Find the Vertex Connectivity of a Graph

» Next - C Program to Implement Bellman Ford Algorithm

Related Posts:

Recommended Articles: