C++ Program to Find the Transitive Closure of a Graph

This C++ program displays the transitive closure matrix of a graph. The reachability of a particular node ‘i’ towards all node pairs (‘i’,’j’) is known as the transitive closure of a graph.

Here is the source code of the C++ program to display the transitive closure of a particular directed graph consisting of four nodes. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.

```
/*
```

 * C++ Program to Find Transitive Closure of a Graph

```
 */
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
#include<iostream>
```
```
using namespace std;
```
```
void printSolution(int reach[][4])
```
```
{
```

    cout<<"Following matrix is transitive closure of the given graph\n";

```
    for (int i = 0; i < 4; i++)
```
```
    {
```
```
        for (int j = 0; j < 4; j++)
```
```
        {
```
```
            cout<<reach[i][j];
```
```
        }
```
```
        cout<<endl;
```
```
    }
```
```
}
```
```
void transitiveClosure(int graph[][4])
```
```
{
```
```
    int reach[4][4], i, j, k;
```
```
    for (i = 0; i < 4; i++)
```
```
    {
```
```
        for (j = 0; j < 4; j++)
```
```
        {
```
```
            reach[i][j] = graph[i][j];
```
```
        }
```
```
    }
```
```
    for (k = 0; k < 4; k++)
```
```
    {
```
```
        for (i = 0; i < 4; i++)
```
```
        {
```
```
            for (j = 0; j < 4; j++)
```
```
            {
```

                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

```
            }
```
```
        }
```
```
    }
```
```
    printSolution(reach);
```
```
}
```
```
int main()
```
```
{
```
```
    int graph[4][4] = { {1, 1, 0, 1},
```
```
                        {0, 1, 1, 0},
```
```
                        {0, 0, 1, 1},
```
```
                        {0, 0, 0, 1}
```
```
                      };
```
```
    transitiveClosure(graph);
```
```
    getch();
```
```
}
```

Output
Following matrix is transitive closure of the given graph
1111
0111
0011
0001

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

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - Inorder Tree Traversal without using Recursion in C++

» Next - C++ Program to Implement Ford Fulkerson Algorithm

Related Posts:

Recommended Articles: