на главнуюВсе эхи RU.ALGORITHMS
войти ?

Re: О представлении графа в базе данных

От Ivan Shmakov (2:5020/400) к Kalachihin Vladimir

В ответ на Заголовок предыдущего сообщения в треде (Имя Автора)


From: Ivan Shmakov <ivan@main.uusia.org>

>>>>> "KV" == Kalachihin.Vladimir@p39.f1.n5095.z2.fidonet.org writes:

IS> <<Можно понимать>>, в данном случае, означает, что выделенное
IS> направление -- важно это для задачи, или нет -- в графе все же
IS> присутствует -- и это направление на корень дерева.

KV> Hет. (А кстати, откуда такое мнение? Вон Alex Mizrahi тоже самое
KV> говорит. Хотя это принципиально неверно.)

Действительно, <<массовость>> этого <<заблуждения>> наводит на
определенные мысли.

KV> Если взять произвольную вершину неориентированного дерева, то
KV> нельзя сказать, в какую сторону там корень.

Запросто: если в дереве существует путь от некоторого соседа
данного узла до корня, не пересекающий сам данный узел, то такой
сосед является родителем данного узла. Если такой сосед не
единственный, то в графе имеются циклы, а значит оный не
является деревом по определению.

В C-образном псевдокоде, это может быть что-то подобное:

int root_p (struct node *); /* true iff NODE is root */

struct node *
parent (struct node *node)
{
return
parent (node, new_node_marks ());
}

struct node *
parent (struct node *node, struct node_marks *marks)
{
struct node *root;

/* assume that root is its own parent */
if (root_p (node)) {
return node;
}

/* iterate over the neighbors */
struct node *nei;
for_each_neighbour (node, nei) {
if (node_marked_p (marks, node)) {
/* already been here; discard */
continue;
}

mark_node (marks, node);

if (parent (marks, nei) != 0) {
/* found the way to the root node */
return nei;
}
}

/* no parent in the chosen direction */
return 0;
}

[...]

--
FSF associate member #7257
--- ifmail v.2.15dev5.4
* Origin: Aioe.org NNTP Server (2:5020/400)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким

FGHI-url этого письма: area://RU.ALGORITHMS?msgid=<1187409009@violet.siamics.net>+38dfb98c