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

E>>Гуглофу на нуле что ли?
BFE>А область применения?
Поиск путей в графе

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

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

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

BFE>

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

BFE>граф увидите.


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

E>>Чем списки соседей в соц. сети не явное представление графа?
BFE>Вот когда список всех пользователей соц. сети лежит в базе данных, то можно сказать, что в базе данных лежит граф в явном виде. Но если в ничего с этим графом не делаете, то вам от этого ни жарко, ни холодно. Для того, чтобы его можно было рассматривать как граф, нужно чтобы к нему применялись спец алгоритмы применимые к графу. Evgeny.Panasyuk нашел один такой алгоритм, который, наверное, применяется в LinkedIn — поиск знакомого, через знакомого. Вы знаете ещё такие же задачи?

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

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

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