Названия алгоритмов обхода графа

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

Dijkstra's - single-source shortest path Kruskal's - finds a minimum spanning tree

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

 Ben Lakey02 июл. 2009 г., 10:32
Ой, я почитал их в своем списке. Исправлена.
 KingNestor02 июл. 2009 г., 09:40
Дейкстра не находит минимальное остовное дерево.
 Ben Lakey02 июл. 2009 г., 10:34
Не совсем понятно, почему этот вопрос был отклонен, это законный вопрос, связанный с программированием, и он не является дубликатом.

Ответы на вопрос(3)

Решение Вопроса

Graph algorithms

http://en.wikipedia.org/wiki/List_of_algorithms#Graph_algorithms

All algorithms in one place

http://en.wikipedia.org/wiki/List_of_algorithms

Dictionary of algorithms and data structures:

Dictionary: http://xlinux.nist.gov/dads/

By area: http://xlinux.nist.gov/dads/termsArea.html

By terms type: http://xlinux.nist.gov/dads/termsType.html

List of all implementations in diff. languages: http://xlinux.nist.gov/dads/termsImpl.html

Обходы в глубину и в ширину, на самом деле это всего лишь два разных способа прикоснуться ко всем узлам.

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

Прим алгоритм является альтернативой Крускала для MST.

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

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

 Ben Lakey12 июл. 2009 г., 09:57
Ваш комментарий полезен и проницателен. Спасибо, что нашли время, и я принял ответ.
 09 июл. 2011 г., 11:07
Правильное название для «полностью подключенных компонентов». являетсяstrongly connected components.

Ваш ответ на вопрос