DFS ile Çizgelerin Gezilmesi

Bir önceki blogumuzda çizgelerin nasıl bilgisayar ortamında gösterilebileceği göstermiştik. Bu yazıyı okumadan önce o yazıya bir göz atmanızı şiddetle yavsiye ederiz. http://bilimolimpiyatları.com/2019/04/01/cizgelerin-bilgisayarda-gosterilmesi/ Şimdi ise çizgelerin DFS(Depth First Search) algoritması kullanılarak nasıl dolaşılabileceğini inceleyiz.

DFS algoritmasının çalışma mantığı, çizge üzerinde geri dönmeden ilerleyebileceğimiz kadar ilerlemeye, bütün komşuları daha önceden ziyaret edilmiş olan bir düğüme geldiğimizde ise aynı yoldan daha önceden ziyaret edilmemiş bir düğüm bulana kadar geri dönülerek aynı işlemi tekrar etmeye dayanır.

Yukarıdaki çizgede 0 noktasından başlayarak dfs algoritmasını uygulamaya başladığımızda ilk önce 0 – 2 – 3 şeklinde ilerlenir, ardından geri dönülür ve işleme 4. düğümden devam edilir. En sonda yaptığımız hareket 0 – 2 – 3 – 4 – 1 – 6 – 5 şeklinde olur. Dikkat edilmesi gereken nokta, ilk başta ve algoritma sırasında seçtiğimiz düğümlere göre hareketimizin değişebileceğidir. Mesela 0 – 5 – 4 – 2 – 3 – 6 – 1 veya 1 – 4 – 6 – 2 – 3 – 0 – 5 de olası durumlardandır.

Bu algoritmayı bilgisayara uyarlamak için kendine yinelemeli bir dfs(v) fonksiyonu tanımlayalım. Burada v parametresi, fonksiyonun inceleyeceği düğümdür. Fonksiyonumuz, ilk önce v düğümünü işaretler (bunu ayrı bir dizi tutarak yapabiliriz). Ardından v düğümünün bütün komşularını teker teker inceler. Eğer işaretlenmemiş bir u düğümü bulursa, dfs(u) fonksiyonunu çağırır. Fonksiyon, bütün kenarlar gezilince sona erer.

#include <bits/stdc++.h>
#define MAXEDGE 100
using namespace std;
vector<int> g[MAXEDGE];

bool vis[MAXEDGE];
//Bu dizide 0 değerleri
//işaretlenmemiş, 1 değerleri ise
//işaretlenmiş düğümleri gösterir.
//İlk durumda dizideki bütün
//değerler sıfırdır.

int d, k;
void dfs(int v){
    cout << v << " ";
    //Düğümleri hangi sırayla gezdiğimizi
    //görebilmek için bulunduğumuz kenarı
    //yazdıralım.

    vis[v] = 1;
    //Bulunduğumuz düğüm işaretlenir.

    for(auto u : g[v])
        if(vis[u] == 0)
            dfs(u);
    //v düğümünün bütün komşuları
    //incelenir. İşaretlenmemiş bir 
    //komşu bulunduğunda dfs fonksiyonu
    //oradan çağrılır.
}

int main(){
    cin >> d >> k;
    int i, j;
    while(k--){
        cin >> i >> j;
        g[i].push_back(j);
        g[j].push_back(i);
    }

    dfs(0); 
    //Fonksiyon 0 numaralı düğümden başlatılır.
}

Bu programa

7 7
0 2
2 3
2 4
4 1
4 6
4 5
0 5

girdileri verildiğinde yukarıdaki resimde gösterilen çizge dfs kullanılarak gezilir. Bu algoritmada her düğüm bir kere gezildiği ve her kenar maksimum bir kere gezildiği için k kenar sayısı ve d düğüm sayısı olmak üzere zaman karmaşıklığı O(k + d)’ dir.

DFS kullanılarak örnek soru çözüm için buraya tıklayabilirsiniz.http://bilimolimpiyatları.com/2019/04/02/dfs-kullanilarak-ornek-soru-cozumu/

Add a Comment

Your email address will not be published. Required fields are marked *