0 Daumen
34 Aufrufe

Muss ich bei einer Breitensuche auf einen gerichteten Graphen, auf die Richtung der Pfeile achten oder spielt das keine Rolle ?

Beispiel: A -> C und B -> A  ist hier B trotzdem erreichbar, weil direkter Nachbar von A, obwohl von A nach B kein Pfeil geht.

Gefragt von

Weiß wirklich keiner, ob ein Unterschied besteht zwischen gerichtet und ungerichteten Graphen bei einer Breitensuche?

1 Antwort

0 Daumen
 
Beste Antwort

Bei gerichteten Graphen muss die Richtig beachtet werden! Das ginge bei deinem Beispiel nur, wenn zwischen C und B ein Pfeil ist. Andernfalls nicht erreichbar. Gerichtet bedeutet Punkt Y ist nur von Punkt X erreichbar, wenn ein Pfeil in Richtung Y zeigt. Zeigt der Pfeil von Y nach X, ist der Punkt zu nicht zu erreichen, sozusagen eine Einbahnstraße.

Falls du dich bereits mit Vektoren im Rahmen der Analytischen Geometrie beschäftigt hast, verstehst du es vielleicht noch besser.

Beantwortet von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...