FB2-判断有向图中两个顶点间是否存在路径¶

代码实现¶

DFS¶

C
/**
 * 判断有向图中两个顶点间是否存在路径 - DFS实现
 * 
 * 算法思想：
 * 使用深度优先搜索从起始顶点Vi开始遍历，看是否能到达目标顶点Vj
 * 
 * 核心思路：
 * 1. 从顶点i开始进行DFS遍历
 * 2. 在遍历过程中，如果遇到目标顶点j，则说明存在路径
 * 3. 使用visit数组避免重复访问，防止无限递归
 * 4. 通过指针参数res返回查找结果
 * 
 * @param G 图的邻接表表示
 * @param i 起始顶点
 * @param j 目标顶点
 * @param visit 访问标记数组
 * @param res 结果指针，用于返回是否存在路径
 */
void pathExistsDFS(Graph G, int i, int j, int visit[], bool* res) {
    // 基础情况：如果当前顶点就是目标顶点，说明找到路径
    if (i == j) {
        *res = true;
        return;  // 可以提前返回，优化性能
    }

    // 标记当前顶点i为已访问，防止重复访问形成环
    visit[i] = 1;

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

    // 遍历当前顶点的所有邻接顶点
    for (; p != NULL; p = p->nextarc) {
        // 如果邻接顶点未被访问过
        if (visit[p->adjvex] == 0) {
            // 递归搜索从邻接顶点到目标顶点j的路径
            pathExistsDFS(G, p->adjvex, j, visit, res);

            // 如果已经找到路径，可以提前返回（可选优化）
            if (*res == true) {
                return;
            }
        }
    }
}

BFS¶

C
/**
 * 判断有向图中两个顶点间是否存在路径 - BFS实现
 * 
 * 算法思想：
 * 使用广度优先搜索从起始顶点Vi开始层次遍历，看是否能到达目标顶点Vj
 * 
 * 核心思路：
 * 1. 从顶点i开始进行BFS遍历
 * 2. 按层次扩展，将可达顶点逐层加入队列
 * 3. 如果在遍历过程中遇到目标顶点j，则说明存在路径
 * 4. 如果队列为空仍未找到目标顶点，则不存在路径
 * 
 * @param G 图的邻接表表示
 * @param i 起始顶点
 * @param j 目标顶点
 * @return true表示存在路径，false表示不存在路径
 */
bool pathExistsBFS(Graph G, int i, int j) {
    // 特殊情况：起始顶点就是目标顶点
    if (i == j) {
        return true;
    }

    // 访问标记数组，初始化为0（未访问）
    int visit[maxsize] = {0};

    // 循环队列，用于BFS层次遍历
    int que[maxsize];
    int front = 0, rear = 0;

    // 将起始顶点i入队并标记为已访问
    que[rear++] = i;
    visit[i] = 1;

    // 当队列不为空时继续搜索
    while (front != rear) {
        // 出队操作：获取队首顶点
        i = que[front++];

        // 检查当前顶点是否为目标顶点
        if (i == j) {
            return true;  // 找到目标顶点，存在路径
        }

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

        // 遍历当前顶点的所有邻接顶点
        for (; p != NULL; p = p->nextarc) {
            // 如果邻接顶点未被访问过
            if (visit[p->adjvex] == 0) {
                // 将邻接顶点入队并标记为已访问
                que[rear++] = p->adjvex;
                visit[p->adjvex] = 1;
            }
        }
    }

    // 队列为空仍未找到目标顶点，说明不存在路径
    return false;
}

C
/**
 * 更简洁的DFS实现（直接返回结果，不使用指针参数）
 * 
 * @param G 图的邻接表表示
 * @param i 起始顶点
 * @param j 目标顶点
 * @param visit 访问标记数组
 * @return true表示存在路径，false表示不存在路径
 */
bool pathExistsDFS_Simple(Graph G, int i, int j, int visit[]) {
    // 基础情况：如果当前顶点就是目标顶点，说明找到路径
    if (i == j) {
        return true;
    }

    // 标记当前顶点为已访问
    visit[i] = 1;

    // 遍历当前顶点的所有邻接顶点
    Node p = G.adjlist[i].firstarc;
    for (; p != NULL; p = p->nextarc) {
        // 如果邻接顶点未被访问，递归搜索
        if (visit[p->adjvex] == 0) {
            if (pathExistsDFS_Simple(G, p->adjvex, j, visit)) {
                return true;  // 找到路径，直接返回
            }
        }
    }

    // 未找到路径
    return false;
}

C
/**
 * 双向BFS实现（优化版本）
 * 
 * 算法思想：
 * 同时从起点和终点开始进行BFS，当两个搜索相遇时说明存在路径
 * 可以在某些情况下减少搜索空间
 * 
 * @param G 图的邻接表表示
 * @param i 起始顶点
 * @param j 目标顶点
 * @return true表示存在路径，false表示不存在路径
 */
