c - 如何结束DFS的迭代

Question

我正在尝试在 C 中的图形上实现 DFS，但是当我到达不再有未访问成员可用的节点时，我正在努力解决如何回溯问题。我已经尝试了所有我能想到的可能的解决方案，但没有成功。在此先感谢您的帮助。

void dfs_iter(int** graph, int* marks, int gsize, int i, NODE** stck)
{
    push_stack(st, i);
    marks[i] = 1;
    printf("%d ", i);

    while (!test_stack(*stck)) {
        int current = data_stack(*stck);
        int k;
        for (k = 0; k < gsize; k++) {
        if ((graph[current][k] == 1)) {
            if (marks[k] == 0) {
                push_stack(stck, k);
                marks[k] = 1;
                printf("%d ", k);
                break;
            } else {
                int l, is_route = 0;
                for (l = k; l < gsize; l++) {
                    if (graph[current][l] == 1 && !marks[l]) {
                        is_route = 1;
                    }
                }
                if (!test_stack(*st) && !is_route)
                    pull_stack(st);
                }
            }
        }
    }
}

这是我尝试对其进行 DFS 的图:

0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 1 0 0

Answer 1

首先，我强烈建议您从 DFS 的典型实现开始，它是递归的。

1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

这有助于可视化 DFS 的实际工作原理。请注意，访问节点时要做的第一件事是将其标记为已访问。要跟踪已访问/未访问的节点，您可以创建一个数组，其中图中的每个节点有一个领域。如果该字段为 0 - 尚未访问过。如果为 1 - 它已经被访问过(当然这只是一种可能的实现)。然后注意，你再也不会去访问过的节点(这意味着如果你在节点 X 中并且 Y 是 X 的邻居，那么如果 Y 被标记为访问过你就不会再次访问它，只需去检查下一个邻居。)然后查看迭代算法伪代码:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v ← S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

这里也一样:如果 v 还没有被标记为已访问，那么你只访问它。