在skiena的书中给出的dfs应用程序在图中查找循环的代码中出现错误 [英] error in the code given in skiena's book for the application of dfs to find a cycle in a graph

问题描述

这是dfs的代码。

  bool processed [MAXV + 1]; / *哪些顶点已经被处理* / 
 bool被发现[MAXV + 1]; / *哪些顶点已被找到* / 
 int parent [MAXV + 1]; / *发现关系* / 
 #define MAXV 1000 / *最大顶点数量* / 
 
 typedef struct {
 int y; / * adjacency info * / 
 int weight; / *边权重，如果有的话* / 
 struct edgenode * next; / *列表中的下一个边* / 
} edgenode; 
 
 typedef struct {
 edgenode * edges [MAXV + 1]; / * adjacency info * / 
 int degree [MAXV + 1]; / *每个顶点的outdegree * / 
 int nvertices; / *图中顶点的数量* / 
 int nedges; / *图中的边数* / 
 bool定向; / *是指向的图形？ * / 
}图表; 
 
 dfs（graph * g，int v）
 {
 
 edgenode * p; / *临时指针* / 
 int y; / *后继顶点* / 
 if（finished）return; / *允许搜索终止* / 
发现[v] = TRUE; 
 time = time + 1; 
 entry_time [v] = time; 
 process_vertex_early（v）; 
 p = g->边缘[v]; 
 while（p！= NULL）{
 y = p-> y; 
 if（发现[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->下; 
 
} 
 process_vertex_late（v）; 
 time = time + 1; 
 exit_time [v] =时间; 
已处理[v] = TRUE; 
} 
  

为了寻找周期，它修改了如下的过程边界函数

  process_edge（int x，int y）
 {
 if（parent [x]！= y）{ / *发现后面的边缘！ * / 
 printf（从％d到％d的循环：，y，x）; 
 find_path（y，x，parent）; 
 printf（\\\
\\\
）; 
 finished = TRUE; 
 
 
 $ / code> 

现在想象一个只有2个叶节点的小树，一根。
当这棵树受到这个函数的支配时，我相信它会说它有周期。
这是错误的！
如果我错了，请纠正我。
Thanks。


解决方案

从勘误表中，在 http://www.cs.sunysb.edu/~skiena/algorist/book/errata ：

（*）第173页，process_edge程序 - 正确的测试应该是

if（发现[y]&&（parent [x]！= y））{/ *发现后沿* /

This is the code for 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;
}

And for finding the cycles it has modified the process edge function like below

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;
    }
}

Now imagine a small tree with just 2 leaf nodes and one root. When this tree is subjected to this function, I believe it will say that it has cycles. which is wrong !! Please correct me if i am wrong. Thanks.

解决方案

From the errata corrige, at http://www.cs.sunysb.edu/~skiena/algorist/book/errata:

(*) Page 173, process_edge procedure -- the correct test should be

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

这篇关于在skiena的书中给出的dfs应用程序在图中查找循环的代码中出现错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！