Поиск в глубину DFS
Поиск в глубину ( DFS) - это один из основных алгоритмов на графах. Алгоритм работает за O(N + M).
Алгоритм
Для начала мы запускаемся от вершины, рассматриваем детей этой вершины, и если мы никогда в них не заходили, то запускаем от них DFS.
|
Двудольный граф
Двудольный граф - граф, вершины которого можно разбить на два множества так, что каждое ребро соединяет вершины из разных множеств.
Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.
Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS.
Алгоритм
Начинаем покраску с произвольной вершины, которую красим в произвольный цвет.
При прохождении по каждому ребру красим следующую вершину в противоположный цвет.
Если при переборе соседних вершин мы нашли вершину, уже покрашенную в тот же цвет, что и текущая, то в графе существует нечётный цикл, а значит, он не является двудольным.
|
Алгоритм можно описать следующим образом:
Дан ориентированный граф с n вершинами и m рёбрами. Требуется перенумеровать его вершины таким образом, чтобы каждое рёбро вело из вершины с меньшим номером в вершину с большим.
Иными словами, требуется найти перестановку вершин (топологический порядок), соответствующую порядку, задаваемому всеми рёбрами графа.
Будем использовать обход в глубину (dfs(v))
Если мы будем в момент выхода из \(dfs(v)\) добавлять нашу вершину в начало некоего списка, то в конце концов в этом списке получится топологическая сортировка.
Таким образом, искомая топологическая сортировка — это сортировка в порядке убывания времён выхода.
|
Деревья
Дерево - это связный граф без простых циклов. В дереве нельзя удалить ни одно ребро, чтобы граф остался связным, поэтому дерево является минимальным связным графом.
Деревьями называются определенные типы связных графов. Вот несколько определений деревьев:
-
Деревом называется связный граф, который не содержит простых циклов. Это означает, что нельзя пройти от одной вершины к другой по ребрам графа и вернуться в исходную вершину, не проходя при этом по какому-либо ребру дважды.
-
Деревом называется связный граф, содержащий (n) вершин и ровно (n-1) ребро.
-
Деревом называется связный граф, который становится несвязным при удалении любого ребра. Это означает, что каждое ребро в дереве является неотъемлемой частью поддержания связности графа.
-
Деревом называется граф, в котором любые две вершины соединены единственным простым путем. Простой путь - это путь, который не проходит по одному и тому же ребру более одного раза.
Деревья имеют множество применений в различных областях, таких как информатика, теория графов, биология, генеалогия и многое другое. Они являются важными структурами данных и широко используются в алгоритмах и вычислениях.
|