Неділя, 21.04.2019, 23:42
Гость

Мішатронік

Автор - Кренцін Михайло

Мобільна версія | Додати у вибране  | Мій профіль | Вихід | RSS |
Меню сайту
Наше опитування
Оцініть мій сайт
Всього відповідей: 12
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0




Даний алгоритм представляє собою рекурсивну функцію, яка проходить по всім вершинам однієї компоненти зв'язності. Умова має бути такою, що всі ребра графа мають одиничну вагу.

Алгоритм працює за складність О(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]);//рекурсія по суміжним вершинам
    }
}

Алгоритм можна використати для вирішення таких задач:

  1. Пошук будь-якого шляху в графі
  2. Перевірка того, чи є вершина предком іншої
  3. Топологічне сортування
  4. Пошук кількості компонент зв'язності та їх вершини
  5. Пошук мостів
  6. Задача LCA (найменший загальний предок)

 

Форма входа
Пошук
Календар
«  Квітень 2019  »
ПнВтСрЧтПтСбНд
1234567
891011121314
15161718192021
22232425262728
2930
Друзі сайту
Погода у Вінниці


Єдина Країна! Единая Страна!