П'ятниця, 29.03.2024, 12:10
Гость

Мішатронік

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

Онлайн всього: 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 (найменший загальний предок)

 

Форма входа
Пошук
Друзі сайту
Календар
«  Березень 2024  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728293031

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