До и после номера

Question

При использовании depth first search на Directed Graph что имеется в виду под номерами 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++; 

значения до и после имеют много значения. Классификация краев - один из таких примеров. Также вы можете использовать значения столбцов, в которые попадают источники и поглотители.