Сгенерировать количество ребер между двумя узлами

Question

Я создал это минимальное связующее дерево с помощью алгоритма Крускала, и мне трудно создать пути между двумя узлами.Может кто-нибудь помочь мне с псевдокодом?Я пробовал использовать список смежности и матрицу смежности

Genracodicetagpre

Answer 1

Если вам нужен любой путь между двумя узлами, подойдет поиск в ширину , ибудет генерировать кратчайший путь (потому что это минимальное остовное дерево).

Answer 2

Связующие деревья по определению не имеют циклов (или циклов), поэтому у вас может быть только один путь (т. е. не "пути" во множественном числе) между двумя узлами.

Возможно, я не понимаю вопроса.Вы пытаетесь найти, как два заданных узла связаны в вашем дереве?

Если так, то это звучит для меня как простейшая грубая сила, когда вы просто следуете из одной точки вдоль ее возможных краев, возможно, выталкивая и выталкивая возможности из стека, было бы в худшем случае O (края)время выполнения, что было бы тривиально по сравнению с алгоритмом Крускала. Вам нужно что-то более быстрое?