0

下面是 DFS 的通用代码，带有用于标记后边缘和树边缘的逻辑。我的疑问是来自顶点的后边返回并指向祖先，而指向父节点的后边不是后边（让我们假设无向图）。在无向图中，我们在 2 个顶点 x 和 y 之间来回有一条边。因此，在我处理 y 时访问 x 后，y 将 x 作为相邻顶点，但由于它已经被访问过，代码会将其标记为后边缘。

我这样说对吗？如果我的假设有效，我们是否应该添加任何额外的逻辑来避免这种情况？

DFS(G)
for v in vertices[G] do
    color[v] = white    
    parent[v]= nil
    time = 0        

for v in vertices[G] do
    if color[v] = white then
    DFS-Visit(v)

Induce a depth-rst tree on a graph starting at v.

DFS-Visit(v)
    color[v]=gray
    time=time + 1
    discovery[v]=time
    for a in Adj[v] do
       if color[a] = white then
        parent[a] = v
        DFS-Visit(a)
        v->a is a tree edge
       elseif color[a] = grey then  
        v->a is a back edge
    color[v] = black
    time = time + 1

白色表示unexplored，灰色表示frontier，黑色表示processed

4

1 回答 1

0

是的，此实现frontier仅通过颜色（已访问，未访问）确定节点，因此不分离父节点和祖先节点。因此，DFS 搜索树中的每条边都将被标记为后边。

为了分离树边缘和后边缘，您需要将边缘与父节点和祖先节点分开。简单的方法是将父节点作为参数提供给 DFS-Visit ( p)。例如：

DFS-Visit(v, p)
 color[v]=gray
 time=time + 1
 discovery[v]=time
 for a in Adj[v] do
   if color[a] = white then
       parent[a] = v
       DFS-Visit(a,v)
       v->a is a tree edge
   elseif color[a] = grey and (a is not p) then
       v->a is a back edge
 color[v] = black 
 time = time + 1

更新：我没有注意到您已经存储了父节点。因此，无需引入参数：

DFS-Visit(v)
 color[v]=gray
 time=time + 1
 discovery[v]=time
 for a in Adj[v] do
   if color[a] = white then
       parent[a] = v
       DFS-Visit(a)
       v->a is a tree edge
   elseif color[a] = grey and (a is not parent[v]) then
       v->a is a back edge
 color[v] = black 
 time = time + 1
于 2012-12-12T07:53:32.533 回答