Hier ist eine Verbrauchsteuer:

Sei G ein gewichteter gerichteter Graph mit n Ecken und m Kanten, wobei alle Kanten ein positives Gewicht haben. Ein gerichteter Zyklus ist ein gerichteter Pfad, der am selben Scheitelpunkt beginnt und endet und mindestens eine Kante enthält. Geben Sie einen O (n ^ 3) -Algorithmus an, um einen gerichteten Zyklus in G mit minimalem Gesamtgewicht zu finden. Ein O ((n ^ 2) * m) -Algorithmus wird teilweise angerechnet.

Hier ist mein Algorithmus.

Ich mache einDFS. Jedes Mal, wenn ich einen findeback edgeIch weiß, ich habe einen gerichteten Zyklus.

Dann gehe ich vorübergehend rückwärts die Straße entlangparent array (bis ich durch alle Eckpunkte im Zyklus gehe) und berechne dietotal weights.

Dann vergleiche ich dietotal weight dieses Zyklus mitmin. min Nimmt immer die minimalen Gesamtgewichte. Nach Abschluss der DFS wird auch unser minimaler gerichteter Zyklus gefunden.

Ok, dann über die zeitliche Komplexität.

Um ehrlich zu sein, kenne ich die zeitliche Komplexität meines Algorithmus nicht.

Für DFS ist die Traversierung O (m + n) (wenn m die Anzahl der Kanten und n die Anzahl der Eckpunkte ist). Für jeden Scheitelpunkt kann er auf einen seiner Vorfahren verweisen und so einen Zyklus bilden. Wenn ein Zyklus gefunden wurde, ist O (n) erforderlich, um die Gesamtgewichte zusammenzufassen.

Ich denke also, die Gesamtzeit ist O (m + n * n). Aber offensichtlich ist es falsch, wie in der Verbrauchssteuer angegeben, ist die optimale Zeit O (n ^ 3) und die normale Zeit ist O (m * n ^ 2).

Kann mir jemand helfen bei:

Ist mein Algorithmus korrekt?Was ist die zeitliche Komplexität, wenn mein Algorithmus korrekt ist?Gibt es einen besseren Algorithmus für dieses Problem?