Last Updated:

Transitive graph closure [ c++ ]

A transitive graph is one in which, from the existence of arcs (xixj) and (xjxk) follows the existence of an arc (xi,xk). A transitive closure of a graph G is called a graph G'=(V, E∪E'), where E' is the minimum set of arcs that must be added to the graph G to become transitive.

Today we will look at the implementation of transitive graph closure algorithms. There are several ways to make a calculation: normal (complexity N^4) and improved (complexity N^3)

 

Source file: input_graph.txt

The first line is the number of vertices in the graph, the rest is the direction of the arcs of the graph.

Program code:

In such a simple way, we dealt with the topic: "Transitive closure of the graph"!