【算法导论】22.2-7 树的直径问题

树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；
原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了

所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度

代码如下：

#include <iostream>#include <vector>#include <queue>using namespace std;#define  N 7#define INFINITE 0x7fffffff#define WHITE 1#define GRAY 2#define BLACK 3//顶点结点结构  struct Vertex  {  Vertex * next;/*指向下一个顶点*/int id;/*节点的标志*/    int color;//颜色      Vertex *p;//指向遍历结果的父结点      int d;//与源点之间的距离      Vertex():next(NULL),id(0),color(WHITE),p(NULL),d(INFINITE){}  };  //图结构struct Graph{Vertex *Adj[N+1];//N个顶点Graph(){         for(int i = 1; i <= N; i++)              Adj[i] = new Vertex;  }~Graph()      {          for(int i = 1; i <= N; i++)              delete Adj[i];      }  };std::queue<int>Q;/*队列，保存搜索过程的中间数据*/int c_node;/*当前遍历的节点*/void Print(Graph *g);bool Init(Graph *g);bool InsertEdge(Graph *g , int start,int end);void PaintColor(Graph *g,int vertex,int color);//插入边bool InsertEdge(Graph *g , int start,int end){Vertex* v = new Vertex();v->id = end;if(g->Adj[start]->next == NULL){/*如果不存在临界表的头结点列表中，则插入*/Vertex* s = new Vertex();s->id = start;g->Adj[start] = s;}Vertex* tmp = g->Adj[start];while(tmp->next){tmp = tmp->next;}tmp->next =v;return true;}/*初始化邻接表表示树，无向图。 1/ \   2   3  /\   /\ 4 5  6  7*/bool Init(Graph *g){InsertEdge(g,1,2);InsertEdge(g,2,1);InsertEdge(g,1,3);InsertEdge(g,3,1);InsertEdge(g,2,4);InsertEdge(g,4,2);InsertEdge(g,2,5);InsertEdge(g,5,2);InsertEdge(g,3,6);InsertEdge(g,6,3);InsertEdge(g,3,7);InsertEdge(g,7,3);return true;}/*宽度优先搜索，vertex为初试的节点这种方法适合于无向图，如果是有向图会产生死循环*/bool BreadFirstSearch(Graph *g,int vertex){ //对所有结点进行初始化        for(int i = 1; i <= N; i++)        {            //g->Adj[i]->color = WHITE;            g->Adj[i]->d = INFINITE;            g->Adj[i]->p = NULL;    PaintColor(g,i,WHITE);    } PaintColor(g,vertex,GRAY);    g->Adj[vertex]->d = 0;      g->Adj[vertex]->p = NULL;      while(!Q.empty())      {          Q.pop();    }  Q.push(vertex);    while(!Q.empty())      {  /*应该存储节点的ID，不应该是数据结构，可以节省存储空间*/        int node = Q.front();c_node = node;Vertex *v = g->Adj[node]; //Q.front();          Q.pop();          std::cout<<v->id<<"\t";  while(v){if(v->color == WHITE){PaintColor(g,v->id,GRAY);g->Adj[v->id]->d = g->Adj[node]->d +1;Q.push(v->id);}v = v->next;}PaintColor(g,node,BLACK);    }      return true;  }/*对临界表的节点染色*/void PaintColor(Graph *g,int vertex,int color){g->Adj[vertex]->color = color;for(int i=1;i<=N;i++){Vertex *v = g->Adj[i];v = v->next;while(v){if(v->id == vertex){v->color = color;}v = v->next;}}}/*显示结果1       2       3       4       5       6       77       3       1       6       2       4       54*/int main(int argc,char *argv[]){//构造一个空的图Graph *g = new Graph;Init(g);BreadFirstSearch(g,1);std::cout<<std::endl;BreadFirstSearch(g,c_node);std::cout<<std::endl;/*最后的节点的深度即树的最大直径*/std::cout<<g->Adj[c_node]->d<<std::endl;getchar();return 0;}