м

Алгоритмы обработки графов на основе поиска в глубину:

• Топологическая сортировка
• Поиск 1-, 2-, 3-связных компонент
• Поиск мостов
• Поиск сильно связанных компонент
• Проверка планарности

Поиском в глубину (DFS – depth first search) называется один из методов обхода графа G = (V, E), суть которого состоит в том, чтобы идти “вглубь” пока это возможно. В процессе поиска в глубину вершинам графа присваиваются номера, а ребра помечаются. Обход вершин графа происходит согласно принципу: если из текущей вершины есть ребра, ведущие в непройденные вершины, то идем туда, иначе возвращаемся назад. Есть два основных метода реализации: рекурсивный и итеративный с использованием стека

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
	if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
	v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do
		S.push(w)

Оценим время работы обхода в глубину. Процедура dfs вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие ребра {w | begin(w) = v }. Всего таких ребер для всех вершин в графе O(E), следовательно, время работы алгоритма оценивается как O(V+E). (в этой оценке считаем что граф хранится списком смежности , для матрицы это O(V^2), для списка рёбер O(VE))*