深度优先搜索是这样的，对最近才发现的结点v的所有出发边进行探索，

直到该结点的所有出发边都被发现为止。

例如上面的图，如果是按照以S点为源结点进行深度优先 遍历的话，

相应的访问顺序是：

（根据具体的应用不同，假定是以左访问优先，

而所谓的左优先指的具体是：如上图，当访问到Z结点的时候，

左优先，继续深入访问Y，而把W结点进行暂存起来）

 

S->Z（W相对于Z靠右,Z被压栈）

Z->Y

Y->X

X结点没有出发边，（所谓出发边指的是从当前结点出发指向其他结点的有向边）

故回溯到Y，Y除了访问过的X同样没有出发边；

回溯到Z，Z还有除了Y没被访问过的出发边指向被压进栈的W

故W从栈中弹出，访问W。

W没有出发边，故回溯到Z,Z再回溯到S。

以上描述就是对图从结点S深度优先遍历一次的大致过程。

 

在树中为了更形象的对这个算法进行描述，免不了多加了一些属性在其中。

其中u是图中的一个节点：

u.color：这个是用来描述当前结点u是什么颜色的，WHITE代表的是，u结点没有被访问。

BLACK代表的是，以结点u为前驱的所有结点都已经被访问到了。

而GRAY代表的是，位于二者{WHITE，BLACK}之间，即u被访问过了，但u的子结点并未被全部访问到。

u.father: 这个其实在本篇文章中意义不大，是用于标记结点u的前驱结点在图G 的Adj[]数组中的位序的，

同时也是用于标识G在跑完DFS算法的时候生成的深度优先树的。

u.startTime：结点的这个属性是用来给每个结点盖上时间戳的，

这个属性记载的是u结点第一次被发现的时间（涂上灰色的时候）

u.endTime：同上，不过这个属性记载的是在搜索完成对u结点的邻接链表扫描结束之后的时间，

该时间同样也是，访问从u出发的所有的结点之后，也是u结点被涂成黑色之后的时间。

u.name： 这个是用来记录结点的名称的；

u.firstedge：这个是邻接链表用于指向该结点后面的第一个邻接结点的指针，

通过它可以找到图中与u结点相连接的其他结点。

下面的深度优先搜索算法的伪代码将其发现结点u的时刻记录在属性u.d中，

将其完成对结点u的处理的时刻记录在u.f这一属性中。

因为|V|个结点中只能有一个发现事件和一个完成事件，

所以这些时间戳都是位于[1， 2*|V|]之间的整数。

很显然对于每个结点都有u.d < u.f

结点u在时间u.d之前为WHITE，在介于[u.d, u.f]之间为GRAY

在u.f之后为BLACK。

 

下面的伪代码给出的是基本的深度优先搜索算法。输入图G既可以是有向图

当然也可以是无向图，而变量为一个全局变量，用它来计算对每一个访问结点的时间戳。

 

1 DFS(G) 2     for each vertex u attibute G.V 3            u.color = WHITE 4            u.father = NIL 5      time = 0 6       7     for each vertec u attribute to G.V 8             if u.color  ==  WHITE 9                      DFS-VISIT(G,u)10 11 //code above is the main DFS that the cycle will check12 //each node in Graph G, if the node is unvisited whose color is white13 // DFS will call method:DFS-VISIT and take that node as the source node14 15 DFS-VISIT(G,u)16 time = time+117 18 u.d = time19 20 u.color = GRAY21 22 for each v attribute to G:Adj[u]23   if v.color == WHITE24       v.f = u25       DFS-VISIT(G, v)  //continue to run26 27 u.color = BLACK28 //blacken the node u after its subnodes all visited29 30 time = time +131 32 u.f = time

 

 下面是使用C++代码实现上述的伪代码：

 在这里说明一下，LZ将color属性单独提出来作为Color数组，这个Color数组

其实质上与平时进行图遍历的visited数组所起到的作用是一样的，只不过，在《算法导论 第三版》

中将结点划分为访问与未访问之间，又多出了一个状态：GRAY，就是一个结点虽然被访问，

但是与它相连接的结点还没有全部被访问，这种情况下，将该结点的颜色属性置为GRAY。

