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 已被处理，因此需要进行检查。

Skienna DFS 算法

Skienna DFS algorithm

algorithm

graph

depth-first-search