Имена алгоритмов обхода графика

Я ищу полный список алгоритмов обхода графика, с краткими описаниями их целей, как отправной точкой для их исследования. До сих пор я знаю:

  • Dijkstra - кратчайший путь с одним источником.
  • Kruskal - находит минимальное остовное дерево

Какие еще известные? Просьба представить краткое описание каждого алгоритма для каждого из ваших ответов.

Ответы

Ответ 1

хорошо известные:

сетевой поток

Ответ 2

Немного от головы:

Первый шаг и первый шаг - только два разных способа касания всех узлов.

Алгоритм Флойда-Варшалла находит кратчайшие пути между любой парой точек в (big-theta) (v ^ 3) времени.

Алгоритм Prim является альтернативой Kruskal для MST.

Существуют также алгоритмы поиска полностью подключенных компонентов, которые представляют собой группы узлов, где вы можете получить от любого члена компонента к любому другому члену. Это имеет значение только для "ориентированных графов", где вы можете пересечь ребро только в одном направлении.

Лично я считаю самое крутое расширение теории графов (не совсем связанное с вашим вопросом, но если вам интересно узнать больше о графиках в целом, это, безусловно, стоит вашего времени) - это понятия "сети потоков": http://en.wikipedia.org/wiki/Flow_network. Это способ вычислить, скажем, сколько электроэнергии можно распределить по домам с различными потребностями и потребностями в электроэнергии и различными электростанциями.

Ответ 3

Алгоритмы графа

Все алгоритмы в одном месте

Словарь алгоритмов и структур данных: