Ho il seguente problema sul mio lavoro:Trova se un albero spanning minimo contiene un bordo in tempo lineare?
dare una O (n + m) algoritmo per trovare che sia un vantaggio e sarebbe una parte del MST di un grafico
(Ci è permesso di ottenere aiuto dagli altri in questo incarico, quindi non è un imbroglio.)
Penso che potrei fare un BFS e scoprire se questo margine è uno spigolo tra due strati e in tal caso se questo margine fosse il più piccolo tra questi livelli. Ma cosa potrei dire quando questo spigolo non è un bordo dell'albero dell'albero BFS?
Se questo è compito, segnalo come tale. –