假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中某个顶点v出发，访问此顶点，然后访问v的一个未被访问的邻接节点w1，接着再从w1出发，访问w1的一个未被访问过的邻接节点w2，然后再从w2出发，访问w2的一个未被访问的邻接顶点w3…如此下去深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到；若此时途中尚有顶点未被访问，则另选图中另外一个未曾被访问的顶点做起始节点，重复上述过程，直至途中所有节点都被访问到为止。
三、代码实现（以图的存储结构邻接表为例）
/*深度优先遍历*/ int visited[MAX_VERTEX]; /*遍历标记*/ int DFS(adjListGraph_p adjGraph, int i) { edgeNode_p e; int j; printf("vertex: %c\n", adjGraph->graph[i].vertex); visited[i] = 1; e = adjGraph->graph[i].fistNode; while(e) { j = locateGraph(adjGraph, e->vertex); if (!visited[j]) DFS(adjGraph, j); e = e->next; } return 0; } int DFSAdjList(adjListGraph_p adjGraph) { int i; for(i = 0; i < adjGraph->numVertex; i++) visited[i] = 0; for(i = 0; i < adjGraph->numVertex; i++) { if (!visited[i]) { DFS(adjGraph, i); } } return 0; }
测试见下个博文，广度优先遍历一起测试。
关注公众号"小败日记"，搬砖过程遇到的问题，大家一起探讨，资源共享
