Description
Suppose we have a directed graph G = (V, E). It's useful to know, given a pair of vertices u and w, whether
there is a path from u to w in the graph. A nice way to store this information is to
construct another graph, call it G*
= (V, E*), such that there is an edge (u, w) in G* if and only if there is a path from u to w in G. This graph is called the transitive
closure of G.
Let n be
the size of V. For k in 0..n, let t(k) be an adjacency
matrix such that, if there is a path in G from any
vertex i to any other vertex j going only through vertices
in { 1, 2,..., k }, then t(k)[i,j] = True, False otherwise.
This set { 1,
2, ..., k } contains the intermediate vertices along the path from
one vertex to another. This set is empty when k=0, so our previous definition
of t(0) is still valid. When k=n, this is the set of all
vertices, so t(n)[i,j] is True if and only if there is a path
from i to j through any vertex. Thus t(n) is the
adjacency matrix for the transitive closure of G.
The transitive closure is calculated using the formula for k >=
1:
t(k)[i,j] = t(k-1)[i,j]
OR (t(k-1)[i,k] AND t(k-1)[k,j])
Solution:
#include<stdio.h>
void wars();
int a[20][20],n,i,j,k;
void main()
{
printf("ENTER
THE NO OF NODES");
scanf("%d",&n);
printf("ENTER
THE ADJECENCY MATRIX\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a[i][j]);
}
}
wars();
}
void wars()
{
int k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=(a[i][k]&&a[k][j])||a[i][j];
printf("THE
TRANSITIVE MATRIX IS\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",a[i][j]);
}
printf("\n");
}
return;
}
OUTPUT :
ENTER THE NO OF NODES4
ENTER THE ADJECENCY MATRIX
0 1 0 0
0 0 0 1
0 0 0 0
1 0 1 0
THE TRANSITIVE MATRIX IS
1 1 1
1
1 1 1
1
0 0
0 0
1 1 1
1
No comments:
Post a Comment