基于动态规划的闭包计算

【题目】：设G=(V,E)是一个有n个顶点的有向图，G在顶点集V上到处一个关系R，它是这样定义的：uRv当且仅dang 从u到v存在一条有向边，即当且仅当（u,v）∈E。设MR是G的邻接矩阵，即MR是一个n x n矩阵，如果（u,v）∈E，则MR[u,v]=1,否则为0。MR的自反和传递闭包MR*,定义如下，对于u,v∈V,如果u=v或G中存在一条从u到v的路径，那么，MR*[u,v]=1,否则为0。对于给定的有向图，请设计一个动态规划算法来计算MR*。
【解题】：这里我们在floyd求最短路径算法的基础上，稍作修改就得到了我们这里所要的答案。这里我用M[][]代表题目的MR[][]，MB[][]代表题目中的MR*[][]。

这里我们用random()函数（在宏定义中定义）随机生成0，1的数，给M[n][n]就行控制。你可以根据需要改变宏定义中N的值。
【代码】：

#include<iostream.h>

#include<stdlib.h>

#include<time.h>

#define N 6 //有向图顶点的个数为N-1

#define random() rand()%2

int M[N][N],MB[N][N];

void floyd()

{

       int i,j,k;

       for(i=1;i<N;i++)

              for(j=1;j<N;j++)

                     MB[i][j]=M[i][j];

       for(k=1;k<N;k++)

              for(i=1;i<N;i++)

                     for(j=1;j<N;j++)

                     {

                            if(MB[i][j]==0)

                            {

                                   if(i==j || (MB[i][k]!=0 && MB[k][j]!=0))

                                          MB[i][j]=1;

                            }

                     }

}

void main()

{

       srand((int)time(NULL));

       for(int i=1;i<N;i++)

       {

              for(int j=1;j<N;j++)

              {

                     if(i==j)

                            M[i][j]=0;

                     else

                            M[i][j]=random();

                     cout<<M[i][j]<<" ";

              }

              cout<<endl;

       }

       cout<<endl;

       floyd();

       for(i=1;i<N;i++)

       {     for(int j=1;j<N;j++)

                     cout<<MB[i][j]<<" ";

              cout<<endl;

       }

}

基于动态规划的闭包计算

Advertisements

留言

推荐文章

Links