Informatiker Board | Druckvorschau: Wann ist ein Graph ein Baum

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Wann ist ein Graph ein Baum (http://www.informatikerboard.de/board/thread.php?threadid=3027)

Geschrieben von Shizmo am 13.05.2016 um 12:47:

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

Geschrieben von eulerscheZahl am 13.05.2016 um 14:04:

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

Geschrieben von Shizmo am 14.05.2016 um 10:31:

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

Geschrieben von eulerscheZahl am 14.05.2016 um 10:38:

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.

Geschrieben von Shizmo am 14.05.2016 um 10:46:

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?