樹的直徑是指樹的最長簡單路。求法: 兩遍BFS :先任選一個(gè)起點(diǎn)BFS找到最長路的終點(diǎn)，再從終點(diǎn)進(jìn)行BFS，則第二次BFS找到的最長路即為樹的直徑；
原理: 設(shè)起點(diǎn)為u,第一次BFS找到的終點(diǎn)v一定是樹的直徑的一個(gè)端點(diǎn)
證明: 1) 如果u 是直徑上的點(diǎn)，則v顯然是直徑的終點(diǎn)(因?yàn)槿绻鹶不是的話，則必定存在另一個(gè)點(diǎn)w使得u到w的距離更長，則于BFS找到了v矛盾)
2) 如果u不是直徑上的點(diǎn)，則u到v必然于樹的直徑相交(反證),那么交點(diǎn)到v 必然就是直徑的后半段了
所以v一定是直徑的一個(gè)端點(diǎn)，所以從v進(jìn)行BFS得到的一定是直徑長度
相關(guān)題目有TOJ1056，TOJ3517.
TOJ 1056(Labyrinth):
大意是一個(gè)由‘#’和'.'構(gòu)成的迷宮，'.'表示可行，‘#’表示不可行，問可行的最長的路的長度是多少。
#include <cstdio>
#include <cstring>
#include <queue>
#define M 1002
using namespace std;
int r,c;
char map[M][M];
bool flag[M][M];
int move[4][2]={-1,0,1,0,0,-1,0,1}; // 分別表示上下左右
int maxt;
struct Node{
int x,y,num;
};
Node ans;
bool legal(int x,int y){ //判斷該點(diǎn)是否越界及是否可走
if(x >=0 && x < r && y>=0 && y < c &&map[x][y]=='.') return true;
return false;
}
void bfs(Node start){
memset(flag,false,sizeof(flag)); //初始所有點(diǎn)標(biāo)記為false
flag[start.x][start.y] = true; //起點(diǎn)標(biāo)記為true
queue<Node>f;
while(!f.empty()) f.pop(); //清空創(chuàng)建的隊(duì)列
Node m,n,tep;
int tx,ty,xx,yy;
int i,j,k,num;
f.push(start);
while(!f.empty()){ //如果隊(duì)列不為空
m = f.front(); //取出隊(duì)首元素
tx = m.x; ty = m.y; num = m.num;
if(num > maxt){ //如果該元素的長度大于maxt，更新maxt
maxt = num;
ans = m;
}
for(i = 0;i < 4; i++){ //以m為起點(diǎn)向4個(gè)方向BFS
xx = tx + move[i][0];
yy = ty + move[i][1];
if(!flag[xx][yy] && legal(xx,yy)){
flag[xx][yy] = true;
tep.x = xx;
tep.y = yy;
tep.num = num + 1;
f.push(tep);
if(num+1>maxt){ //如果有更大的則更新
maxt = num + 1;
ans = tep;
}
}
}
f.pop(); //彈出隊(duì)首元素
}
}
int main(){
int i,j,T;
Node start,end;
bool mark;
scanf("%d",&T);
while(T--){
scanf("%d%d",&c,&r);
mark = false; maxt = -1;
for(i = 0;i < r; i++)
scanf("%s",map[i]);
for(i = 0;i < r; i++){
for(j = 0;j < c; j++){
if(map[i][j]=='.'){ //任選一點(diǎn)BFS
start.x = i;
start.y = j;
start.num = 0;
bfs(start);
mark = true;
break;
}
}
if(mark) break;
}
maxt = -1;ans.num = 0; //此時(shí)ans一定是直徑的端點(diǎn)，將它設(shè)為起點(diǎn)
bfs(ans); //進(jìn)行第二次BFS
printf("Maximum rope length is %d.\n",maxt);
}
}
TOJ3517(The longest athletic track):
題目給出了一棵生成樹，問這棵生成樹最長的路的長度是多少。
#include<iostream>
#include<queue>
#define INF 999999
#define M 2002
using namespace std;
int n;
int maxx;
int map[M][M],sum[M];
bool flag[M];
int bfs(int begin){
queue<int>f;
int i,m,k,key;
maxx=0;
memset(flag,false,sizeof(flag));
f.push(begin);
while(!f.empty()){
k=f.front();
for(i=1;i<=n;i++){
if(map[k][i]!=INF&&!flag[i]){
flag[i]=true;
f.push(i);
sum[i]=sum[k]+map[k][i];
if(sum[i]>maxx) { maxx=sum[i];key=i; }
}
}
f.pop();
}
return key;
}
int main()
{
int i,j,k,dis,key,cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
map[i][j]=map[j][i]=INF;
for(i=1;i<n;i++){
scanf("%d%d%d",&j,&k,&dis);
map[j][k]=map[k][j]=dis;
}
sum[1]=0;
key=bfs(1);
sum[key]=0;
key=bfs(key);
printf("%d\n",maxx);
}
//system("pause");
}