Breitensuche auf gerichteten Graphen andwenden

Question

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.

Comments

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

Answer 1

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.