Блог

Я новичок в теории графов и смущен определением предков в DAG (или в общем графике).

 For example in the following DAG

1--->2--->3<---4<---5
 

Если я сначала запускаю DFS с 1 вершины, то пройденный путь равен 1—2—3. Затем, если я начну DFS с вершины 5,
то пройденный путь будет равен 5—4. Вершина 3 больше не посещается. Итак, порядок посещений равен 1 2 3 5 4.
Как насчет предков 3. Они тоже только 1,2 или 4,5?
как насчет предка Предка из 4. Это только 5 или 1,2, поскольку они также были посещены до посещения 5?

Предками вершины v в DAG является множество всех вершин v ‘ != v таких, что v достижимо из v ‘. Итак, в вашем примере предками 3 будут 1, 2, 4 и 5.

Конечно, все по-другому, если вы просто смотрите на определенный путь: таким образом, предки 3 в пути 1-> 2-> 3 будут просто 1 и 2.