Графы: Представления, Обходы BFS/DFS, Топологическая сортировка и SCC

Матрица смежности vs Списки смежности. BFS и поиск кратчайших путей. DFS: времена входа/выхода d[u]/f[u], классификация ребер, теорема о скобках, топологическая сортировка и алгоритм Косарайю для сильно связных компонент.

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Обходы графов: предварительные знания, план уроков и практика →

Представления графов

Матрица смежности $A[V][V]$ :

O(1)

проверка наличия ребра, но

O(V^2)

памяти;

Списки смежности vector<int> adj[V]:

O(V + E)

памяти (оптимально для разреженных графов).

Классификация рёбер в DFS

При обходе в глубину с временными метками входа $d[u]$ и выхода $f[u]$ ребро $(u, v)$ классифицируется как:

Древесное (Tree edge): ведёт в белую (непосещенную) вершину;

Обратное (Back edge): ведёт в серого предка (

d[v] < d[u] < f[u] < f[v]

)

\implies

сигнализирует о наличии цикла!

Прямое (Forward edge): ведёт в чёрного потомка;

Поперечное (Cross edge): ведёт в чёрную вершину другой ветви.

cpp

// Сильно связные компоненты: Алгоритм Косарайю за O(V + E)
void dfs1(int u, vector<bool>& vis, vector<int>& order, const vector<vector<int>>& adj) {
    vis[u] = true;
    for (int v : adj[u]) if (!vis[v]) dfs1(v, vis, order, adj);
    order.push_back(u);
}

void dfs2(int u, vector<int>& comp, int c, const vector<vector<int>>& radj) {
    comp[u] = c;
    for (int v : radj[u]) if (comp[v] == -1) dfs2(v, comp, c, radj);
}

Что дальше?

Закрепите материал задачей: Повторить число.

Изучено — к практике →

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».