Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритмы на графах

Автор: dvs 3.6.2005, 15:47

Какие алгоритмы работы с графами вам известны?
Мне пока известны такие:
1. Нерекурсивный поиск в глубину
2. Рекурсивный поиск в глубину
3. Нерекурсивный поиск в ширину
4. Рекурсивный поиск в ширину
5. Алгоритм Дейкстры
6. Алгоритм Форда-Беллмана
7. Алгоритм Флойда
8. Эйлеровы пути
9. Гамильтонов путь. Алгоритмы с возвратом
10. Топологическая сортировка
11. Остовное дерево наименьшей стоимости, алгоритмы Прима и Краскала
12. Транзитивное замыкание, алгоритм Воршалла
13. Выделение компонент связности

Возможно, это не все, что мне известно, но это то, что вспомнил.
Кто-нибуть знает еще?
Идеальный вариант:
1. Суть алгоритма(описание и(или) блок-схема), где и для чего используется.
2. Пример, круто, если на паскале... Но можно и на Си.

Нужно их собрать в кучу. smile

1-13 пункты, думаю, что скоро смогу оформить и выложить.

Автор: batigoal 3.6.2005, 16:24

Делал когда-то курсовик на тему ориентированного графа со взвешенными ребрами, но выкладывать не буду - кривой. smile

А алгоритмы брал из книги "Структуры данных в С++".

Автор: borisvolfson 3.6.2005, 17:25

Посмотри у меня на сайте http://borisvolfson.h11.ru/graphs_sources.php есть сборник исходников по графам, там реализации алгоритмов (некоторые с подробными комментариями) на паскале (некоторые на С++)...

Содержание примерно следующее (краткий список smile

):

# Поиск в ширину (BFS)

* Порядок обхода вершин при поиске в ширину
* Лес поиска в ширину
* Определение кратчайшего пути

# Поиск в глубину (DFS)

* Точки сочленения
* Двусвязные компоненты
* Проверка двудольности графа
* Поиск мостов
* Поиск компонент связности
* Поиск цикла в графе
* Порядок обхода вершин при поиске в глубину
* Определение типа ребер при поиске в глубину
* Лес поиска в глубину
* Проверка графа на связность
* Проверка вершин на связность
* Поиск в глубину на списках смежных вершин
* Нерекурсивный поиск в глубину (со стеком)
* Нерекурсивный поиск в глубину (со выделенным стеком)
* Восстановление пути при поиске в глубину
* Порядок обхода вершин при поиске в глубину (до захода в рекурсию и при выходе из рекурсии)
* Поиск в губину с занесением вершин в стек в порядке их обхода

# Ориентированные графы

* Определение типа ребер при поиске в глубину
* Проверка на ацикличность (DAG)
* Построение транзитивного замыкание алгоритм Уоршалла

# Потоки в сетях

* Поиск максимального потока методом Форда-Фалкерсона, алгоритмом Эдмондса-Карпа с поиском аугментального пути поиском в ширину
* Визуализатор предыдущего алгоритма
* Поиск максимального потока методом Форда-Фалкерсона с поиском аугментального пути алгоритмом Дейкстры (вес ребра равен пропускной способности)
* Поиск максимального потока методом Форда-Фалкерсона с поиском аугментального пути алгоритмом Дейкстры (вес ребра равен неиспользованно пропускной способности)
* Поиск максимального потока методом выталкивания превосходящего потока.
* Генератор случайных графов для алгоритмов поиска максимального потока в сети.

# Паросочетания

* Поиск максимального паросочетания в двудольном графе

# Минимальные остовные деревья (MST)

* Поиск минимального остовного дерева алгоритм Прима
* Поиск минимального остовного дерева алгоритм Прима с очередью по приоритетам
* Поиск минимального остовного дерева алгоритм Прима (вариант Седжвика)
* Поиск минимального остовного дерева алгоритм Прима на списках смежных вершин
* Поиск минимального остовного дерева алгоритм Прима на списках смежных вершин с очередью по приоритетам
*

# Представления графа в памяти компьютера

* Матрица смежности
* Списки смежных вершин

# Кратчайщие пути

* Поиск кратчайшего пути от одной вершины до остальных алгорит Дейкстры (матрица смежности)
* Поиск кратчайшего пути от одной вершины до остальных алгорит Дейкстры (списки смежных вершин)
* Поиск кратчайшего пути от одной вершины до остальных алгорит Дейкстры (матрица смежности) с очередью по приоритетам
* Поиск кратчайшего пути от одной вершины до остальных алгорит Дейкстры (списки смежных вершин) с очередью по приоритетам
* Поиск кратчайшего пути между всеми парами вершин алгоритм Флойда
* Генератор случайных графов для алгоритмов поиска кратчайших путей.

# Структуры данных

* Индексированная чередь по приоритетам на базе многопозиционного дерева
* Индексированная очередь по приоритетам на базе бинарного дерева

Автор: poor_yorik 3.6.2005, 17:54

Я тебе єтих тем тыщу могу дать...
+ Алгоритм наименьшего паросочитания в двудольном графе.
+ Алгоритм назначения и назначения на узкое место.
+ Алгоритм оптимального потока.
+ Выделение сильных компонент связности и мостов.
+ Алгоритмы разукрашивания графов.
Алгоритмов очень много. Большинство из них можно найти в книге Критофидеса
Графы. Алгоритмеческий подход.
Его книгу можно найти здесь.
http://www.caravan.ru/~alexch/graphs/L78.htm

