FC05-使用深度优先搜索输出从顶点 Vi 到 Vj 的所有简单路径¶

代码实现¶

C
// 函数 DFS：使用深度优先搜索输出从顶点 Vi 到 Vj 的所有简单路径
// 参数说明：
// G - 图的邻接表表示
// i - 当前访问的顶点（起始顶点）
// j - 目标顶点
// visit[] - 访问标记数组，标记顶点是否已被访问
// path[] - 存储当前路径的数组
// top - 指向路径数组栈顶的指针
void DFS(Graph G, int i, int j, int visit[], int path[], int *top) {
    // 标记当前顶点 i 为已访问
    visit[i] = 1;

    // 将当前顶点 i 加入路径数组
    path[++(*top)] = i;

    // 如果当前顶点就是目标顶点，则输出这条路径
    if (i == j) {
        // 输出从起始顶点到目标顶点的完整路径
        for (int k = 0; k <= *top; k++) {
            printf("%d ", path[k]);
        }
        printf("\n"); // 换行，表示一条完整路径
    }

    // 遍历当前顶点 i 的所有邻接顶点
    Node p = G.adjlist[i].firstarc; // 获取顶点 i 的第一条边
    for (; p != NULL; p = p->nextarc) {
        // 如果邻接顶点未被访问过，则递归搜索
        if (visit[p->adjvex] == 0) {
            DFS(G, p->adjvex, j, visit, path, top);
        }
    }

    // 回溯：路径栈顶指针减 1，恢复顶点 i 的未访问状态
    --(*top);        // 从路径中移除当前顶点
    visit[i] = 0;    // 恢复当前顶点为未访问状态
}

代码逻辑解析¶

1. 图的邻接表表示¶

C
// 图的邻接表结构（假设定义如下）
typedef struct ArcNode {
    int adjvex;              // 邻接顶点的编号
    struct ArcNode *nextarc; // 指向下一个邻接点
} ArcNode, *Node;

typedef struct VNode {
    int data;                // 顶点数据
    ArcNode *firstarc;       // 指向第一条边
} VNode;

typedef struct {
    VNode adjlist[MAXVEX];   // 邻接表数组
    int vexnum, arcnum;      // 顶点数和边数
} Graph;

2. 算法核心思想¶

使用深度优先搜索（DFS）遍历图
通过回溯法找出所有可能的路径
使用访问标记数组避免形成环路（保证路径简单性）

3. 关键数据结构¶

visit[]：访问标记数组，防止重复访问同一顶点
path[]：路径数组，记录当前搜索路径
top：路径栈顶指针，指示当前路径的末尾位置

4. 算法流程¶

标记访问：将当前顶点标记为已访问
加入路径：将当前顶点加入路径数组
路径判断：如果到达目标顶点，输出路径
递归搜索：对未访问的邻接顶点递归搜索
回溯恢复：搜索完成后恢复状态，为其他路径搜索做准备

时间复杂度分析¶

1. 最坏情况分析¶

对于有 V 个顶点、E 条边的有向图： - 在最坏情况下，可能需要遍历所有可能的路径 - 路径数量可能达到指数级别 O(V!)

2. 实际复杂度¶

访问顶点：每个顶点可能被多次访问（不同路径）
遍历边：每条边在搜索过程中可能被访问一次
总体时间复杂度：O(V + E)（单次遍历）+ 路径输出开销

但考虑到需要输出所有路径，实际时间复杂度为： O((V + E) × P)，其中 P 是从源点到终点的简单路径数量

3. 给定复杂度说明¶

题目给出的 O(V + E) 是指单次完整 DFS 遍历的时间复杂度，不考虑路径输出的开销。

空间复杂度分析¶

1. 额外空间使用¶

visit[] 数组：O(V)
path[] 数组：O(V)
递归调用栈：O(V)（最坏情况下递归深度为 V）

2. 总体空间复杂度¶

O(V)，其中 V 是顶点数

较难理解部分的说明¶

1. 回溯机制的重要性¶

C
// 回溯操作
--(*top);        // 从路径中移除当前顶点
visit[i] = 0;    // 恢复当前顶点为未访问状态

这两行代码是算法正确性的关键： - 路径回溯：当从当前顶点的所有邻接点搜索完成后，需要将该顶点从路径中移除 - 状态恢复：将顶点标记为未访问，使得其他路径可以经过该顶点

图解说明：¶

假设图结构如下：

Text Only
1 2 3	`1 → 2 → 4 ↓ ↓ 3 → 5`

从顶点 1 到顶点 4 的搜索过程：

Text Only

