-1
У меня есть древовидная структура взаимосвязанных узлов разных типов. Каждый узел отслеживает, с какими узлами он связан. В этой структуре мне нужно найти самую длинную несвязанную цепочку или путь узлов того же типа.Поиск самой длинной цепи узлов одного типа
Я прочитал графики и широту/глубину первых поисков, но это не совсем дает результаты, которые мне нужны. (они найдут цепочку, но также включают все ветви тупика между исходным и конечным узлами)
Существует ли для этого существующий алгоритм?
Самый длинный * несвязанный * цепь? Если вы ищете цепочку, я предполагаю, что вы хотите, чтобы эти узлы были связаны *? Не могли бы вы уточнить? –
Можете ли вы объяснить свой вопрос немного больше, поскольку, если каждый узел отслеживает узлы, к которым он подключен, похоже, что у вас есть граф, который имеет связанные компоненты, а для каждого типа узла - количество подключенных компонентов, тип узла находится в, тот, который присутствует в большинстве подключенных компонентов, является типом, который имеет самую длинную несвязанную цепочку. это то, что вы имели в виду? – umar
Я думаю, что автор указывает на то, что он может получить график обратно как ((A-> B), (A-> F), (B-> C), (C-> D), (D-> E)). A-F - это все тот же тип. Но он хочет, чтобы любые ветви, такие как A-> F, были обрезаны из графика. Это представляет проблему в случае ((M-> N), (N-> O), (M-> P), (P-> Q)), так как в одном дереве есть две ветви равной длины - который вы обрезаете? –