bool pathExistsBidirectionalBFS(Graph G, int i, int j) {
    if (i == j) return true;

    int visit_start[maxsize] = {0};  // 从起点开始的访问标记
    int visit_end[maxsize] = {0};    // 从终点开始的访问标记

    int que_start[maxsize], que_end[maxsize];
    int front_start = 0, rear_start = 0;
    int front_end = 0, rear_end = 0;

    // 起点BFS初始化
    que_start[rear_start++] = i;
    visit_start[i] = 1;

    // 终点BFS初始化
    que_end[rear_end++] = j;
    visit_end[j] = 1;

    // 交替进行双向BFS
    while (front_start != rear_start && front_end != rear_end) {
        // 从起点开始的BFS一步
        int current_start = que_start[front_start++];
        Node p_start = G.adjlist[current_start].firstarc;
        for (; p_start != NULL; p_start = p_start->nextarc) {
            int adj_vertex = p_start->adjvex;
            if (visit_start[adj_vertex] == 0) {
                // 如果该顶点已被终点BFS访问过，说明路径存在
                if (visit_end[adj_vertex] == 1) {
                    return true;
                }
                visit_start[adj_vertex] = 1;
                que_start[rear_start++] = adj_vertex;
            }
        }

        // 从终点开始的BFS一步
        int current_end = que_end[front_end++];
        Node p_end = G.adjlist[current_end].firstarc;
        for (; p_end != NULL; p_end = p_end->nextarc) {
            int adj_vertex = p_end->adjvex;
            if (visit_end[adj_vertex] == 0) {
                // 如果该顶点已被起点BFS访问过，说明路径存在
                if (visit_start[adj_vertex] == 1) {
                    return true;
                }
                visit_end[adj_vertex] = 1;
                que_end[rear_end++] = adj_vertex;
            }
        }
    }

    return false;
}

复杂度分析¶

DFS方法复杂度¶

时间复杂度：O(V + E)
最坏情况下需要访问所有顶点和边
V: 顶点数，E: 边数
空间复杂度：O(V)
visit数组：O(V)
递归调用栈：最坏情况O(V)

BFS方法复杂度¶

时间复杂度：O(V + E)
同样需要访问所有可达的顶点和边
空间复杂度：O(V)
visit数组：O(V)
队列空间：最坏情况O(V)

图解说明¶

Text Only

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

判断从顶点0到顶点4是否存在路径：

DFS执行过程：
调用pathExistsDFS(0, 4):
├── 访问0，visit[0]=1
├── 遍历0的邻接点：1, 2
├── 调用pathExistsDFS(1, 4)
│   ├── 访问1，visit[1]=1
│   ├── 遍历1的邻接点：3
│   ├── 调用pathExistsDFS(3, 4)
│   │   ├── 访问3，visit[3]=1
│   │   ├── 遍历3的邻接点：4
│   │   ├── 调用pathExistsDFS(4, 4)
│   │   │   ├── i==j，设置res=true
│   │   │   └── 返回
│   │   └── 返回
│   └── 返回
└── 返回

BFS执行过程：
队列：[0] → 访问0
队列：[1,2] → 访问1
队列：[2,3] → 访问2
队列：[3,3,4] → 访问3
队列：[3,4,4] → 访问3
队列：[4,4] → 访问4 → 找到目标，返回true

搜索路径图：
0 ──→ 1 ──→ 3 ──→ 4
│              ↗
└────→ 2 ──────┘

相关知识点延伸¶

1. 两种方法的比较¶

特性	DFS	BFS
搜索方式	纵深探索	层次扩展
内存使用	递归栈	显式队列
路径特性	可能找到较长路径	找到最短路径
实现复杂度	递归简洁	迭代直观

2. 最短路径查找¶

C
// 使用BFS查找最短路径长度
int shortestPathLength(Graph G, int i, int j) {
    if (i == j) return 0;

    int visit[maxsize] = {0};
    int distance[maxsize] = {0};  // 记录到起始点的距离
    int que[maxsize];
    int front = 0, rear = 0;

    que[rear++] = i;
    visit[i] = 1;

    while (front != rear) {
        int current = que[front++];

        if (current == j) {
            return distance[current];  // 返回最短距离
        }

        Node p = G.adjlist[current].firstarc;
        for (; p != NULL; p = p->nextarc) {
            if (visit[p->adjvex] == 0) {
                visit[p->adjvex] = 1;
                distance[p->adjvex] = distance[current] + 1;
                que[rear++] = p->adjvex;
            }
        }
    }

    return -1;  // 不可达
}

3. 实际应用场景¶

C
// 社交网络中的好友关系判断
bool areConnected(UserGraph G, int user1, int user2) {
    return pathExistsBFS(G, user1, user2);
}

// 网络路由可达性检查
bool isReachable(NetworkGraph G, int source, int destination) {
    return pathExistsDFS(G, source, destination, visit_array, &result);
}

// 依赖关系检查（任务调度）
bool hasDependency(TaskGraph G, int task1, int task2) {
    return pathExistsBFS(G, task1, task2);
}

4. 算法优化技巧¶

C
// 带剪枝的DFS优化
bool pathExistsDFS_Optimized(Graph G, int i, int j, int visit[], int max_depth, int current_depth) {
    // 深度限制剪枝
    if (current_depth > max_depth) {
        return false;
    }

    if (i == j) return true;

    visit[i] = 1;

    Node p = G.adjlist[i].firstarc;
    for (; p != NULL; p = p->nextarc) {
        if (visit[p->adjvex] == 0) {
            if (pathExistsDFS_Optimized(G, p->adjvex, j, visit, max_depth, current_depth + 1)) {
                return true;
            }
        }
    }

    visit[i] = 0;  // 回溯时重置访问标记（如果需要多次调用）
    return false;
}

这些算法在实际的图论问题中应用广泛，是解决路径相关问题的基础工具。