В ДФС , исследуемые узлы хранятся в структуре данных стека. Ребра, которые направляют нас к неисследованным узлам, называются ‘ края обнаружения ‘ в то время как ребра, ведущие к уже посещенным узлам, называются ‘ края блока '. ДФС полезен в сценариях, когда программист хочет найти связанные компоненты или циклы в графе.
Следуйте рекомендациям этой статьи, чтобы внедрить ДФС в С++.
Реализация DFS на C++
В следующем разделе мы рассмотрим, как ДФС реализован на С++. Можно выполнить указанные шаги для реализации ДФС .
- Вставьте корневой узел дерева или графа в стек.
- Добавьте верхний элемент стека в список посещений.
- Обнаружить все соседние узлы с посещенным узлом и добавить те узлы, которые еще не посетили стек.
- Повторяйте шаги 2 и 3, пока стек не станет пустым.
Псевдокод DFS
ДФС псевдокод показан ниже. в нагревать() функцию, мы выполняем нашу ДФС функция на каждом узле. Поскольку граф может состоять из двух несвязанных частей, мы можем запустить ДФС алгоритм на каждом узле, чтобы убедиться, что мы покрыли каждую вершину.
ДФС ( г а )
а. посетил '=' истинный
для каждое b ∈ g. Прил. [ а ]
если б. посетил == ЛОЖЬ
ДФС ( г, б )
нагревать ( )
{
Для каждого a ∈ g
а. посетил '=' ЛОЖЬ
Для каждого a ∈ g
ДФС ( г, а )
}
Здесь g, a и b представляют граф, первый посещенный узел и узел в стеке соответственно.
Реализация DFS на C++
Программа на С++ для ДФС реализация приведена ниже:
#include
#include<карта>
#include<список>
с использованием пространство имен станд. ;
шаблон < имя типа т >
сорт Глубина первого поиска
{
частный :
карта < т, список < т > > adjList ;
публичный :
Глубина первого поиска ( ) { }
пустота Add_edge ( т а, т б, логический ты '=' истинный )
{
adjList [ а ] . отталкивать ( б ) ;
если ( ты )
{
adjList [ б ] . отталкивать ( а ) ;
}
}
пустота Распечатать ( )
{
для ( авто я : adjList ) {
cout << я. первый << '->' ;
для ( вход : я. второй ) {
cout << вход << ',' ;
}
cout << конец ;
}
}
пустота dfs_helper ( т узел, карта < т, логический > & посетил ) {
посетил [ узел ] '=' истинный ;
cout << узел << ' ' << конец ;
для ( сосед : adjList [ узел ] ) {
если ( ! посетил [ сосед ] ) {
dfs_helper ( сосед, посетил ) ;
}
}
}
пустота ДФС ( т источник )
{
карта < т, логический > посетил ;
dfs_helper ( src, посетил ) ;
}
} ;
инт основной ( ) {
Глубина первого поиска < инт > г ;
г. Add_edge ( 0 , 5 ) ;
г. Add_edge ( 0 , 7 ) ;
г. Add_edge ( 4 , 7 ) ;
г. Add_edge ( 7 , 8 ) ;
г. Add_edge ( 2 , 1 ) ;
г. Add_edge ( 0 , 6 ) ;
г. Add_edge ( 2 , 4 ) ;
г. Add_edge ( 3 , 2 ) ;
г. Add_edge ( 3 , 6 ) ;
г. Add_edge ( 7 , 5 ) ;
г. Add_edge ( 5 , 8 ) ;
г. Распечатать ( ) ;
г. ДФС ( 6 ) ;
cout << конец ;
}
В этом коде мы реализовали ДФС алгоритм, следующий псевдокоду, приведенному выше. У нас есть 12 пар узлов. Мы определили класс « г », который представляет собой граф с вершинами a и b, представляющими посещенные и непосещенные узлы.
Выход
Заключение
ДФС — популярный алгоритм поиска, полезный для нескольких сценариев, таких как поиск циклов в графе и получение информации о связных компонентах или всех вершинах в графе. Мы также описали работу ДФС метод с примером. ДФС использует стеки для выполнения этой техники, а также может использоваться на деревьях.