2
A
回答
2
您可以使用DFS橫向全圖的邊分類:
DFS-Visit(u) ▷ with edge classification. G must be a directed graph
1. color[u] ← GRAY
2. time ← time + 1
3. d[u] ← time
4. for each vertex v adjacent to u
5. do if color[v] ← BLACK
6. then if d[u] < d[v]
7. then Classify (u, v) as a forward edge
8. else Classify (u, v) as a cross edge
9. if color[v] ← GRAY
10. then Classify (u, v) as a back edge
11. if color[v] ← WHITE
12. then π[v] ← u
13. Classify (u, v) as a tree edge
14. DFS-Visit(v)
15. color[u] ← BLACK
16. time ← time + 1
17. f[u] ← time
正如你可以看到here。
1
您也可以使用時鐘而不是顏色。這似乎更容易。 下面是實現該方法的方法: 但是我會在c中發佈答案,因爲我還不知道C++,因此您必須將其轉換爲C++。
void DFS(Graph* G){
int v;
for (v=0; v < G->n; v++)
visited[v]=FALSE;
for (v=0; v < G->n; v++){
if (!visited[v])
Traverse(G, v);
}
}
void Traverse(Graph* Gr, int v){
int w;
Edge *current;
start[v]=clock; //We are going to classify the edges by the time they were visited
clock++;
visited[v]=TRUE;
current=Gr->stpoint[v];
while (current){
w=current->vertex;
if (!visited[w]) {
printf("%d %d: Tree edge\n",v,w); //If w is not visited then mark v-w as a tree edge
if(!current)
Traverse(Gr, w);
}
else{
if((start[v] > start[w]) && (end[v] < end[w])) //v was visited after w
printf("%d %d: Back edge\n",v,w);
else if ((start[v] < start[w]) && (end[v] > end[w])) //v was visited before w
printf("%d %d: Forward edge\n",v,w);
else if ((start[v] > start[w]) && (end[v] > end[w])) //
printf("%d %d: Cross edge\n",v,w);
}
end[v]=clock;
clock++;
current=current->next;
}
}
相關問題
- 1. 查找圖形中的所有邊類型。樹,向前,向後或交叉邊緣
- 2. 如何在正交圖中組合邊?
- 3. 如何從OpenStreetMap中找到交叉點?
- 4. 在圖像上找到交叉
- 5. 交叉應用查找所有日期
- 6. java函數可以找到最小邊交叉點的圖形
- 7. 查找有向圖和無向圖中的所有循環
- 8. 如何在邊緣找到交點
- 9. 最小化圖中的交叉邊
- 10. 圖中的邊緣交叉減少
- 11. 在Internet Explorer中缺少圖像交叉和邊框
- 12. KineticJS得到所有的交叉點
- 13. UIBezierPath找到交叉點/獲取所有點
- 14. Graphviz交叉邊緣
- 15. 交叉編譯systemd:cap_init沒有找到
- 16. 如何在有向圖中找到包含某個頂點的所有循環?
- 17. 如果圖形具有交叉邊緣,是否單獨連接
- 18. 與最小查找的圖形分區邊線交叉分區
- 19. 在繪圖引擎中找到交叉線
- 20. 爲什麼交叉譜在mlab和scipy.signal中有所不同?
- 21. 如何找到無向圖中兩條邊的相等性?
- 22. 如何在多步驟嚮導中找到所有控件?
- 23. 找到路徑交叉矩陣,最大總和向前然後向後
- 24. 交叉點和多邊形的聯合
- 25. 從交叉框找到一個固體多邊形的算法?
- 26. Android:找到一條線和一個圖像的交叉點
- 27. 在有向圖中尋找邊緣不相交路徑的最大數量
- 28. 找到所有由線交點形成的多邊形
- 29. 如何在Magento中找到沒有圖像的所有產品?
- 30. 雙向交叉ANOVA R中