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

E>>>Ну, A*, например, часто использую...
BFE>>И что это означает?
E>Гуглофу на нуле что ли?
А область применения?
А то я однажды решал задачу прокладки пути от A к B с обходом препятствий и оказалось, что графы там не нужны.

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

E>>>std::list когда-нибудь юзал?..
BFE>>да.
E>AFAIK, одна из популярных реализаций базируется на зацикленном списке нод...
Интересно. Где можно глянуть?

BFE>>Это когда хранятся и используются все переходы графа.
E>А что значит "хранятся"? Если есть функция, которая по id ноды может вернуть id следующей ноды, это в явном виде? Если таки да, то чем ГПСЧ не "явный граф"?
Конечно это не граф.
Вы наверное и вот здесь:

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

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

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

BFE>>Мне на практике такая задача никогда не встречалась, но я сомневаюсь, что для её решения надо строить граф переходов в памяти компьютера.
E>А для поиска цикла в списке, нужно?
Нет, конечно.

BFE>> Я в курсе. Но если из всего внешнего массива доступен только один элемент, то это не граф.
E>Это ты о чём?
Это я о списке друзей из соц сети.
объект std::vector<std::vector<int> > является графом только тогда, когда к нему применяются алгоритмы применимые к графу.