樹邊緣和正向邊緣之間的區別

當我遇到此問題時，我正在閱讀一本書：如何從DFS中的特定頂點的發現和完成時間中區分正向邊和樹邊？在它上面運行？樹邊緣和正向邊緣之間的區別

我到目前爲止所嘗試的是：Fwd之間的主要區別。並且樹邊緣是如果在A和B之間存在樹邊緣，則A是B的直接鄰居，其路徑長度爲1，但是如果是Fwd。邊緣，那麼路徑長度應該大於1左右。因此，當分析可以存儲在數組中的發現和完成時間時，我們可以檢查它們的完成時間/開始時間是否相差1。因爲如果它們這樣做，那麼它就是樹邊緣，否則就是前沿。

但是，我無法開發算法，也懷疑這種方法是一個錯誤的方法。請幫助我。謝謝。

來源

2015-03-31 Cartoon

雖然這樣做有向圖的深度優先搜索，

如果訪問一個新節點V（V還沒有被發現之前）從u
比（u，v）是樹的邊緣。
否則，如果我們訪問一個節點U已經訪問過的早期
- 如果我們還沒有離開/從該節點完成（V），比肯定v是 ü的祖先和（U， v）後邊緣。
- 否則，有兩種可能性 - 交叉邊緣或前緣。在這兩種情況下，我們訪問我們已經離開的節點（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-28 09:32:43

如果discoveryTime（v）已經在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）行）包括在一起。

來源

2015-04-20 13:31:26 stephan

樹邊緣和正向邊緣之間的區別

回答

相關問題