Wann ist ein Graph ein Baum |
13.05.2016, 12:47 | Auf diesen Beitrag antworten » | |||||
Shizmo | Wann ist ein Graph ein Baum Hallo, ich soll einen Algorithmus in Pseudocode schreiben, der bestimmt, ob ein Graph ein Baum ist. Angefangen hab ich mal so:
Also das delta ist der kürzeste Weg. Aber damit ist es vermutlich noch nicht getan... ![]() |
|||||
|
||||||
13.05.2016, 14:04 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Wenn delta(u,v) der Abstand der Knoten ist und 0 der Wert, wenn es keinen Weg gibt, dann funktioniert das. Dazu brauchst du aber erst einmal den Abstand von jedem Knoten zu jedem anderen. Mit Floyd-Warshall geht das in O(|V|^3). Besser wäre mittels Breitensuche/Tiefensuche zu bestimmen, ob der Graph zusammenhängend ist. Wenn dann noch die Anzahl der Kanten passt, kann es nur noch ein Baum sein. Die Breiten-/Tiefensuche geht in O(|V|+|E|). Weil es sich um einen Baum handelt (wenn du auf einen bereits besuchten Knoten stoßen solltest, kannst du die Suche eher abbrechen) also O(|V|). Lineare Laufzeit ist doch was feines ![]() |
|||||
14.05.2016, 10:31 | Auf diesen Beitrag antworten » | |||||
Shizmo | Danke für deine Antwort! Meine erste Idee war eigentlich auch auf Breitensuche aufzubauen, hab mir dann aber gedacht, dass sollte doch einfach gehen und hab die Idee wieder verworfen ![]() Also meinst du so? (Geht eigtl hauptsächlich um Zeile 23,24)
LG |
|||||
14.05.2016, 10:38 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Würde funktionieren, die Laufzeit passt jetzt auch. Die Vorgängerstruktur (u.d, u.PI) brauchst du nicht einmal. Und statt GRAY kannst du auch direkt BLACK verwenden. |
|||||
Anzeige | ||||||
|
||||||
14.05.2016, 10:46 | Auf diesen Beitrag antworten » | |||||
Shizmo | Hmm stimmt eigentlich, meinst du dass es so funktionieren könnte?
//edit: Habs grad durchgespielt, sollte eigentlich passen, und Zeile21 könnte ich mir, glaub ich, auch noch sparen? |
|||||
14.05.2016, 10:50 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Ja. Und Zeile 21 kannst du auch gleich löschen. |
|||||
14.05.2016, 10:51 | Auf diesen Beitrag antworten » | |||||
Shizmo | Haha, siehe edit. Vielen Dank eulersche !!!! |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|