Вопрос по algorithm, graph-theory, graph – Названия алгоритмов обхода графа

15

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

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

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

Дейкстра не находит минимальное остовное дерево. KingNestor
Ой, я почитал их в своем списке. Исправлена. Ben Lakey
Не совсем понятно, почему этот вопрос был отклонен, это законный вопрос, связанный с программированием, и он не является дубликатом. Ben Lakey

Ваш Ответ

3   ответа
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

8

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

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

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

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

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

Правильное название для «полностью подключенных компонентов». являетсяstrongly connected components.
Ваш комментарий полезен и проницателен. Спасибо, что нашли время, и я принял ответ. Ben Lakey

Похожие вопросы