Здравствуйте, Erop, Вы писали:

E>Поиск путей в графе
Это понятно, что поиск пути. А в какой задаче его искать-то потребовалось?

BFE>>А то я однажды решал задачу прокладки пути от A к B с обходом препятствий и оказалось, что графы там не нужны.
E>Бывает. Я, обычно, ищу пути в довольно абстрактных графах. Хотя, иногда, и в графах вполне графической природы. Например, в графе линейного деления...
Ну а я как-то обхожусь без этого.

E>>>А если лес, например? А если в дереве склеивать совпадающие подветки? Это будет дерево или ациклический направленный граф?
BFE>>Это будет два объекта: дерево и список.
E>Что? Ациклический граф, полученный склеиванием одинаковых веток деревьев?
Значит я не понял, что значит склеивать.

BFE>>Интересно. Где можно глянуть?
E>Начни с реализации stl в твоём компиляторе
E>На самом деле, зачем хранить ДВЕ ноды — терминатора, когда можно хранить ОДНУ? То, что возвращает end -- поле list, элемент двусвязного циклического списка. Его next -- это begin списка. Сверху этого всего декоратор, для rbegin и т. д...
О звёзды! Это что? В списке всегда хранится один лишний элемент с аллоцированной памятью под пользовательские данные? Какой кошмар...
Похоже, что авторы, таки, реализовали эту абсурдную идею с графом из одной вершины.
Нет, ну я не могу отвечать за это извращение. Мало ли, что там под капот засунули...

BFE>>

BFE>>int f(int n)
BFE>>{
BFE>>    return (n + 1) % 5;
BFE>>}
BFE>>

BFE>>граф увидите.
E>Ну, да. Это можно интерпретировать, как граф. Например, если рассматривать любые целые n...
А можно и не рассматривать...

E>Поиск людей, к которым ведёт много коротких путей, что бы предложить их добавить в своих друзей.
Ok. Принимается.
E>Анализ структуры графа, что бы выявлять накрутки и т. д...
Не, анализ — это не то...
Анализ — это не для пользователей, а для аналитиков. Аналитики любят красивые картинки...

E>>>А для поиска цикла в списке, нужно?
BFE>>Нет, конечно.
E>Ну так список с циклом это же таки граф?
Да, список с циклом, это, таки, граф. А что?

E>Почему поиск цикла в таком списке -- это алгоритм на графе, а поиск цикла в ГПСЧ -- нет? Алгоритм-то тот же?
Потому, что список существует как структура и к ней применяется алгоритм. А при поиске цикла в ГПСЧ нам сама структура не нужна, насколько я понимаю.

BFE>>объект std::vector<std::vector<int> > является графом только тогда, когда к нему применяются алгоритмы применимые к графу.
E>И?
И они крайне редко нужны на практике.