# 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.

1. `#include<stdio.h>`
2. `#include<conio.h>`
3. `#include<math.h>`
4. `int max(int, int);`
5. `void warshal(int p[10][10], int n) {`
6. `    int i, j, k;`
7. `    for (k = 1; k <= n; k++)`
8. `        for (i = 1; i <= n; i++)`
9. `            for (j = 1; j <= n; j++)`
10. `                p[i][j] = max(p[i][j], p[i][k] && p[k][j]);`
11. `}`
12. `int max(int a, int b) {`
13. `    ;`
14. `    if (a > b)`
15. `        return (a);`
16. `    else`
17. `        return (b);`
18. `}`
19. `void main() {`
20. `    int p[10][10] = { 0 }, n, e, u, v, i, j;`
21. `    printf("\n Enter the number of vertices:");`
22. `    scanf("%d", &n);`
23. `    printf("\n Enter the number of edges:");`
24. `    scanf("%d", &e);`
25. `    for (i = 1; i <= e; i++) {`
26. `        //printf("\n Enter the end vertices of edge %d:", i);`
27. `        scanf("%d%d", &u, &v);`
28. `        p[u][v] = 1;`
29. `    }`
30. `    printf("\n Matrix of input data: \n");`
31. `    for (i = 1; i <= n; i++) {`
32. `        for (j = 1; j <= n; j++)`
33. `            printf("%d\t", p[i][j]);`
34. `        printf("\n");`
35. `    }`
36. `    warshal(p, n);`
37. `    printf("\n Transitive closure: \n");`
38. `    for (i = 1; i <= n; i++) {`
39. `        for (j = 1; j <= n; j++)`
40. `            printf("%d\t", p[i][j]);`
41. `        printf("\n");`
42. `    }`
43. `    getch();`
44. `}`

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.