无向图的直径以及树的直径
轉(zhuǎn)載：http://www.csie.ntnu.edu.tw/~u91029/Path3.html
在一張無向圖上面，給定圖上一點(diǎn)，以最短路徑長(zhǎng)度當(dāng)作距離，找出離此點(diǎn)最遠(yuǎn)的一點(diǎn)，這兩點(diǎn)之間的距離就叫做「偏心距」。
要計(jì)算一張無向圖的直徑與半徑是很簡(jiǎn)單的，首先算好所有兩點(diǎn)之間最短路徑，然後按照定義來算就可以了。
先用floyd算法，再找最長(zhǎng)的即可
樹形圖的最長(zhǎng)路徑（邊無權(quán)重）
方法1：
一棵無根樹的「直徑」，就是相離最遠(yuǎn)的兩個(gè)點(diǎn)的距離。
稍微修改一下計(jì)算高度的程式碼，就可以順便計(jì)算直徑。
樹的直徑，邊無權(quán)重（adjacency matrix）一棵樹的各種直徑一定會(huì)相交在同一點(diǎn)（同一群點(diǎn)）。
1. 反證法。 現(xiàn)在有兩條分開的直徑， 可是一棵樹上各點(diǎn)都得連通， 所以這兩條分開的直徑，中間一定有某處互相連接， 一旦連接起來，勢(shì)必變成更長(zhǎng)的直徑，矛盾。 故所有直徑必相交。2. 反證法。 現(xiàn)在已有兩條直徑相交在某一點(diǎn)， 如果另外一條直徑與這兩條直徑相交在另一點(diǎn)， 勢(shì)必變成更長(zhǎng)的直徑，矛盾。 故所有直徑必相交在同一點(diǎn)（同一群點(diǎn)）。方法二：
在一個(gè)迷宮中找距離最長(zhǎng)的兩個(gè)點(diǎn)。迷宮可以看作是一個(gè)無根樹，因此，這個(gè)問題等價(jià)與在一個(gè)樹形圖中找最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)，也叫做這個(gè)圖的直徑。
迷宮、樹形圖有個(gè)很好的特點(diǎn)：任意兩個(gè)節(jié)點(diǎn)之間的距離就是這兩點(diǎn)之間的最短路徑、也是兩個(gè)節(jié)點(diǎn)的最長(zhǎng)路徑，也可以說任意兩個(gè)節(jié)點(diǎn)之間的距離一定。基于這個(gè)想法，可以很快想到：窮舉每個(gè)點(diǎn)對(duì)，計(jì)算其距離，取最大值，即可。這個(gè)計(jì)算量比較大，思想上可行，實(shí)踐起來，時(shí)間代價(jià)有點(diǎn)不靠譜。查了下，已經(jīng)有好的解決方案了：
1 取任意節(jié)點(diǎn)作為起點(diǎn)，找出到該點(diǎn)最遠(yuǎn)的點(diǎn)，記為A；
2 以點(diǎn)A為起點(diǎn)，找出到該點(diǎn)最遠(yuǎn)的點(diǎn)，記為B；
AB之間的距離，就是圖中距離最遠(yuǎn)的兩個(gè)點(diǎn)的距離（這樣的點(diǎn)對(duì)可能有多個(gè)，但最大距離值只有一個(gè)）。
因此，兩次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;
}
如果邊有權(quán)重的話，感覺著兩個(gè)算法也能正常工作
總結(jié)
以上是生活随笔為你收集整理的无向图的直径以及树的直径的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
