По заданному ребру найдите минимальное остовное дерево, если оно существует

Question

У меня есть взвешенный неориентированный график G и ребро e .Мне нужно найти минимальное связующее дерево, содержащее e , если и только если оно существует.

Answer 1

Я могу интерпретировать ваш вопрос двумя различными способами:

1. найти все минимальные остовные деревья.Если какой-либо из них содержит e, верните его.В противном случае верните ноль.
2. Используйте алгоритм Крускала, добавьте e в связующее дерево, прежде чем делать что-либо еще.Постройте оставшееся дерево.Если вы можете создать минимальный охват, верните его.

Есть две потенциальные точки отказа:

A.график содержит компоненты, не связанные ребром (не существует связующего дерева)
B. минимальное остовное дерево не содержит e

Подход (1) не выполняется при условии A и B. Подход (2) не выполняетсятолько при условии А.