前邊緣在無向圖

CLRS - 第22章前邊緣在無向圖

定理22.10

在深度優先搜索的無向圖G，G的每一條邊是採用樹邊緣或背邊緣。

證明設（u，v）是G的任意一條邊，並且假設沒有損失概率，即u.d < v.d.然後，搜索必須發現並完成v 才能完成u（而u是灰色的），因爲v在u的鄰接列表中。如果第一次搜索探測邊緣（u，v），它在從u到v的方向，則v未被發現（白色），直到時間，否則搜索將已經探索到該邊緣已經在從v到u的方向。因此，（u.v）成爲樹邊緣。如果搜索首先在從v到u的方向上探索（u，v），則（u，v）是後沿，因爲在邊緣首先探索時u仍然是灰色的。

我當然明白證據;但並不完全相信前沿的想法。

Undirected Graph

在上述圖像，存在從第一頂點到第三頂點（第一行）的前邊緣。第一個頂點是源。

據我瞭解DFS（S）將包括前頂點1 - > 3。（我顯然是錯誤的，但我需要有人把我直！）

來源

2013-11-10 p0lAris

看起來你不包括「前沿」的定義，所以我將從我學到的定義開始。

假設u.d < v.d，DFS標籤的邊（u，v）的一個渡從u到v的邊緣時前邊緣如果，V已被標記爲已訪問。

因此，我聲稱你不能在無向圖中有前向邊。

爲了矛盾，假設它是可能的。因此，目標節點已被標記爲已訪問。因此，DFS已經到了那裏並且越過了所有相鄰的邊緣。特別是，你必須已經在相反的方向越過那邊。因此，邊緣已被標記爲某種類型的邊緣，因此不會被標記爲「前沿」。

因此，前向邊緣只能出現在有向圖中。

現在，以防萬一你混了「前進邊緣」和「樹邊」，你描述還是邊緣不一定是樹的邊緣。如果穿越，這只是一個樹邊緣，那是您第一次訪問目的地節點。在無向圖中思考它的簡單方法是當遍歷邊時，如果已經到達了目標節點，則是後沿;否則是樹邊。

來源

2013-11-10 07:42:50

我相信你缺少的是關於算法訪問不同頂點的順序的一些假設。

讓我們假設算法以字典順序訪問頂點。讓我們命名的頂點是這樣的：

------- 
|  | 
S - A - B 
| | | 
C - D - E

在這種情況下，前邊緣會S->A，A->B，B->E，E->D，D->C。其餘的邊緣是後邊緣。

現在，讓我們重命名圖表：

------- 
|  | 
S - B - A 
| | | 
C - D - E

在這種情況下，前邊緣會S->A，A->B，B->D，D->C，D->E（注意：S->A和S->B是不一樣的邊緣在以前的例）。如您所見，輸出取決於算法選擇頂點的順序。當圖是匿名的時，任何輸出都可能是正確的。

來源

2013-11-10 07:48:34

在一般圖的DFS樹中，有TREE，FORWARD，BACK和CROSS邊。

在無向圖的DFS樹中，可能的FORWARD邊被標記爲BACK邊。將被CROSS邊緣標記爲TREE邊緣。

在這兩種情況下，原因是邊緣可以在兩個方向上遍歷，但你首先遇到它們作爲BACK和TREE，第二次遇到FORWARD，也許CROSS，它們已經被標記。

從某種意義上說，邊緣既是前向又是後向，既可以是十字形，也可以是樹形，但首先分別作爲BACK和TREE發現。

來源

2013-11-10 09:58:46 chill

前邊緣在無向圖

回答

相關問題