FA5-DFS-邻接表¶

代码实现¶

递归版本¶

C
/**
 * 图的深度优先搜索遍历（DFS）- 邻接表实现
 * 
 * 算法思想：
 * 1. 从起始顶点开始访问
 * 2. 访问一个未被访问的邻接顶点
 * 3. 以该邻接顶点为新的起始点，重复步骤2
 * 4. 当某顶点的所有邻接顶点都被访问过时，回溯到上一个顶点
 * 5. 继续寻找未被访问的邻接顶点，直到所有顶点都被访问
 * 
 * 核心特点：
 * - 使用递归实现，体现"深度优先"的思想
 * - 先纵深探索，再横向扩展
 * - 使用栈（递归调用栈）来实现回溯机制
 * - 邻接表实现使得查找邻接点更加高效
 */

void DFS(Graph G, int v) {
    // 访问标记数组（建议作为全局变量或静态变量）
    // 这里为了函数独立性，每次调用都重新初始化
    static int visit[maxsize] = {0};

    // 访问当前顶点（标记为已访问并输出）
    visit[v] = 1;
    printf("%d ", v);

    // 获取当前顶点的第一条邻接边
    Node p = G.adjlist[v].firstarc;

    // 遍历当前顶点的所有邻接边
    for (; p != NULL; p = p->nextarc) {
        // 检查邻接顶点是否未被访问
        if (visit[p->adjvex] == 0) {
            // 递归调用DFS，深度优先探索邻接顶点
            DFS(G, p->adjvex);
        }
    }
}

非递归版本¶

C
/**
 * 非递归版本的DFS实现（使用显式栈）- 邻接表版本
 * 
 * 算法思想：
 * 1. 将起始顶点入栈
 * 2. 当栈不为空时，弹出栈顶元素并访问
 * 3. 将该顶点的所有未访问邻接顶点入栈
 * 4. 重复直到栈为空
 */
void DFS_NonRecursive(Graph G, int v) {
    // 访问标记数组
    int visit[maxsize] = {0};

    // 显式栈，用于模拟递归过程
    int stack[maxsize];
    int top = -1;  // 栈顶指针，-1表示空栈

    // 起始顶点入栈
    stack[++top] = v;

    // 当栈不为空时继续
    while (top != -1) {
        // 弹出栈顶元素
        v = stack[top--];

        // 如果该顶点未被访问
        if (visit[v] == 0) {
            // 访问该顶点
            visit[v] = 1;
            printf("%d ", v);

            // 将所有未访问的邻接顶点入栈
            // 注意：邻接表是链式结构，需要逆序遍历保证访问顺序
            Node p = G.adjlist[v].firstarc;
            // 先将所有邻接点存入临时数组
            int adj_vertices[maxsize];
            int count = 0;

            for (; p != NULL; p = p->nextarc) {
                if (visit[p->adjvex] == 0) {
                    adj_vertices[count++] = p->adjvex;
                }
            }

            // 逆序入栈（保证访问顺序的一致性）
            for (int i = count - 1; i >= 0; i--) {
                stack[++top] = adj_vertices[i];
            }
        }
    }
}

C
/**
 * 更简洁的非递归DFS实现
 * 直接按邻接表顺序入栈（访问顺序可能与递归版本不同）
 */
void DFS_NonRecursive_Simple(Graph G, int v) {
    int visit[maxsize] = {0};
    int stack[maxsize];
    int top = -1;

    stack[++top] = v;

    while (top != -1) {
        v = stack[top--];

        if (visit[v] == 0) {
            visit[v] = 1;
            printf("%d ", v);

            // 直接按邻接表顺序将邻接点入栈
            Node p = G.adjlist[v].firstarc;
            for (; p != NULL; p = p->nextarc) {
                if (visit[p->adjvex] == 0) {
                    stack[++top] = p->adjvex;
                }
            }
        }
    }
}

复杂度分析¶

时间复杂度：O(V + E)¶

V: 顶点数，E: 边数
每个顶点被访问一次：O(V)
每条边被检查一次：O(E)
总时间复杂度：O(V + E)

空间复杂度：O(V)¶

递归版本：
visit[]数组：O(V)
递归调用栈：最坏情况O(V)（图退化为链）
非递归版本：
visit[]数组：O(V)
显式栈：最坏情况O(V)
总空间复杂度：O(V)

图解说明¶

Text Only

示例图结构（邻接表表示）：
0 -> 1 -> 2
1 -> 0 -> 3
2 -> 0 -> 3
3 -> 1 -> 2 -> 4
4 -> 3

