前期和後期號碼

Question

當在Directed Graph上做depth first search什麼是pre和post數字？

例如：

如果你開始在節點A，做一個字母Depth First Search你如何確定前置和後置的數字？

Answer 1

注意：雖然這個問題在很久以前就被問過了，但它可能會被別人引用。

深度優先搜索的前後值分別描述訪問的開始時間和訪問頂點的結束時間。在開始的時候，我指的是頂點被發現的時間，結束時間意味着所有孩子（在DFS樹中）將被訪問的時間。

下面是DFS-

dfs(Graph, Vertex) 

    static count = 1 
    pre[Vertex] = count++ 
    visited[Vertex] = true 

    for all v in Edge(Vertex, v) 
     if visited[v] = false 
      dfs(Graph, v) 

    post[Vertex] = count++; 

樣本僞前置和後置值有很大的意義。邊緣分類就是這樣一個例子。您還可以在源圖片和匯點圖片中找到後期值的使用。