寻找树形图中的最长路径

题目：

在一个迷宫中找距离最长的两个点。

 

迷宫可以看作是一个无根树，因此，这个问题等价与在一个树形图中找最远的两个节点，也叫做这个图的直径。

迷宫、树形图有个很好的特点：即任意两个节点之间的距离就是这两点之间的最短路径和最长路径，也可以说任意两个节点之间的距离一定的。

 

其算法为：

 

任选一点u为起点，对树进行BFS遍历，找出离u最远的点v。然后以v为起点，再进行BFS遍历，找出离v最远的点w。则v到w的路径长度即为树的直径。时间复杂度为O(n)。

 

原理：设起点为u，第一次BFS找到的终点v一定是树的直径的一个端点。

证明：

1. 如果u 是直径上的点，则v必然是直径的终点。（因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾）
2. 如果u不是直径上的点，则u到v的路径必然与树的直径相交，设交点为c，那么c到v的路径与直径的后半段重合。所以v一定是直径的一个端点，因此从v进行BFS得到的一定是直径长度。

 

import java.util.LinkedList;
import java.util.Queue;

public class PeopleNet {
	
	private int[] dist = new int[10];
	private int[] last = new int[10];
	
	public People farest(People src) {
		
		for (int i = 0; i < 10; i++) {
			dist[i] = Integer.MAX_VALUE;
			last[i] = -1;
		}
		
		Queue<People> queue = new LinkedList<People>();
		queue.offer(src);
		dist[src.id] = 0;
		
		People temp = null;
		while (!queue.isEmpty()) {
			temp = queue.poll();
			for (People p : temp.friends) {
				if (dist[p.id] == Integer.MAX_VALUE) {
					dist[p.id] = dist[temp.id] + 1;
					last[p.id] = temp.id;
					queue.offer(p);
				}
			}
		}

		return temp;
	}
	
	public void find(People src, People dest) {
		farest(src);
		showPath(dest.id);
	}
	
	public void showPath(int i) {
		if (last[i] == -1) {
			System.out.print(i + " ");
			return;
		}
		
		showPath(last[i]);
		System.out.print(i + " ");
	}
	
	public void getFarest(People p) {
		People v = farest(p);
		People w = farest(v);
	
                System.out.println("the longest path is from " + v.id + " to " + w.id);	
		showPath(w.id);
	}
}

class People {
	int id;
	LinkedList<People> friends;
	
	public People(int id) {
		this.id = id;
		friends = new LinkedList<People>();
	}
}

 

 

原文地址：http://hi.baidu.com/051156/blog/item/6f8c69eed5dfa03e2cf534d5.html