作业帮无向图 n个点 n-1条边 以及两点的距离 打出map二维数组（任意两点间的距离）问题补充：要程序和思想一个深搜填表不过楼主给的条件很诡异,N个点,N个点最多可以有N*（N-1）/2条边.如果楼主
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/25 21:27:23
无向图 n个点 n-1条边 以及两点的距离 打出map二维数组（任意两点间的距离）问题补充：要程序和思想一个深搜填表不过楼主给的条件很诡异,N个点,N个点最多可以有N*（N-1）/2条边.如果楼主
无向图 n个点 n-1条边 以及两点的距离 打出map二维数组（任意两点间的距离）问题补充：要程序和思想
一个深搜填表
不过楼主给的条件很诡异,N个点,N个点最多可以有N*（N-1）/2条边.如果楼主是一个点一个点像链子那样连下去的话,完全没必要二维数组,一维数组或链表就行了.因为那就是条链子,算不上图
n个点给你n-1条边（任意二点只有一条途径）问任意两点的距离
无向图 n个点 n-1条边 以及两点的距离 打出map二维数组（任意两点间的距离）问题补充：要程序和思想一个深搜填表不过楼主给的条件很诡异,N个点,N个点最多可以有N*（N-1）/2条边.如果楼主
重新理解下你可能的题意：
1：你的意思可能就是1个点连一个点,自然是n个点n-1条边.这样你建个数组D
D[i]代表第i个点和第i+1个点之间距离,则第i点和第j点之间距离distance(i,j)=D[i]+D[i+1]+...+D[j-1],但是感觉你这题可能不是这意思
2：即这确实是一个有n个点的无向图.但是里面只有n-1个连接.同样用n*n二维数组D表示这个图
P1 P2 P3 .Pn
P1 0 D12 D13 .D1n
P2 D12 0 D23 .D2n
P3 D13 D23 0 .D3n
................
Pn D1n D2n D3n .0
这数组的元素D[i][j]表示第i点和第j点的距离.特别的当i=j时,显然距离为0.当i和j不相连时为-1,否则距离应该大于0
根据上图,楼主应该很容易看出这数组表示的n*n矩阵式对称的.所以其实楼主只要关注左上角或右下角就行了.我们来关注左上角.根据题意,左上角这n*(n-1)/2个元素中有n-1个元素是大于0的,即相连,剩下的那n*(n-1)/2-(n-1)=(n-1)(n-2)/2个元素为-1,即不相连.楼主你只要考虑相连的那n-1个边.根据数学推导,这n-1条边可以保证n个点中任意2点必定有路径相连且路径唯一.至于如何推导楼主就不必知道了~.
现在假设要求求第i个点和第j个点直接距离
给你个递归算法
float distance(int i,int j)
{
float fResult;
if D[i][j]>0 //如果i和j相连
return D[i][j]; //直接返回i和j之间距离
else //否则
{
for(int k=0; k0 //如果i和其他某个点相连
fResult=distance(k,j); //判断这个点与j的距离
if (fResult >= 0) //如果这个点与j相连
{
fResult+=D[i][k]; //那么将i与k的距离加上k与j的距离相加就是所需的i于j的距离
break; //因为得到结果,所以跳出循环
}
else //否则
fResult=-1; //将结果设为-1,并且继续循环
}
return fResult; //返回结果.如果fResult=-1,那么显然i与j不相连,否则应为一个大于0的数
}
}
111111
可以选择用floyd