在彩色图上执行 DFS 时出现分段错误

Question

这是我的代码：

#include <bits/stdc++.h>

using namespace std;
#define limt 101

//edge stores the edges for each node
//since it is defined outside main, i don't think it is the cause for
//segmentation fault

vector<int> edge[limt][limt];
int vist[limt], tgt;

//dfs call for a node numbered <i>u</i>
//and for only the edges colored <i>c</i>
int dfs(int u, int c)
{
   if (u == tgt) return 1;

   vist[u] = 1;

   for (int i = 0; i < edge[u][c].size(); ++i) {
      if (dfs(edge[u][c][i], c)) return 1;
   }

   vist[u] = 0;
   return 0;
}

int main()
{
   //n : number of nodes
   //m: number of edges
   //c: color of edge
   int n, m;
   int u, v, c;
   cin >> n >> m;
   for (int i = 0; i < m; ++i) {
      cin >> u >> v >> c;
      edge[u][c].push_back(v);
      edge[v][c].push_back(u);
   }
   //q: number of queries/test-cases
   int q, x, y;
   cin >> q;
   while (q--) {
      cin >> x >> y;
      memset(vist, 0, sizeof(vist));
      int ans = 0;
      vist[x] = 1;
      tgt = y;

      //program crashes for second test-case after reaching here

      //i - the color of edge
      //j - all the edges from x of color i
      for (int i = 0; i < limt; ++i) {
         for (int j = 0; j < edge[x][i].size(); ++j) {
             ans += dfs(edge[x][i][j], i);
         }
      }
      vist[x] = 0;
      cout << ans << endl;
   }

   return 0;
}

我给出的输入是：

这里的q是测试用例的数量，第一个用例运行正常，给出输出2但是在第二个用例程序上因分段错误而崩溃。我不知道它有什么错误。我确定我不会造成任何溢出，因为声明在 main().

之外

Answer 1

第二种情况，dfs函数导致无限递归。

第一个调用是 dfs(u=2, c=1);，它调用 dfs(u=1, c=1);，它调用 dfs(u=2, c=1); 等等令人作呕。

如果您运行在调试器中编写代码，您应该能够通过在分段错误点输出堆栈跟踪来查看发生了什么。

这是一张由您的数据生成的图表（颜色为 1=红色，2=绿色，3=蓝色）：

main() 中的循环从 3 开始，跟随 Red 找到 2，然后调用 dfs(2, red);。（这已经有点奇怪了，因为您可以调用 dfs(3, red) 来获得相同的结果）。但是 dfs 函数紧随它找到的第一个红色边缘，所以它最终在 2 和 1 之间来回穿梭。

为避免这种情况，您需要添加一种方法让 dfs 知道不要重新访问它已经访问过的节点。事实上，您已经跟踪了 vist，但没有在 dfs 函数中检查它。

我认为只需将 if ( vist[u] ) return 0; 添加到该函数的开头即可解决此图表的问题。但是我认为你应该将每种颜色的所有 vist 重置为 0 ，而不仅仅是每个测试用例。例如，在此图中，如果从 2 到 4 有一条蓝色边，但从 3 到 4 没有，则搜索将永远找不到它，因为 2已在红色搜索期间标记为已访问。

在彩色图上执行 DFS 时出现分段错误

Segmentation fault while doing DFS on a coloured graph

c++

segmentation-fault

depth-first-search