1

例如。对于 1->2、2->3、3->4、4->2，我想打印 2、3、4。我尝试了 DFS，当我找到之前访问过的顶点时，我去父级直到我不要得到这个顶点，但它不能很好地工作。有时它会进入无限循环。

运行dfs：

int i;
for (i = 0; i < MAX_VER; i += 1)
    if (ver[i].v == 0 && ver[i].nb > 0)
        dfs(i);

dfs:

ver[v].v = 1;

int i;
for (i = 0; i < ver[v].nb; i += 1) {
    ver[ver[v].to[i]].p = v;

    if (ver[ver[v].to[i]].v == 0)
        dfs(ver[v].to[i]);
    else
        // cycle found
        printCycle(ver[v].to[i]);
}

和打印周期：

printf("\cycle: %d ", v);

int p = ver[v].p;

while (p != v) {
    printf("%d(%d) ", p, v);

    p = ver[p].p;
}

printf("\n");

顶点结构：

int *to; // neighbor list

int nb; // how many neighbor
int p; // parent
short v; // was visited? 0 = false, 1 = true
4

2 回答 2

1

听起来您正在寻找“强连接组件” - 所以您很幸运，有一个众所周知的算法可以在图中找到这些。见塔利安。

该算法在那篇文章中有很好的描述，但是有点冗长，所以我不会在这里粘贴。此外，除非您这样做是为了学习，否则使用现有的实现可能会更好，实现起来并不难，但也不是那么容易。

编辑。看起来这个问题实际上是一个骗局......这让我很痛苦，但它可能需要关闭，抱歉。请参阅在有向图中检测循环的最佳算法

于 2012-05-03T08:58:42.973 回答
0

您应该使用顶点着色来避免 DFS 中的无限循环。首先，所有顶点都标记为白色。当您第一次发现一个顶点时（它被标记为白色），您应该将它标记为灰色。如果你发现了一个灰色顶点，你会发现一个循环。

于 2012-05-03T10:02:32.787 回答