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

«
»
This is a C++ Program find the transitive closure using Warshall’s algorithm. In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal (Lidl and Pilz 1998:337). If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation. For example, if X is a set of airports and x R y means “there is a direct flight from airport x to airport y”, then the transitive closure of R on X is the relation R+: “it is possible to fly from x to y in one or more flights.”

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<iostream>`
2. `#include<conio.h>`
3. ` `
4. `using namespace std;`
5. `const int num_nodes = 10;`
6. ` `
7. `int main()`
8. `{`
9. `    int num_nodes, k, n;`
10. `    char i, j, res, c;`
11. `    int adj, path;`
12. ` `
13. `    cout << "\n\tMaximum number of nodes in the graph :";`
14. `    cin >> n;`
15. `    num_nodes = n;`
16. `    cout << "\n\n\tNODES ARE LABELED AS A,B,C,......\n\n";`
17. `    cout << "\nEnter 'y'for 'YES' and 'n' for 'NO' !!\n";`
18. ` `
19. `    for (i = 65; i < 65 + num_nodes; i++)`
20. `        for (j = 65; j < 65 + num_nodes; j++)`
21. `        {`
22. `            cout << "\n\tIs there an EDGE from " << i << " to " << j << " ? ";`
23. `            cin >> res;`
24. `            if (res == 'y')`
25. `                adj[i - 65][j - 65] = 1;`
26. `            else`
27. `                adj[i - 65][j - 65] = 0;`
28. `        }`
29. `    cout << "\nAdjacency Matrix:\n";`
30. ` `
31. `    cout << "\n\t\t\t   ";`
32. `    for (i = 0; i < num_nodes; i++)`
33. `    {`
34. `        c = 65 + i;`
35. `        cout << c << " ";`
36. `    }`
37. `    cout << "\n\n";`
38. `    for (int i = 0; i < num_nodes; i++)`
39. `    {`
40. `        c = 65 + i;`
41. `        cout << "\t\t\t" << c << "  ";`
42. `        for (int j = 0; j < num_nodes; j++)`
43. `            cout << adj[i][j] << " ";`
44. `        cout << "\n";`
45. `    }`
46. `    for (int i = 0; i < num_nodes; i++)`
47. `        for (int j = 0; j < num_nodes; j++)`
48. `            path[i][j] = adj[i][j];`
49. ` `
50. `    for (int k = 0; k < num_nodes; k++)`
51. `        for (int i = 0; i < num_nodes; i++)`
52. `            if (path[i][k] == 1)`
53. `                for (int j = 0; j < num_nodes; j++)`
54. `                    path[i][j] = path[i][j] || path[k][j];`
55. ` `
56. `    for (int i = 0; i < num_nodes; i++)`
57. `        for (int j = 0; j < num_nodes; j++)`
58. `            adj[i][j] = path[i][j];`
59. ` `
60. `    cout << "\nTransitive Closure of the Graph:\n";`
61. ` `
62. `    cout << "\n\t\t\t   ";`
63. `    for (i = 0; i < num_nodes; i++)`
64. `    {`
65. `        c = 65 + i;`
66. `        cout << c << " ";`
67. `    }`
68. `    cout << "\n\n";`
69. `    for (int i = 0; i < num_nodes; i++)`
70. `    {`
71. ` `
72. `        c = 65 + i;`
73. `        cout << "\t\t\t" << c << "  ";`
74. `        for (int j = 0; j < num_nodes; j++)`
75. `            cout << adj[i][j] << " ";`
76. `        cout << "\n";`
77. `    }`
78. `    return 0;`
79. `}`

Output:

```\$ g++ Warshall.cpp
\$ a.out

Maximum number of nodes in the graph :5

NODES ARE LABELED AS A,B,C,......

Enter 'y'for 'YES' and 'n' for 'NO' !!
Is there an EDGE from A to A ? y
Is there an EDGE from A to B ?
Is there an EDGE from A to C ?
Is there an EDGE from A to D ? y
Is there an EDGE from A to E ?
Is there an EDGE from B to A ?
Is there an EDGE from B to B ? n
Is there an EDGE from B to C ? n
Is there an EDGE from B to D ? n
Is there an EDGE from B to E ? n
Is there an EDGE from C to A ? n
Is there an EDGE from C to B ? y
Is there an EDGE from C to C ? y
Is there an EDGE from C to D ? y
Is there an EDGE from C to E ? n
Is there an EDGE from D to A ? n
Is there an EDGE from D to B ? y
Is there an EDGE from D to C ? n
Is there an EDGE from D to D ? y
Is there an EDGE from D to E ? n
Is there an EDGE from E to A ? n
Is there an EDGE from E to B ? y
Is there an EDGE from E to C ? y
Is there an EDGE from E to D ? y
Is there an EDGE from E to E ? y

A B C D E

A  1 0 0 1 0
B  0 0 0 0 0
C  0 1 1 1 0
D  0 1 0 1 0
E  0 1 1 1 1

Transitive Closure of the Graph:

A B C D E

A  1 1 0 1 0
B  0 0 0 0 0
C  0 1 1 1 0
D  0 1 0 1 0
E  0 1 1 1 1

------------------
(program exited with code: 0)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs. 