路径1: 1 → 2 → 4 (找到目标，输出路径)
回溯: 4出栈，2标记为未访问
路径2: 1 → 2 → 5 (继续搜索)
回溯: 5出栈，2标记为未访问，然后1标记为未访问
路径3: 1 → 3 → 5 (继续搜索)

2. 简单路径的保证¶

通过 visit[] 数组确保路径简单性：

C
if (visit[p->adjvex] == 0) // 只有未访问的顶点才能加入路径

这样避免了路径中出现环路，保证了路径的简单性。

延伸知识点¶

1. 完整调用示例¶

C
// 查找从顶点 start 到顶点 end 的所有简单路径
void findAllPaths(Graph G, int start, int end) {
    int visit[MAXVEX] = {0};     // 访问标记数组
    int path[MAXVEX];            // 路径数组
    int top = -1;                // 路径栈顶指针

    printf("从顶点 %d 到顶点 %d 的所有简单路径:\n", start, end);
    DFS(G, start, end, visit, path, &top);
}

2. 路径长度限制版本¶

C
// 限制路径长度的版本
void DFSWithLengthLimit(Graph G, int i, int j, int visit[], 
                       int path[], int *top, int maxLength) {
    if (*top >= maxLength) return; // 超过长度限制

    visit[i] = 1;
    path[++(*top)] = i;

    if (i == j) {
        for (int k = 0; k <= *top; k++) {
            printf("%d ", path[k]);
        }
        printf("\n");
    }

    Node p = G.adjlist[i].firstarc;
    for (; p != NULL; p = p->nextarc) {
        if (visit[p->adjvex] == 0) {
            DFSWithLengthLimit(G, p->adjvex, j, visit, path, top, maxLength);
        }
    }

    --(*top);
    visit[i] = 0;
}

3. 非递归版本 - 使用栈¶

C
// 非递归版本实现
void findAllPathsIterative(Graph G, int start, int end) {
    Stack* stack = createStack(); // 存储搜索状态
    int visit[MAXVEX] = {0};

    // 初始状态入栈
    push(stack, createState(start, -1));
    visit[start] = 1;

    while (!isEmpty(stack)) {
        State current = pop(stack);

        if (current.vertex == end) {
            // 输出路径
            printPath(stack);
        }

        // 处理当前顶点的邻接点
        Node p = G.adjlist[current.vertex].firstarc;
        while (p != NULL) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                push(stack, createState(p->adjvex, current.vertex));
            }
            p = p->nextarc;
        }
    }
}

4. BFS 版本（层序搜索）¶

C
// 使用广度优先搜索查找路径
void findAllPathsBFS(Graph G, int start, int end) {
    Queue* queue = createQueue();
    enqueue(queue, createPath(start));

    while (!isEmpty(queue)) {
        Path currentPath = dequeue(queue);
        int currentVertex = currentPath.lastVertex;

        if (currentVertex == end) {
            printPath(currentPath);
            continue;
        }

        // 扩展路径
        Node p = G.adjlist[currentVertex].firstarc;
        while (p != NULL) {
            if (!isInPath(currentPath, p->adjvex)) {
                Path newPath = extendPath(currentPath, p->adjvex);
                enqueue(queue, newPath);
            }
            p = p->nextarc;
        }
    }
}

5. 实际应用场景¶

网络路由：查找网络中两点间的所有可能路径
社交网络：查找人际关系链中的所有连接路径
游戏AI：棋类游戏中查找所有可能的走棋路径
交通规划：城市间的所有可能行驶路线
编译器：控制流图中基本块间的所有执行路径

6. 性能优化建议¶

C
// 剪枝优化版本
void DFSOptimized(Graph G, int i, int j, int visit[], 
                  int path[], int *top, int minDistance[]) {
    // 剪枝：如果当前路径长度已经超过已知最短路径，停止搜索
    if (minDistance[i] != -1 && *top >= minDistance[i]) {
        return;
    }

    visit[i] = 1;
    path[++(*top)] = i;

    if (i == j) {
        if (minDistance[j] == -1 || *top < minDistance[j]) {
            minDistance[j] = *top; // 更新最短距离
        }
        // 输出路径...
    }

    Node p = G.adjlist[i].firstarc;
    for (; p != NULL; p = p->nextarc) {
        if (visit[p->adjvex] == 0) {
            DFSOptimized(G, p->adjvex, j, visit, path, top, minDistance);
        }
    }

    --(*top);
    visit[i] = 0;
}

这种方法体现了图遍历、回溯算法和状态恢复的经典思想，是解决图论中路径问题的重要方法。