Алогритм

А почитать книжку Н. Вирта слабо? Не говоря уже о Кнуте. Да и в любом учебнике будет написано. Во-первых таких "алогритмов" имеется изрядное количество. Во-вторых, что значит "как можно оптимальнее"? Не говоря уже о том, что это неграмотно сказано, что выступает в качестве критерия? Скорость? Объем требуемой памяти? Прозрачность алгоритма?

и типа где проблема?

void process (struct A* node) { struct A* item; for ( item = node; item; item = node->next ){ process_node(item); if (children) process(children); } }

int main() { struct A* root = .... ; process(root); }

И да поможет тебе РЕКУРСИЯ!

насвкидку это будет так:

void walk(struct A* a)
{
if ( !a ) return;

// Do something here with a

walk(a->next);
walk(a->prev);
walk(a->children);
}

ЗЫ: А бесконечность - это математический термин, который в программировании не уместен.

Ты сказал про свой граф только то, что все его вершины имеют кратность <=4. Про структуру ничего не известно. Циклы в нем есть? А петли? А кратные ребра? А что насчет связности?

Т.о., в общем случае не придумаешь ничего, кроме тупого обхода - хошь, в ширину, хошь, в глубину.

Кстати, добрый человек довольно краткий конспект выложил, можешь почитать, если лень читать толстые книжки: http://yevgeny.nm.ru/institut/dm4.html#x6

NewComer (*) (2003-03-25 15:17:27.775589):
Как только в графе появляются циклы, твой алгоритм зацикливается.
Т.е. надо еще пройденные вершины помечать.

anonymous (*) (2003-03-25 15:07:24.721154):
Ну, в приведенном тобой примере слишком много предположений о том, кто такие
children & Ko. Может, автор вопроса другое имел в виду?

Это из libxml кусок структуры...
Автор

>void process (struct A* node) { struct A* item; for ( item = node; >item; item = node->next ){ process_node(item); if (children) >process(children); } }
>int main() { struct A* root = .... ; process(root); }
Бесконечный цикл
>void walk(struct A* a)
>{
>if ( !a ) return;
>// Do something here with a
>walk(a->next);
>walk(a->prev);
>walk(a->children);
>}
Проход без сохранения ирархии...

Ещё как уместен. Если у тебя ленивый язык, то ничто не мешает работать с бесконечными структурами.

Это я так - пример на вскидку - ессно, алгоритм работоспособен только для дерева.