Kreis der Länge 4 in einem ungerichteten Graphen finden |
| 16.06.2011, 18:17 | homee | Auf diesen Beitrag antworten » |
| Kreis der Länge 4 in einem ungerichteten Graphen finden Ich suche einen Algorithmus, der einen einfachen Kreis der Länge 4 (also 4 Knoten, 4 Kanten) in einem ungerichteten Graphen findet. Der Graph liegt als Adjazenzlist vor. Der Algorithmus soll eine Worst-Case Laufzeit von besitzen (v ist die Anzahl der Knoten im Graph) und das ganze soll nach dem Prinzip der Breitensuche funktionieren. Der Kreis muss nicht ausgegeben werden. Es soll nur gezeigt werden, dass ein solcher Kreis existiert oder eben nicht. Meine Ideen: Leider habe ich nicht einmal einen Ansatz im Moment. |
||
| 16.06.2011, 18:31 | kiste | Auf diesen Beitrag antworten » |
Mache für jeden Knoten eine Breitensuchen der Tiefe 4 und vergleiche mit dem Startknoten. |
||
| 16.06.2011, 18:55 | homee | Auf diesen Beitrag antworten » |
Was genau soll ich vergleichen? Angenommen ich habe einen Kreis 1 -> 2 -> 3 -> 4 -> 1 und 1 ist mein Startpunkt, dann hat Knoten 1 keinen Vorgänger und Distanz 0, Knoten 2 hat 1 als Vorgänger und Distanz 1, Knoten 3 hat Knoten 2 als Vorgänger und Distanz 2 und Knoten 4 hat Knoten 1 als Vorgänger und Distanz 1. Wie kann ich daraus schließen, dass es ein Kreis ist? |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
