E23*_*235 3 algorithm depth-first-search graph-algorithm
给出graph G(V,E),
无方向图.
|E| = m, |V| = n
Run Code Online (Sandbox Code Playgroud)
图的数据结构是邻接列表
如何在复杂性中找到并打印简单循环(或打印没有这样的循环)O(n)
?
(如果有循环,则输出应该是循环的顶点列表.)
我知道如何找到复杂性的循环O(n)
,互联网上也有gudies.
我的问题是如何打印它.
这就是我试图做的事情:
DFS-CheckCycle ( Graph G)
{
p[] <- null //parent array
foreach v in V
Color[u] <- white
foreach v in V
{
if (Color[u] = white)
Visit(u)
}
}
Visit(Vertex u)
{
bool Cycle <- false;
Color[u] <- gray
foreach v in Adj[u]
{
p[v] <- u
if (Color[v] = white)
Visit(v);
else if (Color[v] = gray)
{
Cycle <- true;
break;
}
}
if(!Cycle)
print "No Cycle"
else
PrintCycle(v,u)
}
PrintCycle(Vertex v, Vertex u)
{
if(v = u)
print v;
else
{
print v;
PrintCycle(p[v], u);
}
}
Run Code Online (Sandbox Code Playgroud)
记住它需要O(n)
.
我的PrintCycle函数不会打印所有顶点.
我需要一些帮助如何打印我发现的循环的顶点.
我注意到你的算法中有两件似乎不正确的事情.首先,当您使用DFS步行时,您应该保持以下不变量:
Visit()
尚未结束的访问顶点应涂成灰色;Visit()
已返回的已访问顶点应涂成黑色(或颜色,灰色或白色除外).我注意到的另一件事是,您没有正确地为父节点分配节点.在您的Visit()
方法中,即使我们要在下一步中访问的顶点是灰色的,即在DFS树中已经有父节点,也会分配父节点.
所以我会相应地更改你的代码:
DFS-CheckCycle ( Graph G)
{
p[] <- null //parent array
foreach v in V
Color[v] <- white
foreach u in V
{
if (Color[u] = white) {
p[u] <- -1; // meaning it is a root of a DFS-tree of the DFS forest
Visit(u)
}
}
}
Visit(Vertex u)
{
bool Cycle <- false;
Color[u] <- gray
foreach v in Adj[u]
{
if (Color[v] = white) {
p[v] <- u
Visit(v);
}
else if (Color[v] = gray)
{
Cycle <- true;
break;
}
}
Color[u] <- black; // once DFS for this vertex ends, assign its color to black
if(!Cycle)
print "No Cycle"
else
PrintCycle(v,u)
}
PrintCycle(Vertex v, Vertex u)
{
if(v = u)
print v;
else
{
print v;
PrintCycle(p[v], u);
}
}
Run Code Online (Sandbox Code Playgroud)
编辑:将您的PrintCycle
方法转换为非递归方法可能是个好主意:
PrintCycle(Vertex v, Vertex u)
{
do {
print u;
u = p[u];
} while (u != v);
}
Run Code Online (Sandbox Code Playgroud)