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

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

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

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

Ответы

Ответ 1

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

Поиск по глубине http://en.wikipedia.org/wiki/Depth-first_search
Поиск по ширине http://en.wikipedia.org/wiki/Breadth-first_search
Алгоритм Prim http://en.wikipedia.org/wiki/Prim's_algorithm
Алгоритм Крускаля http://en.wikipedia.org/wiki/Kruskal's_algorithm
Алгоритм Беллмана-Форда http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
Алгоритм Флойда-Варшалла http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
Алгоритм обратного удаления http://en.wikipedia.org/wiki/Reverse-Delete_algorithm
Dijkstra's_algorithm http://en.wikipedia.org/wiki/Dijkstra's_algorithm

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

Алгоритм Форда-Фулкерсона http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Максимальный поток http://en.wikipedia.org/wiki/Maximum_flow_problem

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

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

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

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

Словарь: http://xlinux.nist.gov/dads/
По области: http://xlinux.nist.gov/dads/termsArea.html
По типу терминов: http://xlinux.nist.gov/dads/termsType.html
Список всех реализаций в diff. языки: http://xlinux.nist.gov/dads/termsImpl.html