图的深度优先搜索

深度优先搜索（Depth-First Search, DFS）简单来说就是利用栈结构，不断遍历一个顶点的关联顶点。

基本思想

1. 首先访问图中某一个顶点 vᵢ，以该顶点为出发点。
2. 任选一个与顶点 vᵢ 邻接的未被访问的顶点 vⱼ；访问 vⱼ。
3. 以 vⱼ 为新的出发点继续进行深度优先搜索，直至图中所有和 vᵢ 有路径的顶点均被访问到。

算法实现

邻接矩阵形式

int visited[n];
graph g;
 
void DFS(int i) {  // 图用邻接矩阵存储
    int j;
    printf("node:%c\n", g.vexs[i]);
    visited[i] = TRUE;
    for (j = 0; j < n; j++)
        if ((g.arcs[i][j] == 1) && (!visited[j]))
            DFS(j);
}

邻接表形式

vexnode g[n];
 
void DFS(int i) {  // 图用邻接表存储
    int j;
    edgenode *p;
    printf("node:%c\n", g[j].vertex);
    visited[i] = TRUE;               // 标识当前结点为访问过
    p = g[i].link;                   // 得到当前结点的一条边
    while (p != NULL) {
        if (!visited[p->adjvex])     // 如果存在边并未被访问过
            DFS(p->adjvex);
        p = p->next;
    }
}

非连通图的遍历

对于非连通图，我们想要对其每个连通分量进行深度优先遍历，于是我们可以先找一个顶点进行遍历，遍历后检查是否有顶点未被访问，如果有则从未访问的顶点开始继续遍历。

void TRAVER() {  // 遍历用邻接矩阵表示的非连通图
    int i;
    for (i = 0; i < n; i++)
        visited[i] = FALSE;          // 标志数组初始化
    for (i = 0; i < n; i++)
        if (!visited[i])
            DFS(i);                  // 从顶点出发遍历一个连通分量
}

复杂度分析

• 对于邻接矩阵形式，无法直接得到一个顶点的邻接点，必须要遍历以该点为横坐标的所有值并一一与 1 比较来判断邻接点，时间复杂度为 O(n²)。
• 对于邻接表形式，可以直接知道邻接点的稀疏表示，快速拿到一个顶点的邻接点信息，时间复杂度为 O(n + e)。

链接到

• 上一个知识点：7.3 图的邻接表存储
• 下一个知识点：7.5 图的广度优先搜索
• 相关知识点：5.2 深度优先搜索