Algorithmus -- Kreistest im Graphen |
| 10.07.2005, 20:27 | SOA | Auf diesen Beitrag antworten » |
| Algorithmus -- Kreistest im Graphen Folgendes: Es sei ein Algorithmus der Komplexität O(n) zu bestimmen, der einen Graphen prüft, ob er einen Kreis besitzt, also azyklisch ist! Graph: eine Adjanzenmatrix: Es sei der schlechteste Fall zu betrachten, also wenn alle Elemente der Matrix betrachtet werden müssen. Ich habe also n * n Elemente in der Matrix. Ein Kreis ist also dadurch gekennzeichnet, dass kein Element/(Ecke und Kante) mehrfach vorkommt. Die Matrix ist also darauf zu prüfen, ob 2 gleiche Elemente vorkommen! Die Komplexität dieser Betrachtung wäre dann doch: Anzahl der Vergleiche Die Komplexität berägt O(n^4)...is das so korrekt?? Danke SOA |
||
| 10.07.2005, 21:05 | dfg | Auf diesen Beitrag antworten » |
Die Aufgabe muss so lauten: Es sei ein Algorithmus der Komplexität O(n) zu bestimmen, der einen Graphen prüft, ob er einen Kreis besitzt, also zyklisch ist! Denn ein Kreis ist ein Zyklus 
Kurze Veranschaulichung: Ein zyklenfreier Graph ist nichts anderes als ein Baum! Und was noch wichtig ist das du die Knoten geordnet vergleichst, also Vergleiche die du schon gemachst hast nicht nochmal wiederholst. So kannst du einen Algorithmus finden der mit auf der Anzahl der Knoten arbeitet. Mit anderen worten es gibt kein Algorithmus der die Komplexität O(n) hat. Tippfehler? |
||
| 10.07.2005, 22:47 | SOA | Auf diesen Beitrag antworten » |
danke.... Tiefenspannbaum und Breitenspannbaum war´das Stichwort.... Viele Grüße SOA |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
