Wann ist ein Graph ein Baum

13.05.2016, 12:47

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:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

if |V| != |E|-1
  return false

for each vertex u in G.V {
   for each vertex v in G.V {
      if(u != v && delta(u,v) == 0)    //2 ungleiche Knoten haben keine Verbindung
         return false
   }
}

return true

Also das delta ist der kürzeste Weg.

Aber damit ist es vermutlich noch nicht getan... verwirrt

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 Augenzwinkern

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 Zunge raus

Also meinst du so? (Geht eigtl hauptsächlich um Zeile 23,24)

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

if |V| != |E|-1
   return false

for each vertex u in G.V - {s} 
   u.color = WHITE
   u.d = infinity
   u.PI = NIL

s.color = GRAY
s.d = 0
s.PI = NIL
ENQUEUE(Q,s)

while Q not empty 
   u = DEQUEUE(Q)
   for each v in G.Adj[u] 
      if v.color == WHITE 
         v.color = GRAY
         v.d = u.d + 1
         v.PI = u
         ENQUEUE(Q,v)

      else if v.color == GRAY || BLACK
         return false

   u.color = BLACK
return true

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.

14.05.2016, 10:46

Auf diesen Beitrag antworten »

Shizmo

Hmm stimmt eigentlich, meinst du dass es so funktionieren könnte?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

if |V| != |E|-1
   return false

for each vertex u in G.V - {s} 
   u.color = WHITE

s.color = BLACK

ENQUEUE(Q,s)

while Q not empty 
   u = DEQUEUE(Q)
   for each v in G.Adj[u] 
      if v.color == WHITE 
         v.color = BLACK
         ENQUEUE(Q,v)

      else
         return false

   u.color = BLACK

return true

//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 !!!!

Neue Frage »

Antworten »

Wann ist ein Graph ein Baum

Verwandte Themen