基于邻接矩阵的无向无权图两点间所有路径查找求助

阿华AIGC实验室

2026-5-21

无向无权图邻接矩阵全路径查找的实现方案

嘿，看你的描述，应该是在用回溯法找两点间所有路径时，卡在了邻接矩阵的邻接节点遍历部分对吧？别着急，我们结合你给出的算法思路，一步步把这个问题解决掉。

先回顾你的核心算法逻辑

你给出的伪代码是标准的回溯思路，完全没问题：

用栈（或者数组/vector模拟栈）记录当前路径
当当前节点等于目标时，输出完整路径
否则遍历所有邻接且不在当前路径中的节点，递归搜索
递归返回后弹出当前节点，完成回溯

针对邻接矩阵的关键实现细节

邻接矩阵的核心是：matrix[u][v]为1（或者你定义的连通标记）时，u和v是相邻节点。但因为是无向图，matrix[u][v]和matrix[v][u]是完全等价的，还要注意跳过节点自身（除非你的图允许自环，一般无向图不需要考虑）。

那你卡壳的foreach部分，对应到邻接矩阵的实现应该是这样：

遍历所有节点v（从0到numVertices-1，假设节点是从0开始编号）
同时满足两个条件：
1. matrix[current][v] == 1（current和v连通）
2. v不在当前的路径中（避免无向图中往回走，陷入死循环）

完整的代码实现（适配你的类结构）

假设你的AdjacencyMatrix类已经包含了邻接矩阵matrix和节点总数numVertices，我们可以添加一个递归辅助函数来实现核心逻辑：

#include <iostream>
#include <vector>
using namespace std;

class AdjacencyMatrix {
private:
    int** matrix;
    int numVertices;

    // 递归辅助函数：current是当前节点，dest是目标节点，path记录当前路径，visited标记路径中的节点
    void findPathsHelper(int current, int dest, vector<int>& path, vector<bool>& visited) {
        // 将当前节点加入路径并标记为已访问
        path.push_back(current);
        visited[current] = true;

        // 到达目标节点，输出路径
        if (current == dest) {
            for (size_t i = 0; i < path.size(); ++i) {
                if (i > 0) cout << " -> ";
                cout << path[i];
            }
            cout << endl;
        } else {
            // 遍历所有节点，寻找符合条件的邻接节点
            for (int v = 0; v < numVertices; ++v) {
                // 邻接且未被访问（不在当前路径中）
                if (matrix[current][v] == 1 && !visited[v]) {
                    findPathsHelper(v, dest, path, visited);
                }
            }
        }

        // 回溯：弹出当前节点，取消访问标记
        path.pop_back();
        visited[current] = false;
    }

public:
    // 构造函数、析构函数等初始化逻辑省略，假设已正确初始化matrix和numVertices
    void Find_All_Paths(int Origin, int Destination) {
        // 先校验节点合法性
        if (Origin < 0 || Origin >= numVertices || Destination < 0 || Destination >= numVertices) {
            cout << "错误：起点或终点节点编号无效！" << endl;
            return;
        }

        vector<int> path;
        vector<bool> visited(numVertices, false);
        findPathsHelper(Origin, Destination, path, visited);
    }
};

你可能遇到的瓶颈优化点

路径节点判断的效率优化：一开始如果用线性遍历判断节点是否在路径中，效率较低，改成visited布尔数组后，判断操作变成O(1)，大大提升了大节点数场景下的性能。
无向图的死循环避免：因为无向图的双向连通性，如果不做visited标记，会出现u→v→u→v...的死循环，这也是你必须在遍历邻接节点时加判断的原因。
邻接矩阵遍历范围：一定要确保遍历所有节点（从0到numVertices-1），不要遗漏任何可能的邻接节点。