Ich versuche, einen O (| V | + | E |) Zeitalgorithmus zu finden, um zu prüfen, ob eine Verbindung besteht ungerichteter Graph hat einen Zyklus von ungerader Länge oder nicht.
Ich überlege, eine Breite zuerst Suche auf dem Graphen zu machen und zu versuchen, die Scheitelpunkte schwarz und weiß zu beschriften, so dass keine zwei Scheitelpunkte, die mit der gleichen Farbe markiert sind, benachbart sind.
Gibt es einen bekannteren Algorithmus, um dieses Problem in linearer Zeit zu lösen?
Ihr Ansatz ist der richtige. Du kannst nicht besser als das.
Der Grund dafür ist, dass wenn Sie die Vertices während der BFS mit ihrer Tiefe beschriften, alle Kanten entweder dieselben Labels oder Labels verbinden, die sich um eins unterscheiden. Es ist klar, dass, wenn es eine Kante gibt, die die gleichen Etiketten verbindet, es einen ungeraden Zyklus gibt. Wenn nicht, können wir alle ungeraden Etiketten weiß und alle geraden Etiketten schwarz färben.
Es kann auch mit DFS und Nummerierung der Vertices gemacht werden.
Erkunden Sie (u)
Wenn Sie bereits "besucht" haben, dann wenn (Takt-Num [u]) ungerade ist, dann gibt es einen ungeraden Zyklus,
sonst markieren Sie "u" als "besucht"
Num [u] = Uhr ++;
für alle benachbarten Knoten v von u
%Vor%