Depth First Search

Yazar : Hakan 84 kez okundu Tarih : 19 Haziran 2017 19:28

DFS ( Depth-First Search ) graf üzerinde en uzak düğüme kadar dolaşma yöntemlerinden biridir. Önce derinlik ( en uzak düğüm ) araması olarak bilinir.

# bir graf oluşuturuyoruz. 
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}
# fonksiyonumaza grafımızı ve başlangıç noktamızı veriyoruz.
def dfs(graph, start):
    # visited isminde daha önce ziyaret ettiğimiz noktaları ekleyeceğimiz boş bir küme oluşturuyoruz. stack ise başlangıç noktamızın içerdiği bir liste
    visited, stack = set(), [start]
    # Döngümüz stack listesi bitene kadar dönecek
    while stack:
        # verteck'e stack'in son elemanını atıyoruz ve stack'ten son elemanı çıkartıyoruz. 
        vertex = stack.pop()
        print(graph[vertex])
        if vertex not in visited:
            # daha önce ziyaret edilmediyse visited'a elemanı ekliyoruz.
            visited.add(vertex)
            # Eklediğimiz elemanın graftaki kümesinden daha önce ziyaret edilenlerin bulunduğu visited listesini çıkartıyoruz ki daha önce ziyaret edilmişse bir daha ziyaret edilmesin.
            stack.extend(graph[vertex] - visited)
    return visited
print(dfs(graph, 'E'))

 

Etiketler : dept-first-search, dept-first-search, python-dept-first-search, python-dept-first-search, önce-derinlik-araması, önce-derinlik-araması,

Yazar : Hakan - Kategori: Python - Tarih: 19 Haziran 2017

blog comments powered by Disqus

Popüler Yazılar

Python ile fotoğraflarınızı byte byte okuyun

Hadi fotoğraflarımızı byte byte okuyalım ...

Hızlıca büyük dosya oluşturma

Çok sıklıkla özellikle nginx/apache kontrol ...

Linux Yaz Kampı Python Eğitimi

Merhaba Arkadaşlar. Bu sene Linux ...

Bubble Sort ( kabarcık sıralaması )

Kabarcık sıralama yazılması basit bir ...

Mac OS'a python 3 kurulumu

Mac OS'da python 2 default ...