递归DFS执行过程（从顶点0开始）：

调用DFS(0):
├── 访问0，visit[0]=1
├── 遍历0的邻接表：1 -> 2
├── 调用DFS(1)  ← 按邻接表顺序，先访问1
│   ├── 访问1，visit[1]=1
│   ├── 遍历1的邻接表：0 -> 3
│   ├── 0已访问，调用DFS(3)
│   │   ├── 访问3，visit[3]=1
│   │   ├── 遍历3的邻接表：1 -> 2 -> 4
│   │   ├── 1已访问，2已访问，调用DFS(4)
│   │   │   ├── 访问4，visit[4]=1
│   │   │   ├── 遍历4的邻接表：3（已访问）
│   │   │   └── DFS(4)返回
│   │   └── DFS(3)返回
│   └── DFS(1)返回
└── 回到DFS(0)，继续遍历0的邻接表
    └── 1已访问，2未访问，调用DFS(2)
        ├── 访问2，visit[2]=1
        ├── 遍历2的邻接表：0 -> 3（都已访问）
        └── DFS(2)返回

访问顺序：0 -> 1 -> 3 -> 4 -> 2

执行轨迹图：
0 ──→ 1 ──→ 3 ──→ 4
│     ↓    ↗
│     └─→ 2
└──────────┘

邻接表遍历过程：
顶点0: [1] -> [2]  （按链表顺序访问）
顶点1: [0] -> [3]  （0已访问，访问3）
顶点3: [1] -> [2] -> [4] （1,2已访问，访问4）
顶点4: [3] （3已访问，回溯）
顶点2: [0] -> [3] （0,3已访问，回溯）

相关知识点延伸¶

1. 邻接表与邻接矩阵DFS的比较¶

特性	邻接表DFS	邻接矩阵DFS
时间复杂度	O(V + E)	O(V²)
空间复杂度	O(V + E)	O(V²)
适用图类型	稀疏图	稠密图
邻接点查找	O(degree)	O(V)
实现复杂度	较复杂	较简单

2. DFS的四种边类型（有向图）¶

C
// 在DFS过程中可以识别四种边类型
enum EdgeType {
    TREE_EDGE,     // 树边：DFS树中的边
    BACK_EDGE,     // 回边：指向祖先的边（检测环）
    FORWARD_EDGE,  // 前向边：指向后代的边
    CROSS_EDGE     // 横叉边：其他边
};

3. DFS在有向图中的应用¶

C
// 检测有向图中的环
int isCyclic(Graph G) {
    int color[maxsize] = {0}; // 0:未访问, 1:正在访问, 2:已完成访问

    for (int i = 0; i < G.numver; i++) {
        if (color[i] == 0) {
            if (isCyclicUtil(G, i, color)) {
                return 1; // 存在环
            }
        }
    }
    return 0; // 无环
}

int isCyclicUtil(Graph G, int v, int color[]) {
    color[v] = 1; // 标记为正在访问

    Node p = G.adjlist[v].firstarc;
    for (; p != NULL; p = p->nextarc) {
        if (color[p->adjvex] == 1) {
            return 1; // 发现回边，存在环
        }
        if (color[p->adjvex] == 0 && isCyclicUtil(G, p->adjvex, color)) {
            return 1;
        }
    }

    color[v] = 2; // 标记为已完成访问
    return 0;
}

4. 强连通分量算法（Kosaraju算法）¶

C
// 使用两次DFS计算强连通分量
void findSCC(Graph G) {
    int visited[maxsize] = {0};
    int stack[maxsize];
    int top = -1;

    // 第一次DFS：按完成时间排序
    for (int i = 0; i < G.numver; i++) {
        if (!visited[i]) {
            DFS_First(G, i, visited, stack, &top);
        }
    }

    // 构造转置图
    Graph GT = transposeGraph(G);

    // 重置访问标记
    memset(visited, 0, sizeof(visited));

    // 第二次DFS：按完成时间逆序访问转置图
    while (top != -1) {
        int v = stack[top--];
        if (!visited[v]) {
            printf("SCC: ");
            DFS(GT, v);  // 每次DFS访问一个强连通分量
            printf("\n");
        }
    }
}

5. DFS生成树和应用¶

DFS遍历会生成DFS生成树，这个树在以下方面有重要应用： - 关节点检测：删除后图不再连通的顶点 - 桥边检测：删除后图不再连通的边 - 双连通分量：不含关节点的极大子图 - 欧拉回路：经过每条边恰好一次的回路

这些概念构成了图论算法的重要基础。