Filtering Eckpunkte in einem Diagramm

Question

Sagen wir, ich habe einen gerichteten azyklischen Graphen mit n Ecken und eine Teilmenge der Ecken bei Größe M.

Die M Eckpunkte werden als besucht markiert, wie kann ich alle Ecken finden, die alle von ihren Vorgängern im Graphen werden

zum Beispiel besichtigt: wenn es 4 Eckpunkte a, b, c, u und 3 gibt (a, u) (b, u) (c, u) und a, b, c sind als besucht markiert Ich muss u.

ich alle gehen durch die Eckpunkte zu denken und für jeden Vertex Check all seiner Vorgänger, aber ich denke, dass dies .. nicht viel effizienter ist

Answer 1

jene M Eckpunkte aus dem ursprünglichen Graphen löschen. Dies kann erreicht werden, indem einfach die ausgehenden Kanten von den "besuchten" Knoten entfernt werden.

Die Knoten, die nicht in M ​​sind und die von keinem anderen Scheitelpunkt aus erreichbar sind, haben alle ihre Vorgänger besucht (in M).

Wenn der Graph die Form einer Adjazenzmatrix hat, kann dies durch Scannen jeder Spalte und Prüfen, ob ein Eintrag ungleich Null vorhanden ist, erfolgen.