无向图 n个点 n-1条边以及两点的距离打出map二维数组（任意两点间的距离）问题补充：要程序和思想

来源：学生作业帮编辑：神马作文网作业帮分类：综合作业时间：2024/11/12 16:37:03

无向图 n个点 n-1条边以及两点的距离打出map二维数组（任意两点间的距离）问题补充：要程序和思想
一个深搜填表
不过楼主给的条件很诡异,N个点,N个点最多可以有N*（N-1）/2条边.如果楼主是一个点一个点像链子那样连下去的话,完全没必要二维数组,一维数组或链表就行了.因为那就是条链子,算不上图
n个点给你n-1条边（任意二点只有一条途径）问任意两点的距离

重新理解下你可能的题意：
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的数
}
}

数轴上的两点M，N分别表示-5和-2，那么M，N两点间的距离是（　　）已知两点M(0,2),N(0,-2)且点P到这两点的距离的和等于6. 平面上有P,Q两点距离为9厘米,点M是平面内的任意一点,请回答（在问题补充里面） 1、在边长为1的正方形内,任意给定n个点,如果其中总有两点之间的距离不大于二分之根号二,那么n的最小值为( & 在边长为1的正方形内,任意给定N个点,如果其中总有两点之间的距离不大于二分之根号二,那么N的最小值为如图,点M,N是线段AB上任意两点,且AB=10cm,图中所有线段的和等于35cm,则点M,N之间的距离是_____cm 若数轴上M、N两点之间的距离为2010（m在n左侧）m,n两点折叠点为0.5,折叠后M和N互相重合,m,n两已知点P(m,3)与点Q(1,-n)关于原点对称,求P,Q两点间的距离设在区间(0,1)上随机地取n个点,求相距最远的两点间的距离的数学期望. 已知两点M(1,2),N(x,-2)之间的距离等于5,求点N的坐标圆曲线计算已知圆曲线两点之间直线距离和半径,求出两点间直线到弧线任意点的垂直距离.求公式和解说. 在已知n个点三维坐标的情况下,求每两点之间的距离.用matlab.

无向图 n个点 n-1条边 以及两点的距离 打出map二维数组（任意两点间的距离）问题补充：要程序和思想

无向图 n个点 n-1条边以及两点的距离打出map二维数组（任意两点间的距离）问题补充：要程序和思想