LINUX.ORG.RU

объединение вершин графа

 ,


0

0

Добрый день!

Есть такая задача. Граф (циклический, ориентированный), у которого ветки могут быть 2 типов (А и Б). Надо найти группы узлов, связанных между собой ветками типа А. Потом, собственно, такие узлы надо будет заменить новым объединенным узлом.

Ткните, пожалуйста, в описание алгоритма, который бы находил такие группы узлов.

p.s. например, граф

o==o
| /
o
должен преобразоваться в такой
q
|
o
где «==» ветка типа А, «/» и «|» ветки типа Б. «о» - необъединенные узлы, «q» - объединенный узел


Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.