# 深度优先搜索

#include "stdafx.h" #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]; 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]; } }; 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 *temp =g->adj[start]; while(temp->next) { temp=temp->next; } temp->next=v; return true; }   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; 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[vertex]=BLACK; g->f[vertex]=v_time++; } 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 _tmain(int argc, _TCHAR* argv[]) { Graph *g =new Graph(); init(g); DepthFirstSearch(g,1); return 0; }