Алгоритмы на графах
Формулировка задачи. Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные пути от вершины 1 до каждой из вершин графа. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.
Формулировка
задачи. Дано
двоичное дерево. Необходимо организовать
полный его проход с минимальными затратами
дополнительной памяти. Для полного обхода
любого дерева можно легко и просто
составить рекурсивную процедуру.
Такого рода рекурсивный
механизм используется в задаче о методе
минимакса. Но рекурсия для своей реализации
требует достаточно много дополнительной
памяти, что не укладывается в требование
минимальности затрат. Экономное решение
очевидно должно иметь нерекурсивную
природу.
Формулировка задачи. Дан произвольный неориентированный граф. Найти между двумя заданными точками k – кратчайших путей.
Формулировка
задачи. Дан взвешенный граф, в котором
веса присвоены ребрам. Необходимо найти
минимальное остовное дерево
имеющую своим корнем одну из вершин графа.
Формулировка задачи. Дан взвешенный граф, в котором веса присвоены ребрам. Необходимо найти минимальное остовное дерево имеющую своим корнем одну из вершин графа.
Формулировка задачи. Дан непустой взвешенный граф с произвольными весами ребер. Требуется найти кратчайшие длины путей между всеми парами вершин графа, если в графе нет циклов отрицательной длины или обнаружить наличие таких циклов.
Формулировка задачи. Дан непустой граф. Необходимо найти путь между двумя вершинами содержащий наименьшее количество вершин (ребер).
Алгоритм поиска компонент связности
Формулировка
задачи.
Дан произвольный граф
возможно состоящий из нескольких компонент
связности. И дана произвольная вершина
графа. Требуется выделить компоненту связности
содержащую данную вершину.