Это моя первая статья на Medium, поэтому, если я допустил какую-либо ошибку или неверное утверждение, сообщите мне об этом в поле для комментариев.
Целевой аудиторией является новичок в информатике. Я собираюсь объяснить немного больше о поиске в глубину.
Предварительные требования: основы представления графа и концепция стека.
Акроним поиска в глубину — DFS. В CS DFS — очень популярный алгоритм теории графов, который на самом деле решает множество реальных задач.
Основная идея DFS состоит в том, чтобы начать посещение с исходного узла и поместить его в стек. Затем возьмите верхний элемент из стека и извлеките его из стека. Исследуйте весь дочерний элемент недавно выскочившего элемента из стека и продолжайте помещать дочерний элемент в стек. Повторяйте это, пока стек не станет пустым. Этот подход будет отлично работать, если у нас есть направленный ациклический граф. Но если у нас есть неориентированный граф, то этот подход создаст проблему, потому что может быть возможно, что мы помещаем в стек тот же узел, который уже присутствует в стеке, вызывая бесконечный запуск. временная сложность алгоритма. Итак, чтобы сделать его эффективным алгоритмом времени работы, мы создадим контейнер, который сообщает о текущем состоянии узла.
Статус означает просто проверить, был ли этот узел посещен или нет до сих пор, если посещен, не помещайте его в стек, в противном случае поместите его в стек.
Алгоритм:
Шаг -1: Возьмите логический контейнер или массив размером с количество узлов в графике и сделайте все позиции ложными, что просто означает, что изначально все узлы не посещаются.
Шаг 2: поместите исходный узел в стек и пометьте его как посещенный узел в логическом массиве.
Шаг 3: вытащите верхний элемент стека
Шаг -4: Распечатайте всплывающий элемент
Шаг 5: Исследуйте все дочерние узлы узла и проверьте, не является ли он не посещенным, поместите его в стек и пометьте как посещенный, в противном случае отбросьте его.
Шаг -6: Повторяйте шаги 3,4 и 5, пока стек не станет пустым, и, наконец, мы получим порядок dfs узла данного графа.
Код:
DepthFirstSearh(Graph , srcNode, numOfNode)
{
bool посещено[numOfNode] = {flase};
Стек;
s.push(srcNode);
visited[srcNode] = true;
пока(!isEmpty(s))
{
currentTop = s.top(); s.pop()
print(currentTop);
foreach(дочерний элемент в Graph[currentTop])
{
если(!посетили[ребенка])
s.push(дочерний); посещенный[ребенок] = правда;
}
}
}
Приложения:
- Вычисление общего количества несвязных компонент графа.
- Проверьте возможность достижения пункта назначения из источника.
- Решить задачу коммивояжера.
- Обнаружение цикла в графе.
