Depth First Search

Алгоритм "Обход в глубину (Depth first search)".
Суть заключается в таком обходе графа потока управления, при котором обработка потомка узла графа происходит раньше, чем обработка любого родственного узла( родственный узел имеет того же родителя, что и данный узел).

Например для данного графа:
Узлы: 1,2,3,4,5,6,7,8
Дуги: 1-2, 1-6, 2-3, 3-2, 3-4, 3-5, 4-5, 6-4, 6-7, 7-8, 8-7

Cледующий граф является depth-first представлением:
Узлы: 1,2,3,4,5,6,7,8
Дуги дерева: 1-2, 1-6, 2-3, 3-4, 4-5, 6-7, 7-8
Другие дуги: 3-2(B), 3-5(F), 6-4(C), 8-7(B)

Номера, присвоенные узлам при обходе в глубину, называются DFO номерами узлов.
Depth-first представление включает depth-first spanning tree (все узлы графа, и такие дуги графа, которые переводят граф в дерево) , и остальные дуги, которые не используются при обходе в глубину (можно нарисовать пунктиром).
Дуги, принадляжащие depth-first spanning tree называются tree edges
Остальные дуги разделяются на 3 класса:

  • forward edges(F) - от узла к прямому наследнику, но не являются tree edges
  • back edges (B) - от узла к к одному из предков узла
  • cross edges (C) - связывают узлы, ни один из которых не является предком другого

Заметим, что depth-firt spanning tree может определяться неоднозначно. Например для данного графа
Узлы A,B,C,D
Дуги: A-B, B-D, B-C, A-C

Оба следующих представления являются depth-firt spanning tree
Узлы: A,B,C,D
Дуги: A-B, B-D, B-C

Узлы: A,B,C,D
Дуги: A-C, A-B, B-D

Данный алгоритм строит depth-first представление:

4 интерфейсы для выполнения обработки узла графа:
1. Process_Before() - действия до посещения узла
2. Process_After() - действия после посещения узла
3. Process_Succ_Before() - действия до посещения потомка узла
4. Process_Succ_After() - действия после посещения потомка узла

N: set of Node
r,i: Node
Visit: Node --> boolean

procedure Depth_First_Search(N,Succ,x)
    N: in set of Node
    Succ: in Node --> set of Node
    x: in Node
begin:    
    y: Node
    Process_Before(x)
    Visit(x) := true
    for each y in Succ(x) do
        if !Visit(y) then
            Process_Succ_Before(y)
            Depth_First_Search(N,Succ,y)
            Process_Succ_After(y)
        fi
    od
    Process_After(x)
end || Depth_First_Search

begin
    for i in N do
        Visit(i) := false
    od
    Depth_First_Search(N,Succ,r)
end

Обход в прямом порядке, обход в ширину (Preorder traversal)
Суть обхода заключается в обработке потомка узла графа после обработки узла, и всех родственных узлов, при этом не рассматриваются обратные дуги (B). Номера, присвоенные узлам при таком обходе, называются RPO номерами.

Обход в обратном порядке, обход в глубину (Postorder traversal)
Суть обхода заключается в обрабоке узла после обработки всех его потомков, при этом не рассматриваются обратные дуги (B).

Литература
*wikipedia.org
*Steven S. Muchnik "Advanced Compiler Design Implementation"

ЕСЛИ КТО-ТО ЗАМЕНИТ ТЕКСТОВОЕ ПРЕДСТАВЛЕНИЕ ГРАФОВ КАРТИНКАМИ, БУДУ ТОЛЬКО РАД. У МЕНЯ НЕТ ВРЕМЕНИ РИСОВАТЬ КАРТИНКИ
\\dimstar

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.