31 #include
     
       32 #include
      
        33  34 #define MaxVertexNum 50 35  36  37 typedef struct node 38 { 39     int adjvex; 40     struct node* next; 41 }EdgeNode; 42  43  44 typedef struct vnode 45 { 46     char name; 47     int father; 48     int startTime; 49     int endTime; 50          51     EdgeNode *firstedge; 52  53 }VertexNode, AdjList[MaxVertexNum]; 54  55  56 typedef struct 57 { 58     AdjList Adj; 59     int edgeNum, vertexNum; 60 }Graph; 61  62  63 typedef enum {WHITE, GRAY, BLACK} color; 64  65  66 color  Color[MaxVertexNum]; 67  68 int time; 69  70  71 void InitGraph(Graph *G) 72 { 73     int i, j, k; 74      75     EdgeNode *s; 76          77     printf("Input VertexNum  and EdgeNum :  "); 78     scanf("%d %d", &G->vertexNum, &G->edgeNum); 79     getchar(); 80  81     for(i = 0 ; i < G->vertexNum; i++) 82     { 83              84  85             scanf("%c", &G->Adj[i].name); 86             getchar(); 87              88  89             G->Adj[i].firstedge = NULL; 90              91             G->Adj[i].father = -1; 92              93             Color[i] = WHITE; 94  95     } 96  97     printf("input edges, Create Adjacency List :\n"); 98          99     for(k = 0 ; k < G->edgeNum; k++)100     {101         scanf("%d  %d", &i, &j);102         103         s = (EdgeNode*)malloc(sizeof(EdgeNode));104         105         s->adjvex = j;106 107         s->next = G->Adj[i].firstedge;108 109         G->Adj[i].firstedge  = s;110 111 112 113     /*   if the graph is undirected graph,114          release the following codes115         116         s = (EdgeNode *) malloc(sizeof(EdgeNode));117 118         s->adjvex = i;119 120         s->next = G->Adj[j].firstedge;121 122         G->Adj[j].firstedge = s;123     */124      }125 }126 127 128 129 130 131 void DFS_VISIT(Graph *G, int i)132 {133     EdgeNode *p;134         135     time = time+1;136 137     G->Adj[i].startTime = time;138 139     Color[i] = GRAY;140 141      p = G->Adj[i].firstedge;142 143      while(p)144      {145          if(Color[p->adjvex]==WHITE)146          {147              G->Adj[p->adjvex].father = i;148              DFS_VISIT(G, p->adjvex);149          }150          p = p->next;151      }152 153      Color[i] = BLACK;154      time++;155 156      G->Adj[i].endTime = time;157 }158 159 void DFS(Graph *G)160 {161     int i ;162 163     time = 0;164     for(i = 0; i < G->vertexNum; i++)165         if(Color[i] == WHITE)166             DFS_VISIT(G,i);167 }168 169 170 void PrintVisit(Graph *G, int source)171 {172     EdgeNode *p;173 174     p = G->Adj[source].firstedge;175 176     printf("current node name : %c\n", G->Adj[source].name);177     printf("current node connect to :\n");178 179     while(p)180     {181         printf("node:%c   ", G->Adj[p->adjvex].name);182         p = p->next;183     }184 185     printf("\n\n");186 187 }188 189 190 void PrintGraph(Graph *G)191 {192     int i;193     for(i = 0 ; i < G->vertexNum ; i++)194         PrintVisit(G , i );195 196 }197 198 199 200 201  int main()202  {203      Graph G;204 205      InitGraph(&G);206 207      PrintGraph(&G);208 209      DFS(&G);210 211          return 0;212 213  }
      
     

根据上面所化的图进行数据的输入是这样的

边：

S Z Y W X T V U 

 点：（0,1） （0,3）  （1,2）  （1,3）  （2,4） （3,4）  （4,1）

（6，0）  （6,3） （5,6） （5,7） （7,6） （7,5）

 

对于点的输入是这样的，

对应的是相应的点在G->Adj数组中的序号。

在控制台输入的时候是不需要添加括号和中间逗号的，

一组两个数，以空格分隔，回车换行接着输入下一条边。

例如第一个输入的是S符号，则说明S在Adj中的位序为0

而W是第四个输入的，在Adj中的位序3

如果想表示S->W 这条有向边的话，则在边输入的时候，输入0(空格)3

所以边的输入是要根据具体的点在Adj数组中的位序而定的。 

 

深度搜索在本文中是以递归实现的，

如果不适用递归的话，同样亦可以通过不断地压栈，

然后不断地弹栈来实现针对某一个结点的不断深入地搜索。

当 当前结点有三个子结点需要访问的时候，

如果默认是左优先，则把靠右边的两个结点全部压栈。

然后继续访问左结点的子结点，如此下去。

一旦当某一个结点再也找不到子结点的时候，

则弹栈，继续从弹出栈的结点进行深入访问，如此继续下去。

直到所有的结点都被访问后结束。