使用深度优先搜索 (DFS) C++ 查找图中两个节点之间是否存在路径

Question

我正在尝试实现深度优先搜索（DFS），如果图中两个节点之间存在路径，则使用递归返回布尔值。下面是我的实现。边缘输入采用向量数组的形式。

我尝试调试程序以检测到底哪里出错了，但我不知道为什么当我调用 return validPath_helper(n, i, destination,visited, adjList);validPath 函数中执行 code> 函数。

bool validPath_helper(int n, int source, int destination, vector<bool> visited, vector<vector<int>> adjList){
    visited[source] = true;

    if(adjList[source][destination]){
        return true;
    }

    for(int i=0; i<adjList[source].size(); i++){
        if(adjList[source][i]){
            return validPath_helper(n, i, destination, visited, adjList);
        }
    }
    return false;
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<bool> visited(n, false);
    vector<vector<int>> adjList(n);

    int u, v;
    for(int i=0; i<edges.size(); i++){
        u = edges[i][0];
        v = edges[i][1];
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    for(int i=source; i<n; i++){
        if(!visited[i]){
            return validPath_helper(n, i, destination, visited, adjList);
        }
    }
    return false;
}

任何帮助将不胜感激！

Answer 1

段错误通常是由于访问未分配的内存而发生的，因此您应该首先调查这一点。您说 validPath_helper 正在触发 seg 错误，因此您应该检查该函数。

在您的情况下，罪魁祸首是这一行：

if(adjList[source][destination]){
    return true;
}

这里您想检查源节点和目标节点之间是否存在边。但是，如果您回顾一下创建邻接列表的方式，您会发现它是一个向量的向量，对于每个节点，我们都有一个它有边的节点列表。

例如下图：

1 - 2
0 - 1
1 - 3

邻接列表将是：

0 -> 1
1 -> 0 2 3
2 -> 1
3 -> 1

让我们以源 2 和目标 3 为例。
现在，当您的 validPath_helper 被调用时，它将检查 adjList[2][3] 但正如您在上面看到的 adjList[2] 的长度仅为 1，因此没有第四个元素检查（3 是索引，因此是第四个元素）。这是您的段错误的原因。

这也会导致代码中出现一个完全不同的问题，即您想要检查 2 和 3 之间是否存在边，而是检查 2 列表的第 4 个位置是否存在非零元素。

您可以通过几种方法解决这个问题。

方法 # 1

而不是

if(adjList[source][destination]){
    return true;
}

try

for (int index = 0; index < adjList[source].size(); index++) {
    if (adjList[source][index] == destination)
        return true;
}

您需要在 validPath_helper 函数的两个位置进行此更改。

方法#2

在大图的情况下，上述方法会增加程序的运行时间，如果您关心运行时间并且了解哈希列表，则此方法更好。

#include <unordered_set> // at top

bool validPath_helper(int n, int source, int destination, vector<bool> visited, vector<unordered_set<int>> adjList){
    visited[source] = true;

    if(adjList[source].find(destination) != adjList[source].end()){
        return true;
    }

    for(int i: adjList[source]){
        if (!visited[i] && validPath_helper(n, i, destination, visited, adjList)) {
            return true;
        }
    }
    return false;
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<bool> visited(n, false);
    vector<unordered_set<int>> adjList(n); 

    int u, v;
    for(int i=0; i<edges.size(); i++){
        u = edges[i][0];
        v = edges[i][1];
        adjList[u].insert(v); 
        adjList[v].insert(u);
    }

    return validPath_helper(n, i, destination, visited, adjList);
}

您的代码中还有更多错误：

1. 两个函数中都有一些不必要的循环。
2. 您将访问设置为 true，但在新节点上调用 DFS 之前不检查它。
3. 您返回第一个 DFS 结果并且不检查其他子节点。 （由于在 validPath_helper 函数中返回 validPath_helper 调用。

也请研究这些问题，如果您遇到困难，请参阅上面的方法＃2。