1

この質問に出くわしたとき、私は本を読んでいました: DFS が実行されているときに、グラフ内の特定の頂点の検出時間と終了時間から、前方エッジとツリー エッジの違いをどのように見分けることができますか?

私がこれまでに試みたことは次のとおりです。 Fwd との主な違い。Tree Edges は、A と B の間にツリー エッジが存在する場合、A は経路長 1 の B の直接の隣人ですが、Fwd の場合です。エッジの場合、パスの長さは 1 程度よりも大きくする必要があります。そのため、配列に格納できる検出時刻と終了時刻を分析すると、それらの終了時刻と開始時刻が 1 異なるかどうかを確認できます。そうである場合、それはツリー エッジであり、そうでない場合は前方エッジです。

しかし、私はアルゴリズムを開発することができず、このアプローチがバグのあるものであることも疑っています. 私を助けてください。ありがとうございました。

4

2 に答える 2

4

有向グラフで深さ優先探索をしているときに、

  1. u から新しいノード v (v は以前に発見されていない) にアクセスした場合、
    (u,v) はツリー エッジです。

  2. そうでなければ、すでに以前にアクセスしたノード v にアクセスした場合

    • そのノード (v) からまだ出発/終了していない場合、確かに v は u の祖先であり、(u,v) はバック エッジです。

    • それ以外の場合は、クロス エッジまたはフォワード エッジの 2 つの可能性があります。どちらの場合も、すでに出発したノード (v) にアクセスします。ここでは、到着時刻を使用してそれらを区別できます。

      • u の到着時間が v よりも小さい場合、これは前方エッジ (先祖から子孫へ、u -> v) です。

      • u の到着時間が v よりも大きい場合、それはクロス エッジです。

参考のため：

void dfsEdges(struct graph*G, int v, int *visited, int *arrTime, int *depTime)
{
 static int time=0;


visited[v]=1;
arrTime[v]=time++;

struct node *temp = G->array[v];
while(temp!=NULL)
{
    if(visited[temp->val] != 1)
    {
        dfsEdges(G,temp->val,visited,arrTime,depTime);
    }
    else
    {
        if(depTime[temp->val] ==-1)
        printf("\n%d - %d is back edge\n",v,temp->val);
        else
        {
            if(arrTime[v]<arrTime[temp->val])
            printf("\n%d - %d is forward edge\n",v,temp->val);
            else
            printf("\n%d - %d is cross edge\n",v,temp->val);
        }

    }
    temp=temp->next;

}
depTime[v]=time++;

}
于 2015-04-28T09:32:43.037 に答える
0

v の観測時に DiscoveryTime(v) が既に定義されていて、discoveryTime(u) <= discoveryTime(v) である場合、エッジ (u, v) は前方エッジに分類されます。したがって、エッジ (u, u) も前方エッジとして分類されます。分類は、DFS が頂点を通過した順序に基づいています。つまり、別の頂点から開始すると、異なる分類になる可能性があります。疑似コードのアルゴリズム (説明と証明付き) は、Kurt Mehlhorn: Data Structures and Efficient Algorithms, Volume 2, Springer Verlag, EATCS Monographs, 1984. (絶版ですが、著者によりオンラインで入手可能) に記載されています。以下に示すように、第4章「グラフのアルゴリズム」、21ページ。25ページのフラグメントをエッジ分類とともに含めました（著者が提案したように、行（8）から（10））。

[1] によるエッジ分類による DFS アルゴリズム

于 2015-04-20T13:31:26.250 に答える