有向图的传递闭包

定义：有向图G=(V,E)，G的传递闭包定义为图G*=(V,E*)，其中E*={(i,j):图G中存在一条从i到j的通路}

 方案1：

对E中每条边赋以权值1，然后运行Floyd-Warshall算法。如果从顶点i到顶点j存在一条路径，则d_ij < n,否则d_ij=INFINITY.

 

方案2：

如果图G中从顶点i到顶点j存在一条通路，且其所有中间顶点均属于集合{1,2,...,k}，则定义t_ij(k) 为true，否则为false。我们把边(i,j)加入E*中当且仅当t_ij(n) = true

递归式为

t_ij⁽⁰⁾ =false if i!=j and (i,j)不属于E  or true if i=j or (i,j)属于E

 

对k>=1

t_ij^(k)=t_ij^(k-1) || (t_ik^(k-1) && t_kj^(k-1))

 

 

#include <iostream>
using namespace std;

typedef struct Graph
{
    static const int vertex_num=4;
    int edge_num;
    int W[16];
}Graph;



void Create_Graph(Graph* g)
{
    for(int i=0;i<16;++i)
    {
        if(i%5==0)
            g->W[i]=0;
        else
            g->W[i]=999;
    }
    cout <<"Enter edges num:";
    cin >>g->edge_num;
    for(int i=0;i<g->edge_num;++i)
    {
        int u,v,w;
        cout <<"Enter u,v,w:";
        cin >>u>>v>>w;
        int index=4*(u-1)+v-1;
        g->W[index]=w;
    }    
}


bool T[4][16];



void Transitive_Closure(const Graph* g)
{
    for(int i=1;i<=4;++i)
    {
        for(int j=1;j<=4;++j)
        {
            int index=4*(i-1)+j-1;
            if(g->W[index]==999)
                T[0][index]=false;
            else
                T[0][index]=true;
        }
    }
    for(int k=1;k<=4;++k)
    {
        for(int i=1;i<=4;++i)
        {
            for(int j=1;j<=4;++j)
            {
                T[k][4*(i-1)+j-1]=T[k-1][4*(i-1)+j-1] || (T[k-1][4*(i-1)+k-1] && T[k-1][4*(k-1)+j-1]);
            }
        }
    }

    for(int i=0;i<16;++i)
    {
        int u=i/4+1;
        int v=i%4+1;
        if(T[4][i])
            cout <<"There is a path from "<<u<<" to "<<v<<endl;
    }
}


int main()
{
    Graph* g=new Graph;
    Create_Graph(g);
    Transitive_Closure(g);

    delete g;
    return 0;
}