Code:
#include iostream
#include conio.h
using namespace std;
const int num_nodes = 10;
int main()
{
int num_nodes, k, n;
char i, j, res, c;
int adj[10][10], path[10][10];
cout << "\n\tMaximum number of nodes in the graph :";
cin >> n;
num_nodes = n;
cout << "\n\n\tNODES ARE LABELED AS A,B,C,......\n\n";
cout << "\nEnter 'y'for 'YES' and 'n' for 'NO' !!\n";
for (i = 65; i < 65 + num_nodes; i++)
for (j = 65; j < 65 + num_nodes; j++)
{
cout << "\n\tIs there an EDGE from " << i << " to " << j << " ? ";
cin >> res;
if (res == 'y')
adj[i - 65][j - 65] = 1;
else
adj[i - 65][j - 65] = 0;
}
cout << "\nAdjacency Matrix:\n";
cout << "\n\t\t\t ";
for (i = 0; i < num_nodes; i++)
{
c = 65 + i;
cout << c << " ";
}
cout << "\n\n";
for (int i = 0; i < num_nodes; i++)
{
c = 65 + i;
cout << "\t\t\t" << c << " ";
for (int j = 0; j < num_nodes; j++)
cout << adj[i][j] << " ";
cout << "\n";
}
for (int i = 0; i < num_nodes; i++)
for (int j = 0; j < num_nodes; j++)
path[i][j] = adj[i][j];
for (int k = 0; k < num_nodes; k++)
for (int i = 0; i < num_nodes; i++)
if (path[i][k] == 1)
for (int j = 0; j < num_nodes; j++)
path[i][j] = path[i][j] || path[k][j];
for (int i = 0; i < num_nodes; i++)
for (int j = 0; j < num_nodes; j++)
adj[i][j] = path[i][j];
cout << "\nTransitive Closure of the Graph:\n";
cout << "\n\t\t\t ";
for (i = 0; i < num_nodes; i++)
{
c = 65 + i;
cout << c << " ";
}
cout << "\n\n";
for (int i = 0; i < num_nodes; i++)
{
c = 65 + i;
cout << "\t\t\t" << c << " ";
for (int j = 0; j < num_nodes; j++)
cout << adj[i][j] << " ";
cout << "\n";
}
return 0;
}
Output:
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
Adjacency Matrix:
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)
Press return to continue
More C++ Programs:
