Вопрос по 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 , Это способ вычислить, скажем, сколько электричества можно распределить по домам с различными потребностями и требованиями к электроэнергии и различными электростанциями.

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

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