深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。其过程为：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中的某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

其算法可以描述如下：

//--- 算法7.4和7.5使用的全局变量 ---
bool visited[MAX_VERTEX_NUM];    // 访问标志数组
Status (*VisitFunc)(int v);      // 函数变量

void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 算法7.4
    // 对图G作深度优先遍历。
    int v;
    VisitFunc = Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数
    for (v=0; v<g.vexnum visited false for v if dfs void g int w true visitfunc></g.vexnum>