algorithm - Skienna DFS 算法

Question

以下是 Skiena'a 算法设计手册中提供的 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] && (parent[v]!=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;
}

我觉得支票:

else if ((!processed[y] && (parent[v]!=y) ) || (g->directed))
  process_edge(v,y);

可以简单地是:

else if ((parent[v]!=y ) || (g->directed))
    process_edge(v,y);

我看不出在代码中此时 processed[y] 怎么可能永远是 true。在无向图上的 DFS 中，标记为已处理的节点可能已经遍历了它的所有后代，所以事实上，在代码中的那个点，我们正在通过尚未处理的节点的边到达 y , 使得 y 不可能已经被处理。如果 Skiena 代码是正确的，并且 processed[y] 检查是正确性所必需的，那么我在这里缺少什么？您能否举一个需要该条件的示例 - 我无法想象？

Answer 1

这是必要的。设图为三个顶点的无向环路。

dfs 可以按以下顺序进行:1 -> 2 -> 3。当我们回到 1 时(在处理完 2 和 3), 3 有一条边，但是 3 被处理了，所以检查是必要的。