‘壹’ 数据结构C语言版Floyd算法
不知道数据结构C语言版中Floyd算法中，矩阵D没有分别保存D-1
‘贰’ 1.利用求传递闭包的Warshall算法，给定关系R，编写求R的可传递闭包的C语言程序并利用下列数据测试。
c++版
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
void main()
{
int n_dim=0;
cout<<"Input number of dimensions:";
cin>>n_dim;
char **array=new char*[n_dim]; //以下是动态创建一个 n_dim*n_dim 数组，如不太清楚的看我BLOG里的
char ch; //另一篇关于动态数组的文章
for(int i=0;i<n_dim;i++)
{
array[i]=new char[n_dim]; //这句也是
for(int j=0;j<n_dim;j++)
{
cin>>ch;
array[i][j]=ch;
}
}
for(i=0;i<n_dim;i++)
for(int j=0;j<n_dim;j++)
for(int k=0;k<n_dim;k++)
if(array[i][j]=='1'&&array[k][i]=='1')
array[k][j]='1';
cout<<"The trasitive closure of a relation R represented:"<<endl;
for(i=0;i<n_dim;i++)
{
for(int j=0;j<n_dim;j++)
cout<<array[i][j];
cout<<endl;
}
}
另一c++
#include <iostream>
#include <string>
using namespace std;
int **matrix;
void warshall(int n,int **m);
void setValue(int elem1,int elem2,int value);
void buildMatrix(int numElement);
int main()
{
int num;
string str;
cout << "Please input the number of elements:" << endl;
cin >> num;
buildMatrix(num);
cout << "Please input a set,such as R={(x1,x2),(x3,x4),...}: " << endl;
cin >> str;
for(int i=0;i<str.size();i++)
if((str.at(i)=='(') && (str.at(i+2)==','))
setValue(str.at(i+1)-'0',str.at(i+3)-'0',1);
warshall(num,matrix);
return 0;
}
void warshall(int n,int **m)
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(m[j][i] == 1)
for(k=0;k<n;k++)
m[j][k] = m[j][k] || m[i][k];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout << " " << m[i][j] << " ";
cout << endl;
}
}
void setValue(int elem1,int elem2,int value)
{
if(value>0)
matrix[elem1-1][elem2-1] = value;
}
void buildMatrix(int numElement)
{
int i,j;
matrix = (int**) new int*[numElement];
for(i=0;i<numElement;i++)
matrix[i] = new int[numElement];
for(j=0;j<numElement;j++)
for(i=0;i<numElement;i++)
matrix[j][i] = 0;
}
‘叁’ 如何在C语言中采用warshall算法判断一个无向图是否连通
所谓无向图连通，就是任意两个点都存在路径到达
所以需要验证任意a,b两个点之间是否有路。
Warshall算法是一种动态规划算法。
首先设连通矩阵为M，i,j之间连通则Mij = 1,否则Mij = 0
设可能中间点的为c，c = 0
检查所有的ij组合，如果Mic == 1且 Mcj == 1则 Mij变为1，否则不变
然后c++，如果c大于点的数量则退出
最后如果M中全是1则为连通图
‘肆’ floyd-warshall算法的算法概述
单独一条边的路径也不一定是最佳路径。 从任意一条单边路径开始。所有两点之间的距离是边的权的和，(如果两点之间没有边相连, 则为无穷大）。 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 不可思议的是，只要按排适当，就能得到结果。// dist(i,j) 为从节点i到节点j的最短距离
For i←1to n do
For j←1to n do
dist(i,j) = weight(i,j)
For k←1to n do// k为“媒介节点”{一定要先枚举媒介节点}
For i←1to n do
For j←1to n do
if(dist(i,k) + dist(k,j) < dist(i,j))then// 是否是更短的路径？
dist(i,j) = dist(i,k) + dist(k,j)
这个算法的效率是O(V^3)。它需要邻接矩阵来储存图。
这个算法很容易实现，只要几行。
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。
计算每一对顶点间的最短路径（floyd算法）
‘伍’ c++Warshall算法
#include <stdio.h>
#include <stdlib.h>
#define N 20
#define M 20
main()
{
int i,j,k,m,n;
int r1[M],r2[M],a[N],mr[N][N]={0};
FILE * fp;
printf("程序自动调用c:/stone2.txt文件内相应数据\n");
fp=fopen("c:\\stone2.txt","r");
fscanf(fp,"%d",&n); /*读取集合元素个数*/
for(i=0;i<n;i++) /*读取集合元素*/
fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&m); /*读取关系个数*/
for(k=0;k<m;k++)
fscanf(fp,"%d,%d",&r1[k],&r2[k]); /*读取关系*/
fclose(fp);
printf("自反闭包r(R):\n{");
for(i=0;i<n;i++) printf("<%d,%d>,",a[i],a[i]); /*输出自反闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,",r1[k],r2[k]);
else continue;
}
printf("\b}\n");
printf("对称闭包s(R):\n{"); /*输出对称闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k]) printf("<%d,%d>,<%d,%d>,",r1[k],r2[k],r2[k],r1[k]);
else printf("<%d,%d>,",r1[k],r2[k]);
}
printf("\b}\n");
k=0;
for(i=0;i<n,k<m;i++)
{
if(r1[k]!=a[i]) continue;
else
{
for(j=0;j<n,k<m;j++) /*关系转换成矩阵*/
{
if(r2[k]!=a[j]) continue;
else
{
mr[i][j]=1;
k++; i=0;j=0;
break;
}
}
}
}
printf("关系所对应的关系矩阵:\n");
for(i=0;i<n;i++)
{ /*打印关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
for(k=0;k<n;k++)
for(i=0;i<n;i++) /*warshall*/
for(j=0;j<n;j++)
mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{ /*把mr[]非0项赋值为1*/
if(!mr[i][j]) continue;
else mr[i][j]=1;
}
printf("传递闭包对应关系矩阵:\n");
for(i=0;i<n;i++)
{ /*输出传递闭包对应的关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
system("PAUSE");
}
‘陆’ Warshall算法求传递闭包
#include
<stdio.h>
#include
<stdlib.h>
#define
N
20
#define
M
20
main()
{
int
i,j,k,m,n;
int
r1[M],r2[M],a[N],mr[N][N]={0};
FILE
*
fp;
printf("程序自动调用c:/stone2.txt文件内相应数据\n");
fp=fopen("c:\\stone2.txt","r");
fscanf(fp,"%d",&n);
/*读取集合元素个数*/
for(i=0;i<n;i++)
/*读取集合元素*/
fscanf(fp,"%d",&a[i]);
fscanf(fp,"%d",&m);
/*读取关系个数*/
for(k=0;k<m;k++)
fscanf(fp,"%d,%d",&r1[k],&r2[k]);
/*读取关系*/
fclose(fp);
printf("自反闭包r(R):\n{");
for(i=0;i<n;i++)
printf("<%d,%d>,",a[i],a[i]);
/*输出自反闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k])
printf("<%d,%d>,",r1[k],r2[k]);
else
continue;
}
printf("\b}\n");
printf("对称闭包s(R):\n{");
/*输出对称闭包*/
for(k=0;k<m;k++)
{
if(r1[k]!=r2[k])
printf("<%d,%d>,<%d,%d>,",r1[k],r2[k],r2[k],r1[k]);
else
printf("<%d,%d>,",r1[k],r2[k]);
}
printf("\b}\n");
k=0;
for(i=0;i<n,k<m;i++)
{
if(r1[k]!=a[i])
continue;
else
{
for(j=0;j<n,k<m;j++)
/*关系转换成矩阵*/
{
if(r2[k]!=a[j])
continue;
else
{
mr[i][j]=1;
k++;
i=0;j=0;
break;
}
}
}
}
printf("关系所对应的关系矩阵:\n");
for(i=0;i<n;i++)
{
/*打印关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
/*warshall*/
for(j=0;j<n;j++)
mr[i][j]+=mr[i][j]+mr[i][k]*mr[k][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
/*把mr[]非0项赋值为1*/
if(!mr[i][j])
continue;
else
mr[i][j]=1;
}
printf("传递闭包对应关系矩阵:\n");
for(i=0;i<n;i++)
{
/*输出传递闭包对应的关系矩阵*/
for(j=0;j<n;j++)
printf("%5d",mr[i][j]);
printf("\n");
}
system("PAUSE");
}
自己写的,三个闭包都有,包括传递闭包,看注释就知道了,还是用文件读写,方便数据输入
‘柒’ Warshall算法
Warshall算法是计算稠密有向图的传递闭包的首选。
通过计算传递闭包后，可以测试有向图中任何顶点是否可以从其它顶点到达的能力。
经典形式
for(i=0;i<V;++i)
for(s=0;s<V;++s)
for(t=0;t<V;++t)
if(A[s][i] && A[i][t]) A[s][t]=1;
用接邻矩阵A表示有向图，可以定义为 bool A[V][V];
V是A中的总结点数
A[i][j]=1表示从i到j有一条边，
A[i][j]=0表示i到j没有边；