⑴ 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