本文共 2715 字,大约阅读时间需要 9 分钟。
转载:
在一張無向圖上面,給定圖上一點,以最短路徑長度當作距離,找出離此點最遠的一點,這兩點之間的距離就叫做「偏心距」。
要計算一張無向圖的直徑與半徑是很簡單的,首先算好所有兩點之間最短路徑,然後按照定義來算就可以了。
先用floyd算法,再找最长的即可
树形图的最长路径(边无权重)
方法1:
一棵無根樹的「直徑」,就是相離最遠的兩個點的距離。
稍微修改一下計算高度的程式碼,就可以順便計算直徑。
一棵樹的各種直徑一定會相交在同一點(同一群點)。
1.反證法。現在有兩條分開的直徑,可是一棵樹上各點都得連通,所以這兩條分開的直徑,中間一定有某處互相連接,一旦連接起來,勢必變成更長的直徑,矛盾。故所有直徑必相交。2.反證法。現在已有兩條直徑相交在某一點,如果另外一條直徑與這兩條直徑相交在另一點,勢必變成更長的直徑,矛盾。故所有直徑必相交在同一點(同一群點)。
方法二:
在一个迷宫中找距离最长的两个点。迷宫可以看作是一个无根树,因此,这个问题等价与在一个树形图中找最远的两个节点,也叫做这个图的直径。
迷宫、树形图有个很好的特点:任意两个节点之间的距离就是这两点之间的最短路径、也是两个节点的最长路径,也可以说任意两个节点之间的距离一定。基于这个想法,可以很快想到:穷举每个点对,计算其距离,取最大值,即可。这个计算量比较大,思想上可行,实践起来,时间代价有点不靠谱。查了下,已经有好的解决方案了:
1 取任意节点作为起点,找出到该点最远的点,记为A;
2 以点A为起点,找出到该点最远的点,记为B;
AB之间的距离,就是图中距离最远的两个点的距离(这样的点对可能有多个,但最大距离值只有一个)。
因此,两次dfs即可搞定。也可以用bfs
代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int m,n;
int f[4][2] = {
{0,1},{1,0},{0,-1},{-1,0}};char map[1002][1002];
bool flag[1002][1002];
int max,step,maxM,maxN;
int si,sj;
void dfs(int i,int j)
{
int ii,a,b;
for(ii=0;ii<4;ii++)
{
a = i+ f[ii][0];
b = j+ f[ii][1];
if(a>=0 && a<m && b>=0 && b<n && map[a][b]=='.' && flag[a][b])
{
step++;
flag[a][b] = false;
if(max < step)
{
max = step;
maxM = a;
maxN = b;
}
dfs(a,b);
flag[a][b] = true;
step--;
}
}
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
si = -1;
for(i=0;i<m;i++)
{
scanf("%s",map[i]);
if(si==-1)
for(j=0;j<n;j++)
if(map[i][j]=='.')
{
si = i;
sj = j;
break;;
}
}
memset(flag, true, sizeof(flag));
flag[si][sj] = false;
max = 0;
step = 0;
dfs(si,sj);
memset(flag, true, sizeof(flag));
flag[maxM][maxN] = false;
max = 0;
step = 0;
dfs(maxM, maxN);
printf("Maximum rope length is %d.\n",max);
}
system("pause");
return 0;
}
如果边有权重的话,感觉着两个算法也能正常工作