1
Bu, DFS ağacının bir ön sırasına karşılık gelen bir DFS ön-sipariş köşe numaralandırmasıdır ve ikincisi, DFS ağacının bir son-sırasına karşılık gelen bir post-order numaralandırmasıdır.Grafik ön sipariş/sipariş sonrası geçişi?
Birisi, bu siparişi nasıl aldığımızı açıklayabilir, çünkü yalnızca ön siparişin veya siparişin yalnızca ikili ağaçlara nasıl uygulanacağını biliyorum.
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)
Not:
DFS'nin nasıl çalıştığını biliyor musunuz? Eğer Ön sipariş 1. Eğer asgari ağırlığa sahip kök düğümünü seçerseniz, örn. ve sonra 2. arama yapın ve ağırlığı daha az olan başka bir düğümü seçip, ebeveyn ve onun dışındaki tüm diğer düğümler döngü oluşturmamalı ve hepsini kaplayana kadar 2. adımı tekrar etmelidir. verteks – CY5
DFS, bir (ikili) ağaçta olduğu gibi herhangi bir grafik üzerinde benzer şekilde çalışır; birincil fark, algoritmanın döngüsel grafiklerdeki döngüleri (ağaçta bulunmayan) açık bir şekilde engellemesidir. Bu, düğüm değerleri bazı tanımlanmış kurallara uyuyorsa, dolaylı olarak ele alınabilir. – user2864740