『壹』 數據結構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沒有邊；