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

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

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

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

Посмотри у меня на сайте Домашняя страничка Бориса Вольфсона есть сборник исходников по графам, там реализации алгоритмов (некоторые с подробными комментариями) на паскале (некоторые на С++)...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Это сообщение отредактировал(а) borisvolfson - 4.6.2005, 18:33

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

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

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

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

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

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

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

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

Snezhana999, лучше создать новую тему
и, наверное, Центр помощи больше подойдёт