Существует граф с множеством узлов и очень немного ребер между ними - проблема заключается в присвоении чисел узлам, так что большинство узлов находятся от i до i + 1 или иным образом закрываются.Как назначить последовательные числа узлам направленного графа?
Моя проблема заключается в хорошем графическом отображении данных, но алгоритм, подобный этому, является частью почти всех компиляторов (промежуточный код - всего лишь граф, полученный объектный код получает ячейки памяти).
Я думал, что это был просто простой поиск по глубине, но результаты этого не так уж велики - кажется, что он минимизирует количество ссылок обратно достаточно хорошо, но те, которые он оставляет, имеют тенденцию быть ужасными (например, 1 -> 500 -> 1).
Любые лучшие идеи?
Что вы подразумеваете под «так, чтобы большинство узлов находились от i до i + 1 или иным образом закрывались».? –
@Assaf: Я бы определил его как пометку N узлов графа с уникальными числами из {1,2, ..., N}, так что сумма дельт всех связанных пар минимальна. Это верно? –
Это может быть очень интересной проблемой, если бы я мог понять только то, что вы имеете в виду ... это похоже на проблему с гамильтоновым путём? «i to i + 1» между как можно большим числом узлов? – mvds