【算法导论】22.3 图的深度优先搜索-C++实现
本程序是用邻接表表示的图的深度优先搜索，为算法导论22.3伪代码的C++实现。
对于有向图可以得到正确的结果，对于无向图貌似也可以得到遍历结果，代码如下：
#include <iostream>using namespace std;#define N 6#define INFINITE 0x7fffffff#define WHITE 1#define GRAY 2#define BLACK 3//顶点结点结构 struct Vertex { Vertex * next;/*指向下一个顶点*/int id;/*节点的标志*/ Vertex():next(NULL),id(0){} }; //图结构struct Graph{Vertex *Adj[N+1];//N个顶点及邻接点头指针int color[N+1];//颜色 int p[N+1];//指向遍历树节点的父结点 int d[N+1];/*节点发现时间*/int f[N+1];/*节点结束遍历时间*/Graph(){ for(int i = 1; i <= N; i++) { Adj[i] = new Vertex;color[i]=WHITE;d[i] = 0;f[i] = 0;p[i] = 0;}}~Graph() { for(int i = 1; i <= N; i++) delete Adj[i]; } };void Print(Graph *g);bool Init(Graph *g);bool InsertEdge(Graph *g , int start,int end);void PaintColor(Graph *g,int vertex,int color);void DepthFirstVisit(Graph *g,int vertex,int& v_time);//插入边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->42->53->6->54->25->46->6*/bool Init(Graph *g){InsertEdge(g,1,2);InsertEdge(g,1,4);InsertEdge(g,2,5);InsertEdge(g,3,5);InsertEdge(g,3,6);InsertEdge(g,4,2);InsertEdge(g,5,4);InsertEdge(g,6,6);return true;}void DepthFirstVisit(Graph *g,int vertex,int& v_time){g->color[vertex] = GRAY;v_time ++;g->d[vertex] = v_time;Vertex * v = g->Adj[vertex];int node = v->id;std::cout<<node<<"\t";v = v->next;while(v){if(g->color[v->id] == WHITE){g->p[v->id] = vertex;DepthFirstVisit(g,v->id,v_time);}v = v->next;}g->color[node] = BLACK;g->f[node] = v_time++;}/*宽度优先搜索，vertex为初始访问的节点这种方法适合于无向图，如果是有向图会产生死循环*/bool DepthFirstSearch(Graph *g,int vertex){for(int i=1;i<=N;i++){g->color[i] = WHITE;}int time = 0;for(int i=1;i<=N;i++){if(g->color[i] == WHITE){DepthFirstVisit(g,i,time);}}return true;}int main(){//构造一个空的图Graph *g = new Graph;Init(g);DepthFirstSearch(g,1);getchar();return 0;}