Также для пополнения знаний предлагаю зайти на сайт
http://algolist.manual.ru

Автор: SoWa 3.6.2005, 18:22

Забыли про бинарные графы:
-Построение бинарного дерева
-Сортировка бинарного дерева
-Поиск в бинарном дереве

Автор: borisvolfson 4.6.2005, 18:20

poor_yorik
Очень интересно, что за алгоритм поиска минимального паросочетания... может все-таки максимального?
Еще очень интересует, что за алгоритм "назначения на узкое место".
Алгоритм оптимального потока - я так понимаю это задача о максимальном потоке, а какой конкретно алгоритм используется? Меня очень интересуют современные алгоритмы решения этой задачи.

SoWa
Хотелось бы уточнить терминологию, что вы понимаете под бинарным графом, просто такого термина я еще не встречал.

Автор: poor_yorik 5.6.2005, 11:34

borisvolfson , с паросочетанием и вправду сглупил, извиняюсь!! smile

А насчет назначения на узкое место могу рассказать. Я так понял тебе известен алгоритм назаченя. То есть дан двудольный граф, всем его ребрам приписан некоторый вес, надо найти такое паросочетание, чтобы сумма весов всех выбраных ребер была максимальной (минимальной). Так в задаче о назначениях на узкое место нужно найти такое паросочетание, чтобы минимальный вес ребра, вошедшего в паросочетание, был максимален.
Решение задачи, похоже на задачу о назначениях. Его можно найти по уже указнной мною ссылке.

Автор: borisvolfson 5.6.2005, 18:11

poor_yorik
А ссылку можно? smile

Автор: poor_yorik 6.6.2005, 09:39

Короткое описание алгоритма здесь
http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-2002/algorithm
На этом же сайте находяться визуализаторы, которые показывают дествие алгоритма в пошаговом режиме. Лучше скачать визуализатор 1999 года. smile

Автор: borisvolfson 6.6.2005, 17:27

Знаю хороший сайт. Спасибо.

Автор: SoWa 6.6.2005, 19:08

Как?! Не встречать бинарного дерева?
Это Граф-дерево, у каждого отца которого только два потомка, причем каждый из потомков меньше, чем отец.
Там кучи алгоритмов построения таких графов, их сотрировки, поиска в них.

Автор: dvs 6.6.2005, 22:42

Пожайлуста, прекратите оффтоп.
Создайте тему в "Религиозных войнах" и решайте проблемы там. smile

Автор: borisvolfson 7.6.2005, 17:19

SoWa
Просто в программировании обычно бинарные деревья относят к структурам данных, а не к графам, а в математике наоборот.
dvs15
Можешь сказать, какие конкретно алгоритмы тебя интересуют, я могу посмотреть в своих запасниках...

Автор: Snezhana999 20.12.2011, 20:27

У кого-нибудь есть реализованный алгоритм поиска связных компонент графа?

Автор: maxim1000 21.12.2011, 06:37

Snezhana999, лучше создать новую тему
и, наверное, http://forum.vingrad.ru/forum/Vingrad-help-center.html больше подойдёт

Автор: garfish 25.11.2013, 14:14

наверно сюда можно добавить еще раздел

# Алгоритмы над конечными автоматами (ориентированными графами с конечным числом состояний)
* Детерминизация конечного автомата - построение эквивалентного автомата и устранение совпадающих переходов.
* Минимизация конечного автомата - построение эквивалентного автомата с меньшим числом состояний.

# Представления графа в памяти компьютера
- Функция действия автомата - определяет действие вершины и дальнейшее следование по матрице смежности
- Польская запись - запись выражений в обратном опрядке, где операнды расположены перед знаками операций.

# Потоки в сетях
* Алгоритм Левита - находит кратчайшее расстояние от одной из вершин графа до всех остальных.
* Алгоритм Джонсона - позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
* Алгоритм Флойда — Уоршелла - для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа
* Алгоритм Беллмана — Форда - алгоритм поиска кратчайшего пути во взвешенном графе.

* Поиск максимального паросочетания в двудольном графе
тут есть несколько варианций:
- Алгоритм Куна
- алгоритм Хопкрофта-Карпа, (адаптированный алгоритм Форда-Фалкерсона)
- алгоритм Куна-Манкреса, он же венгерский алгоритм.

Автор: Arkado 11.12.2013, 14:05

Привет!

У меня есть ориентированный граф и по нему стоят следующие задачи:

1. Для произвольного узла (вершины) X графа нужно найти ближайшую к нему вершину вверх по графу, через которую проходят все возможные пути к узлу X.

2. Для нескольких (>=2) произвольно выбранных узлов графа требуется:

а) проверить, что все эти узлы полностью независимы друг от друга;
б) если зависимость всё же имеется, то среди выбранных узлов должны быть узлы, обеспечивающие такую связь, т.е. не должно быть пропущенных этапов между "первыми" и "последними" выбранными узлами.

Есть ли готовые алгоритмы решения таких задач?
Если нет, то подскажите, пожалуйста, какие алгоритмы (их названия) нужно применить для решения каждой задачи?

Автор: maxim1000 11.12.2013, 19:28

Arkado, лучше сделать отдельную тему

Автор: Absorber001 6.1.2014, 02:44

Модератор: Сообщение скрыто.