Некоторые алгоритмы построения связных графов:

• Алгоритм Краскала. 2 На входе — пустой подграф, который достраивают до потенциального минимального остовного дерева. 2 Сначала рёбра сортируют по неубыванию их весов. 2 Затем в подграф добавляют ребро только в том случае, если оно соединяет две разные компоненты связности, одним из которых является подграф. 2 На каждом шаге добавляют минимальное по весу ребро, один конец которого содержится в подграфе, а другой — ещё нет. 2 Алгоритм завершает работу, когда множество вершин подграфа совпадает с множеством вершин исходного графа. 2
• Алгоритм Прима. 23 Сводится к жадному перебору рёбер, но уже из определённого множества. 2 Сначала граф делят на два подграфа — древесных и недревесных вершин. 3 Затем выбирают произвольную вершину и делают её текущей. 3 Помещают в накопитель все рёбра, которые ведут из этой вершины в не MST-узлы. 3 Если в какой-либо из узлов уже ведёт ребро с большей длиной, заменяют его ребром с меньшей длиной. 3 Затем выбирают ребро с минимальным весом из накопителя. 3 Повторяют операцию до тех пор, пока все вершины не окажутся в дереве. 3
• Алгоритм, основанный на поиске в глубину. 4 Используют для выделения точек сочленения и мостов. 4
• Алгоритмы обхода графа. 4 Для выделения связных компонент графа применяют поиск в ширину или поиск в глубину. 4
• Алгоритм Беллмана — Форда. 4 Находит кратчайшие маршруты между заданной вершиной и всеми вершинами, достижимыми из неё. 4 Алгоритм допускает наличие в графе рёбер отрицательного веса. 4