|
Даний алгоритм представляє собою рекурсивну функцію, яка проходить по всім вершинам однієї компоненти зв'язності. Умова має бути такою, що всі ребра графа мають одиничну вагу.
Алгоритм працює за складність О(N+M), де N - кількість вершин, а M - ребер.
vector < vector<int> > g; // граф
int n; // число вершин
bool was[n]; // масив, в якому одиницями будуть відмічені пройдені вершини
void dfs(int v)/стартова вершина
{
if (was[v]) return;//база рекурсії
was[v]=1;//пройдена вершина
for (int i=0;i<g[v].size();++i)
{
dfs(g[v][i]);//рекурсія по суміжним вершинам
}
}
Алгоритм можна використати для вирішення таких задач:
- Пошук будь-якого шляху в графі
- Перевірка того, чи є вершина предком іншої
- Топологічне сортування
- Пошук кількості компонент зв'язності та їх вершини
- Пошук мостів
- Задача LCA (найменший загальний предок)
|
