例如。对于 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