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

Question

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

我尝试调试程序以检测我到底哪里出错了，但我不知道为什么我在 validPath 函数中调用 return validPath_helper(n, i, destination, visited, adjList); 函数后立即出现分段错误检查节点是否被访问后。

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

段错误通常是由于访问 un-allocated 内存而发生的，所以这是您应该首先调查的。你说 validPath_helper 触发了段错误，所以你应该检查那个函数。

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

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，因此没有要检查的第 4 个元素（3 是索引，因此是第 4 个元素）。这是您的段错误的原因。

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

您可以通过多种方式解决此问题。

方式#1

而不是

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

尝试

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);
}

您的代码中还有几个错误：

你的两个函数中都有一些不必要的循环。
您将 visited 设置为 true 但在新节点上调用 DFS 之前未检查它。
你return第一个DFS结果，不检查其他子节点。（由于 return validPath_helper 调用了 validPath_helper 函数。

也看看这些问题，如果卡住了，请参考上面的方式#2。

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

Finding if a path exists between two Nodes in a Graph using Depth First Search(DFS) C++

c++

recursion

graph

depth-first-search

graph-traversal

方式#1

方式#2