Реализация обхода графа в глубину - PullRequest
Новая
       46

Реализация обхода графа в глубину

3 голосов
/ 23 апреля 2011

У меня есть противоречивая информация о первом обходе глубины, и я мог бы помочь понять, как построить программу. Учитывая определенный граф, я хочу напечатать последовательность вершин. Пользователь будет вводить конкретный узел, с которого начинается обход. Я смотрю на разные примеры и не понимаю, как работает порядок обхода в глубину. У меня есть следующий псевдокод для работы: 

public DFS() {
    DFS(v)
    {   num(v) = i ++;
       for all vertices u adjacent to v
       { if num(u) is 0
            attach edge(uv) to edges;
            DFS(u);
        }
    }



depthFirstSearch()
{     for all vertices v
        num(v) = 0;
  edges = null; //vector of all edges
  i=1;
  while there is a vertex v such that num(v) is 0
         DFS(v);
  output edges;
}

1 Ответ

2 голосов
/ 23 апреля 2011

Ключом к обоим из этих фрагментов является следующая идея: 

check if item found at (v)
if item not found,
   for all vertices u adjacent to v
     depth_first_search(u)

Вместо того, чтобы сразу проверять конечное условие для всех дочерних узлов (v) (списка), вы проверяете толькодля него в текущем узле v. Если конечное условие не выполнено, вы применяете ту же самую глубину первой функции поиска, начиная с первого потомка v, u1.Поскольку у u1 также могут быть дочерние элементы, та же самая функция будет применена к дочерним элементам u1 до обработки оставшихся дочерних элементов v и т. Д.Вот почему он называется поиском по глубине, так как ваш поиск сначала ищет самый низкий набор дочерних элементов в пути, а затем возвращается, чтобы проверить оставшихся дочерних элементов.

...