c - skiena 书中给出的应用 dfs 在图中查找循环的代码错误

Question

这是 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 个叶节点和一个根的小树。当这棵树受制于这个函数时，我相信它会说它有循环。这是错误的!如果我错了，请纠正我。谢谢。

Answer 1

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

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

if (discovered[y] && (parent[x] != y)) {/* 找到后边 */