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つのリーフノードと1つのルートを持つ小さなツリーを想像してみてください。この木がこの機能を受けると、周期があると言えると思います。これは間違っています!! 私が間違っている場合は私を訂正してください。ありがとう。

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にあるが、以前に検出されたノードへのエッジを処理しないことです。では、彼はどのようにしてサイクルを見つけるのでしょうか？！サイクル（または何らかの理由でバックエッジ）に関心がある場合は、すべてのエッジを処理する必要があると思います。

バックエッジに興味がなく、バックエッジの処理を避けたい場合は、表示されているコードが正しいです。

彼が書いたテキストの「FindingCycles」セクションの直前の箇所で、それは非常に皮肉なことです。

深さ優先探索ベースのアルゴリズムの微妙さは、実装しようとするたびに頭を悩ませます。

本当なの！：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！）になります。2番目の条件が削除された場合、アルゴリズムが子（y）からその親（x）に向かうエッジを（無向グラフで）以前の祖先の1つに戻るエッジとして検出する可能性があります。これは完全に間違っています。

于 2016-06-16T11:50:09.750 に答える