アルゴリズム導論-2.2-7-ツリーの直径

一、テーマ
ツリーT=(V,E)の直径(diameter)はmax(u,v)と定義され、すなわち、ツリーの直径は、ツリー内のすべての最短パス長の最大値である.ツリーの直径を計算する有効なアルゴリズムを書き出し,アルゴリズムの実行時間を解析した.
二、考える
Step 1:ツリー内の任意のノードをソースポイントとし、広さ優先遍歴を行い、ソースポイントから最も遠い点dを見つける
Step 2:dをソース点とし,広さ優先遍歴を行い,dから最も遠い点を探し出し,その長さを記録する
三、コード

//          
#include <iostream>
#include <queue>
using namespace std;

#define N 8
#define WHITE 0
#define GRAY 1


//     
struct Edge
{
	int start;//      
	int end;//      
	Edge *next;//            
	Edge(int s, int e):start(s),end(e),next(NULL){}
};
//      
struct Vertex
{
	Edge *head;//              
	bool color;//  ，          
	Vertex *p;//          
	int d;//        
	Vertex():head(NULL),color(WHITE),p(NULL),d(0x7fffffff){}
};
//   
struct Graph
{
	Vertex *V[N+1];//N   
	Graph()
	{
		int i;
		for(i = 1; i <= N; i++)
			V[i] = new Vertex;
	}
	~Graph()
	{
		int i;
		for(i = 1; i <= N; i++)
			delete V[i];
	}
};

//        STL       
queue<Vertex*> Q;

//   
void InsertEdge(Graph *G, Edge *E)
{
	//          
	if(G->V[E->start]->head == NULL)
		G->V[E->start]->head =E;
	//   ，      ，      ，    
	else
	{
		//     ，   
		Edge *e1 = G->V[E->start]->head, *e2 = e1;
		while(e1 && e1->end < E->end)
		{
			e2 = e1;
			e1 = e1->next;
		}
		if(e1 && e1->end == E->end)
			return;
		if(e1 == e2)
		{
			E->next = e1;
			G->V[E->start]->head =E;
		}
		else
		{
			e2->next = E;
			E->next = e1;
		}
	}
}
//          ，              
void BFS(Graph *G, Vertex *s, int &ls, int &lv)
{
	int i;
	//                 ，            ，         
	for(i = 1; i <= N; i++)
	{
		G->V[i]->color = WHITE;
		G->V[i]->d = 0x7fffffff;
		G->V[i]->p = NULL;
	}
	// s        
	s->color = GRAY;
	s->d = 0;
	s->p = NULL;
	//     ，       s
	while(!Q.empty())
		Q.pop();
	Q.push(s);
	//           ，         
	while(!Q.empty())
	{
		//           u，        
		Vertex *u = Q.front();
		Q.pop();
		//  u           v
		Edge *e = u->head;
		while(e)
		{
			Vertex *v = G->V[e->end];
			//  v    ，          
			if(v->color == WHITE)
			{
				//    
				v->color = GRAY;
				//    
				v->d = u->d + 1;
				if(v->d > ls)
				{
					ls = v->d;
					lv = v->id;
				}
				//u          
				v->p = u;
				//         
				Q.push(v);
			}
			e = e->next;
		}
		// u               ，u     （       ，      ）
		u->color = GRAY;
	}
}
//  
void Print(Graph *G)
{
	int i;
	//      
	for(i = 1; i <= N; i++)
	{
		cout<<i<<':';
		//   i        
		Edge *e = G->V[i]->head;
		while(e)
		{
			cout<<e->end<<' ';
			e = e->next;
		}
		cout<<endl;
	}
	cout<<endl;
}
/*
1 2
1 4
4 2
2 5
5 4
3 6
3 5
6 6
*/
/*
1 2
1 5
2 6
6 3
7 6
3 7
3 4
4 8
7 8
7 4
*/
int main()
{
	//       
	Graph *G = new Graph;
	Edge *E;
	Print(G);
	//   
	int i, start, end;
	for(i = 1; i <= 10; i++)
	{
		cin>>start>>end;
		E = new Edge(start, end);
		InsertEdge(G, E);
		//   ，     
		E = new Edge(end, start);
		InsertEdge(G, E);
	}
	Print(G);
	int ls = -1, lv;
	//     ，       ，      lv，lv             
	BFS(G, G->V[1], ls, lv);
	ls = -1;
	//     ， lv  ，       
	BFS(G, G->V[lv], ls, lv);
	cout<<ls<<endl;
	return 0;
}