Это нумерация вершин-ордеров DFS, которая соответствует обходу предзаказов дерева DFS, а вторая - это нумерация после заказа, которая соответствует обходному порядку дерева DFS.Графический предварительный заказ/послепорядок?
Может кто-нибудь объяснить, как мы получили этот заказ, потому что я знаю, как применять предварительный заказ или пост-порядок только на бинарных деревьях. спасибо
Попробуйте следовать этому шагу псевдокода за шагом с вашим примером, и вы поймете алгоритм, это очень легко и просто ДФС:
Initialize clock to 1
PreVisit(v):
pre[v] <- clock
clock <- clock + 1
PostVisit(v):
post[v] <- clock
clock <- clock + 1
Explore(v):
visited[v] = true
PreVisit(v)
for all u adj to v:
if u is not visited:
Explore(u)
PostVisit(v)
Примечание что вам нужно создать массив из pre, post и visited с длиной вершин. Для массива visited, вы должны заполнить его false, прежде чем звонить по телефону Explore(v).
Знаете ли вы, как работает DFS? если Preorder 1.Выберите корневой узел с минимальным весом, т.е. 1 в вашем примере, а затем 2.search и выберите другой узел, вес которого меньше всего другого узла, кроме родителя, и его не должно формировать цикл и повторять шаг 2, пока вы не охватите все vertex – CY5
DFS работает аналогично по любому графику, как с (двоичным) деревом - основное отличие состоит в том, что алгоритм должен явно запрещать циклы в циклических графах (которые не встречаются в деревьях). Это можно неявно позаботиться о том, соответствуют ли значения узлов некоторым определенным правилам. – user2864740