4

这是dfs的代码。

bool processed[MAXV+1]; /* which vertices have been processed */
bool discovered[MAXV+1]; /* which vertices have been found */
int parent[MAXV+1]; /* discovery relation */  
#define MAXV 1000 /* maximum number of vertices */

typedef struct {
int y;                   /* adjacency info */
int weight;             /* edge weight, if any */
struct edgenode *next; /* next edge in list */
} edgenode;

typedef struct {
edgenode *edges[MAXV+1]; /* adjacency info */
int degree[MAXV+1];     /* outdegree of each vertex */
int nvertices;         /* number of vertices in graph */
int nedges;            /* number of edges in graph */
bool directed;        /* is the graph directed? */
} graph;

dfs(graph *g, int v)
{

   edgenode *p;           /* temporary pointer */
   int y;                /* successor vertex */
   if (finished) return; /* allow for search termination */
   discovered[v] = TRUE;
   time = time + 1;
   entry_time[v] = time;
   process_vertex_early(v);
   p = g->edges[v];
   while (p != NULL) {
         y = p->y;
         if (discovered[y] == FALSE) 
         {
             parent[y] = v;
             process_edge(v,y);
             dfs(g,y);
         }
         else if ((!processed[y]) || (g->directed))
         process_edge(v,y);
         if (finished) return;

       p = p->next;

}
   process_vertex_late(v);
   time = time + 1;
   exit_time[v] = time;
   processed[v] = TRUE;
}

为了找到循环，它修改了如下的过程边缘功能

process_edge(int x, int y)
{
    if (parent[x] != y) { /* found back edge! */
       printf("Cycle from %d to %d:",y,x);
    find_path(y,x,parent);
    printf("\n\n");
    finished = TRUE;
    }
}

现在想象一棵只有 2 个叶节点和一个根的小树。当这棵树受到这个函数的影响时，我相信它会说它有循环。这是错误的！如果我错了，请纠正我。谢谢。

4

4 回答 4

7

来自勘误表，位于http://www.cs.sunysb.edu/~skiena/algorist/book/errata：

(*) 第 173 页，process_edge 程序——正确的测试应该是

if (discovered[y] && (parent[x] != y)) { /* found back edge */

于 2013-05-26T16:47:05.270 回答
1

我认为你是对的，代码是错误的。

在我看来，问题出if (parent[x] != y)在process_edge(). 在对 的两个调用中，假定的父级在假定的子级之前process_edge()传递，即在内部我们期望成为父级，所以我认为该行应该是。process_edge()xif (parent[y] != x)

于 2012-12-15T03:57:19.157 回答
0

可悲的是，我认为这个 dfs 代码是错误的。自从我详细研究这些东西以来已经有很长时间了，但我认为很明显代码根本没有按照他说的那样做。

查找循环代码是正确的（正如 Antonio 所指出的，勘误表中显示了更改）。

主要问题是查找循环例程在 process_edge 中，但他没有将边缘处理到先前发现的节点！那么他将如何找到循环？！如果您对循环（或出于任何原因的后边缘）感兴趣，我认为您必须处理所有边缘。

如果您对后边缘不感兴趣并希望避免处理它们，那么所提供的代码是正确的。

具有讽刺意味的是，在正文中寻找周期部分之前的段落中，他写道：

我发现每当我尝试实现一个基于深度优先搜索的算法时，它的微妙之处都会让我大吃一惊。

你不说！:P

while 循环应如下所示：

...

while (p != NULL) {
    y = p.y;

    process_edge(v,y);

    if (discovered[y] == FALSE) {
        parent[y] = v;
        dfs(g,y);
    }

    if (finished) {
        return;
    }

    p = p.next;
}

...
于 2013-07-15T08:17:48.420 回答
0

在无向图中，只有树边和后边（没有前边或交叉边）。它是树边的充分条件是

if (discovered[y] == FALSE)

但是在已经发现的顶点的情况下，无向边有可能返回其父级（而不是其祖先）。为了防止这种情况，添加了另一个条件：

if (discovered[y]==TRUE && (parent[x] != y))

例如：y 已经被 x 发现（比如说）。当递归算法移动到顶点 y（x 的子节点）时，在这种情况下，顶点 X 现在是顶点 y，顶点 Y 是父节点（y）（或 x！）。如果第二个条件被删除，则算法有可能检测到从 child(y) 到其 parent(x) 的边（在无向图中）作为返回到前祖先之一的边，这是完全错误的。

于 2016-06-16T11:50:09.750 回答