⑴ 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語言提取txt中二維數據，然後輸出到excel中製作成一個鄰接矩陣
這應該是圖論里的比較典型的通路問題，將所有的數據存到一個二維數組a[90][90]，這個數組全部初始化位0，然後根據輸入操作，比如輸入1,75那麼a[0][74] = 1;然後用Warshall演算法求矩陣的傳遞閉包即可！相關資料自己查閱一下，慢慢研究！祝早日成功！
⑶ 用C語言實現以下問題並講解大概思路和所用演算法，非常感謝！
唔，你這個問題的話，因為你這個不指定起點，所以應該是多源最長路徑問題，我參考了一下多源最短路徑的Floyd演算法如下，不知道可不可以啊：
首先是輸入
g[i][j]表示從i城市到j城市所需要的路費，
int g[M][M]={{null,2,1,null},{null,null,5,4},{null,null,null,null},{null,null,null,null}}
null表示兩個城市之間不存在路徑，看上去這個數組很浪費，因為Floyd演算法是可以針對更復雜的圖進行計算的演算法，具體有沒有更優演算法我也不知道=。=
然後讓M=你輸入的城市數量-1，這里M=4
輸入設置好以後，就可以進行循環比較了，通過三重循環的比較，最終得到D[4][4]這樣一個數組，這個數組中的D[i][j]表示從i城市到j城市所需要的最高的路費，然後再通過比較數組D中最大值，應該就可以得出結果了。
這里復制一下原理：
Floyd-Warshall演算法的原理是動態規劃。
設Di,j,k為從i到j的只以(1..k)集合中的節點為中間節點的最短路徑的長度。
若最短路徑經過點k，則Di,j,k = Di,k,k − 1 + Dk,j,k − 1；
若最短路徑不經過點k，則Di,j,k = Di,j,k − 1。
因此，Di,j,k = min(Di,k,k − 1 + Dk,j,k − 1,Di,j,k − 1)。（而我們是求最長，所以應該換成max就可以了）
void floyd(int g[M][M],int D[M][M])
{
for(int k = 0;k<M;k++)
for(int i = 0;i<M;i++)
{
for(int j = 0;j<M;j++)
{
if(k == 0)//k=0，第一輪循環時，先將基礎值賦值給D數組
{
if(g[i][j]!=null)
D[i][j] =g[i][j];
else
{
g[i][j]=-30000;//在k=0的第一輪循環中，讓沒有路徑的地方等於一個大的負數，這樣之後的比較就不需要重復的判斷非空了
D[i][j]=-30000;
}}
else//當k不等於0時，也就是第二輪循環之後,進行最長路徑的比較和計算，大的值賦值給D數組
{
D[i][j] = MAX(D[i][j],D[i][k]+D[k][j]);
}
}
}
}
最後再寫個循環，取出數組D中的最大值就可以得到最大路程瞭然後再算最大路費，如果前面的演算法沒錯的話。
我的感覺的話，Floyd-Warshall演算法比較容易實現，不需要特殊的數據結構，就是可能演算法的時間和空間復雜度比較高，不知道你怎麼看
⑷ 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");
}
自己寫的,三個閉包都有,包括傳遞閉包,看注釋就知道了,還是用文件讀寫,方便數據輸入
⑸ C語言可以用於模擬隨機的行進路線嗎
我們分析一下你的問題：不同隨機點隨機進出門口。
1、分析：機場的門口是固定的，進出門口的是人或者車輛，那麼存在隨機性的就是人或者車。因此，變數就可以設置為一個，代表移動的物體。
2、第一，假設用X表示移動物體，這個可以列出可能的物體集合，然後使用隨機演算法抽取其中一個；
3、第二，使用Floyd演算法。Floyd-Warshall演算法（Floyd-Warshall algorithm）是解決任意兩點間的最短路徑的一種演算法，可以正確處理有向圖或負權的最短路徑問題，同時也被用於計算有向圖的傳遞閉包。
總結一下：
這個設計使用了隨機主體（人或者車）的隨機抽取，而移動隨機使用的是Floyd。
⑹ 數據結構-圖的鄰接表表示（C語言）
//grap_theory.cpp:定義控制台應用程序的入口點。
//
//#include"stdafx.h"//VS2010頭文件
#include<stdio.h>
#defineNTOTAL(26*4)//最大路徑數目
#defineMAX_DISTANCE10000.0
structpiont{
intline_adjacency_list;
intnum_piont;
inttest_num[2];
charfrom[NTOTAL];
charto[NTOTAL];
charall_piont[NTOTAL];
intall_piont_num[NTOTAL];
floatdistance[NTOTAL];
floatdistance_all[NTOTAL][NTOTAL];
};//結構體定義
voidread(piont*test){
inti;
chartemp[100];
scanf("%d",&test->line_adjacency_list);//讀取行數
gets(temp);//讀取回車字元
for(i=0;i<test->line_adjacency_list;i++){//讀取列表
scanf("%c%c%f",&test->from[i],&test->to[i],&test->distance[i]);
gets(temp);//讀取回車字元
}
scanf("%c%c",&test->from[i],&test->to[i]);//讀取短短路徑名稱
}
voidcal_num_piont(piont*test){
inti,j;
intfrom_num,to_num;
test->num_piont=0;
for(i=0;i<NTOTAL;i++){
test->all_piont_num[i]=0;//點的度數清零
test->distance_all[i][i]=0.0;
for(j=i+1;j<NTOTAL;j++){
test->distance_all[i][j]=MAX_DISTANCE;
test->distance_all[j][i]=MAX_DISTANCE;
}
}
for(i=0;i<test->line_adjacency_list;i++){
//判斷from
for(j=0;j<test->num_piont;j++){
if(test->from[i]==test->all_piont[j]){
from_num=j;
test->all_piont_num[j]++;
break;
}
}
if(j==test->num_piont){
test->all_piont[j]=test->from[i];
from_num=j;
test->all_piont_num[j]++;
test->num_piont++;
}
//判斷end
for(j=0;j<test->num_piont;j++){
if(test->to[i]==test->all_piont[j]){
to_num=j;
test->all_piont_num[j]++;
break;
}
}
if(j==test->num_piont){
test->all_piont[j]=test->to[i];
to_num=j;
test->all_piont_num[j]++;
test->num_piont++;
}
test->distance_all[from_num][to_num]=test->distance[i];
test->distance_all[to_num][from_num]=test->distance[i];
}
//判斷所求點的位置
for(i=0;i<test->num_piont;i++){
if(test->from[test->line_adjacency_list]==test->all_piont[i])
test->test_num[0]=i;
if(test->to[test->line_adjacency_list]==test->all_piont[i])
test->test_num[1]=i;
}
}
floatmin_distance(piont*test){
inti,j,k,n;
floatmin_dis;
floatdis_i_k_add_k_j;
n=test->num_piont;
//Floyd-Warshall演算法
for(k=0;k<n;k++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
dis_i_k_add_k_j=(test->distance_all[i][k]+test->distance_all[k][j]);
if(test->distance_all[i][j]>dis_i_k_add_k_j)
test->distance_all[i][j]=dis_i_k_add_k_j;
}
}
}
min_dis=test->distance_all[test->test_num[0]][test->test_num[1]];
returnmin_dis;
}
voidtest_printf(piont*test,floatmin_dis){
inti;
printf("%d ",test->num_piont);
for(i=0;i<test->num_piont;i++){
printf("%d ",test->all_piont_num[i]);
}
printf("%-8.0f ",min_dis);
}
voidmain()
{
floatmin_dis;
pionttest1;//結構體聲明
read(&test1);
cal_num_piont(&test1);
min_dis=min_distance(&test1);
test_printf(&test1,min_dis);
}
⑺ 離散數學Warshall演算法求傳遞閉包C語言實現
#include <stdio.h>#include <stdlib.h>#define N 20#define M 20main(){ 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＂)；}自己寫的，三個閉包都有，包括傳遞閉包，看注釋就知道了，還是用文件讀寫，方便數據輸入
⑻ 如何在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則為連通圖
⑼ C語言編程floyd法求助
for(i=0;i<n;i++){//輸出每對頂點間最短路徑長度及最短路徑
for(j=0;j<n;j++){
printf("%d到%d的最短長度:",i+1,j+1);
printf("%d\t",D[i][j]);//輸出Vi到Vj的最短路徑長度
printf("\n");
}
}
修改這里的就好了。不要全部輸出。
你可以定義一個變數 來累加 D[I][J]初步想法
int minzise = 0;
for(i=0;i<n;i++){//輸出每對頂點間最短路徑長度及最短路徑
for(j=0;j<n;j++){
minzise+= D[i][j];//
}
}
printf(「%d」),minzise)//符合你要求嗎？
⑽ Warshall演算法的演算法介紹
1、引言
Warshall在1962年提出了一個求關系的傳遞閉包的有效演算法。其具體過程如下，設在n個元素的有限集上關系R的關系矩陣為M：
（1）置新矩陣A=M;
（2）置k=1;
（3）對所有i如果A[i,k]=1，則對j=1..n執行：
A[i,j]←A[i,j]∨A[k,j];
（4）k增1;
（5）如果k≤n，則轉到步驟（3），否則停止。
所得的矩陣A即為關系R的傳遞閉包t(R)的關系矩陣。
在左孝凌等編著的《離散數學》中提到了該演算法，但並未對此演算法作出解釋。下面本文將對該演算法的思想作出一種比較通俗的解說。
2、對Warshall演算法的解說
設關系R的關系圖為G，設圖G的所有頂點為v1,v2,…,vn，則t(R)的關系圖可用該方法得到：若G中任意兩頂點vi和vj之間有一條路徑且沒有vi到vj的弧，則在圖G中增加一條從vi到vj的弧，將這樣改造後的圖記為G』，則G』即為t(R)的關系圖。G』的鄰接矩陣A應滿足：若圖G中存在從vi到vj路徑，即vi與vj連通，則A[i,j]=1，否則A[i,j]=0。
這樣，求t(R)的問題就變為求圖G中每一對頂點間是否連通的問題。
定義一個n階方陣序列A(0),A(1),A(2),…,A(n)，每個方陣中的元素值只能取0或1。A(m)[i,j]=1表示存在從vi到vj且中間頂點序號不大於m的路徑（m=1..n），A(m)[i,j]=0表示不存在這樣的路徑。而A(0)[i,j]=1表示存在從vi到vj的弧，A(0)[i,j]=0表示不存在從vi到vj的弧。
這樣，A(n)[i,j]=1表示vi與vj連通，A(n)[i,j]=0表示vi與vj不連通。故A(n)即為t(R)的關系矩陣。
那麼應如何計算方陣序列A(0),A(1),A(2),…,A(n)呢？
很顯然，A(0)=M（M為R的關系矩陣）。
若A(0)[i,1]=1且A(0)[1,j]=1，或A(0)[i,j]=1，當且僅當存在從vi到vj且中間頂點序號不大於1的路徑，此時應將A(1)[i,j]置為1，否則置為0。
一般地，若A(k-1)[i,k]=1且A(k-1)[k,j]=1，或A(k-1)[i,j]=1，當且僅當存在從vi到vj且中間頂點序號不大於k的路徑，此時應將A(k)[i,j]置為1，否則置為0（k=1..n）。用公式表示即為：
A (k)[i,j]=(A(k-1)[i,k]∧A(k-1)[k,j])∨A(k-1)[i,j] i,j,k=1..n
這樣，就可得計算A(k)的方法：先將A(k)賦為A(k-1)；再對所有i=1..n，若A(k)[i,k]=1（即A(k-1)[i,k]=1），則對所有j=1..n，執行：
A (k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]
但這與前述Warshall演算法中的第（3）步還有一定距離。若將上式改為：
A(k)[i,j]←A(k)[i,j]∨A(k)[k,j] （即把A(k-1)[k,j]改為A(k)[k,j]）
就可將上標k去掉，式子就可進一步變為：
A[i,j]←A[i,j]∨A[k,j]
這樣可以只用存儲一個n階方陣的空間完成計算，且與前述Warshall演算法中第（3）步的式子一致。那麼，可不可以把A(k-1)[k,j]改為A(k)[k,j]呢？答案是肯定的。下面將證明在計算A(k)的過程中A(k-1)[k,j]與A(k)[k,j]相等（A(k)被賦初值A(k-1)後）。考察計算A(k)的方法 只有當i=k時A(k)[k,j]的值才有可能改變，此時將式A(k)[i,j]←A(k)[i,j]∨A(k-1)[k,j]中的i換為k，得A(k)[k,j]←A(k)[k,j]∨A(k-1)[k,j]，對某一j，執行該式的賦值操作前A(k)[k,j]=A(k-1)[k,j]，因為計算A(k)開始時A(k)被賦為A(k-1)，故它們相或的結果等於A(k-1)[k,j]，故賦值操作不改變A(k)[k,j]的值。這樣，就沒有操作會改變A(k)[k,j]的值，故A(k-1)[k,j]與A(k)[k,j]相等。
綜上，就可得到計算A(n)的演算法，且該演算法與前述的Warshall演算法完全一致。
由上面的分析，不難看出，Warshall演算法類似於求圖中每對頂點間最短路徑的Floyd演算法。其實，用Floyd演算法也能求關系的傳遞閉包，方法為令關系R的關系圖G中的每條弧的權值都為1，這樣得一有向網G1，設G1的鄰接矩陣為D(-1)（若vi無自迴路，則D(-1)(i,i)=∞），對G1用Floyd演算法求其每對頂點間最短路徑，得結果矩陣D(n-1)。因若G中vi與vj連通，當且僅當D(n-1)[i,j]≠∞，故將矩陣D中的∞都改為0，其它值都改為1，得矩陣A，則矩陣A即為t(R)的關系矩陣。Floyd演算法和Warshall演算法的時間復雜度都為O(n3)，但明顯用Floyd演算法求關系的傳遞閉包繞了彎子。
參考文獻：
[1]左孝凌，李為鑒，劉永才，《離散數學》，上海：上海科學技術文獻出版社，1982
[2]嚴蔚敏，吳偉民，《數據結構 C語言版》，北京：清華大學出版社，1997