FA4-DFS-邻接矩阵¶

代码实现¶

递归¶

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

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

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

    // 递归访问所有未被访问的邻接顶点
    for (int i = 0; i < G.numver; i++) {
        // 检查是否存在从顶点v到顶点i的边，且顶点i未被访问
        if (G.Edge[v][i] == 1 && visit[i] == 0) {
            // 递归调用DFS，深度优先探索
            DFS(G, i);
        }
    }
}

非递归¶

C
/**
 * 非递归版本的DFS实现（使用显式栈）
 * 
 * 算法思想：
 * 1. 将起始顶点入栈
 * 2. 当栈不为空时，弹出栈顶元素并访问
 * 3. 将该顶点的所有未访问邻接顶点入栈
 * 4. 重复直到栈为空
 */
void DFS_NonRecursive(MGraph 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);

            // 将所有未访问的邻接顶点入栈（逆序入栈保证访问顺序）
            for (int i = G.numver - 1; i >= 0; i--) {
                if (G.Edge[v][i] == 1 && visit[i] == 0) {
                    stack[++top] = i;
                }
            }
        }
    }
}

复杂度分析¶

时间复杂度：O(V²)¶

V: 顶点数
每个顶点被访问一次：O(V)
对每个顶点，都要检查所有其他顶点寻找邻接点：O(V)
总时间复杂度：O(V × V) = O(V²)

空间复杂度：O(V)¶

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

图解说明¶

Text Only

示例图的邻接矩阵表示：
    0 1 2 3 4
  0 0 1 1 0 0
  1 1 0 0 1 0
  2 1 0 0 1 0
  3 0 1 1 0 1
  4 0 0 0 1 0

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

调用DFS(0):
├── 访问0，visit[0]=1
├── 查找0的邻接点：1,2
├── 调用DFS(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 ←───┘

相关知识点延伸¶

1. DFS与BFS的对比¶

特性	DFS	BFS
数据结构	栈（递归）	队列
遍历方式	纵深探索	层次扩展
空间复杂度	O(V)	O(V)
时间复杂度	O(V²)邻接矩阵	O(V²)邻接矩阵
最短路径	不一定最短	无权图最短路径
应用场景	拓扑排序、强连通分量	最短路径、连通性

2. DFS的经典应用¶

C
// 检测图中是否存在环（有向图）
int detectCycle(MGraph G) {
    int visit[maxsize] = {0};    // 访问状态
    int recStack[maxsize] = {0}; // 递归栈跟踪

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

3. 图的连通性分析¶

C
// 计算连通分量个数
int countComponents(MGraph G) {
    int visit[maxsize] = {0};
    int count = 0;

    for (int i = 0; i < G.numver; i++) {
        if (visit[i] == 0) {
            DFS(G, i);  // 访问一个连通分量
            count++;    // 连通分量数加1
        }
    }
    return count;
}

4. 拓扑排序实现¶

C
// 基于DFS的拓扑排序
void topologicalSort(MGraph G) {
    int visit[maxsize] = {0};
    int stack[maxsize];  // 存储拓扑序列
    int top = -1;

    // 对所有未访问顶点进行DFS
    for (int i = 0; i < G.numver; i++) {
        if (visit[i] == 0) {
            DFS_Topological(G, i, visit, stack, &top);
        }
    }

    // 输出拓扑序列
    while (top != -1) {
        printf("%d ", stack[top--]);
    }
}

5. DFS搜索树的概念¶

DFS遍历过程中会形成一棵搜索树： - 树边：DFS遍历中实际使用的边 - 回边：指向祖先节点的边（用于检测环） - 前向边：指向后代节点的边 - 横叉边：其他连接不同子树的边

这些概念在图论算法分析中非常重要。