Menü

İlk Derinlik Araması (DFS) C ++ Programı Bir Grafiği veya Ağacı Gezmek İçin

  • Ana
  • Diğer
  • İlk Derinlik Araması (DFS) C ++ Programı Bir Grafiği veya Ağacı Gezmek İçin

depth first search c program traverse graph

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Bu Öğretici, Bir Grafiğin veya Ağacın Derinlemesine İlerletildiği C ++ 'da Derinliği İlk Aramayı (DFS) kapsar. Ayrıca DFS Algoritmasını ve Uygulamasını Öğreneceksiniz:

Önce derinlik arama (DFS), bir ağaç veya bir grafikte gezinmek için kullanılan başka bir tekniktir.

DFS, bir kök düğüm veya bir başlangıç ​​düğümü ile başlar ve ardından grafiğin veya ağacın daha derinlerine inerek geçerli düğümün bitişik düğümlerini araştırır. Bu, DFS'de düğümlerin alt öğesi olmayan bir düğümle karşılaşılıncaya kadar derinlemesine araştırıldığı anlamına gelir.

Yaprak düğüme ulaşıldığında, DFS geri döner ve benzer şekilde daha fazla düğümü keşfetmeye başlar.

=> Yeni Başlayanlar C ++ Eğitim Kılavuzuna Buradan Dikkat Edin.

Derinlik öncelikli arama

Ne öğreneceksin:

C ++ 'da Derinlik İlk Arama (DFS)

Düğümleri enlemesine araştırdığımız BFS'nin aksine, DFS'de düğümleri derinlemesine araştırıyoruz. DFS'de, keşfedilen düğümleri depolamak için bir yığın veri yapısı kullanıyoruz. Bizi keşfedilmemiş düğümlere götüren kenarlara 'keşif kenarları', zaten ziyaret edilmiş düğümlere giden kenarlara 'blok kenarları' denir.

Daha sonra, DFS tekniği için algoritmayı ve sözde kodu göreceğiz.

DFS Algoritması

  • Aşama 1: Yığına bir ağacın veya grafiğin kök düğümünü veya başlangıç ​​düğümünü ekleyin.
  • Adım 2: Yığından en üstteki öğeyi açın ve ziyaret edilenler listesine ekleyin.
  • Aşama 3: Ziyaret edilen olarak işaretlenen düğümün tüm bitişik düğümlerini bulun ve henüz ziyaret edilmemiş olanları yığına ekleyin.
  • 4. adım : Yığın boşalana kadar 2. ve 3. adımları tekrarlayın.

Sözde kod

DFS için sözde kod aşağıda verilmiştir.

DFS için sözde kod

Yukarıdaki sözde koddan, tüm köşelerin ziyaret edildiğinden emin olmak için DFS algoritmasının her köşede yinelemeli olarak çağrıldığını fark ettik.

Resimlerle Geçişler

Şimdi bir grafiğin DFS geçişini gösterelim. Netlik sağlamak amacıyla, BFS çiziminde kullandığımız grafiğin aynısını kullanacağız.

Çapraz geçişli DFS Çizimleri

0 başlangıç ​​düğümü veya kaynak düğüm olsun. İlk olarak, onu ziyaret edildi olarak işaretler ve ziyaret edilenler listesine ekleriz. Ardından yığındaki tüm bitişik düğümlerini itiyoruz.

Yığındaki tüm bitişik düğümleri itin

Daha sonra, işlemek için bitişik düğümlerden birini alırız, yani 1. yığının tepesini, ziyaret edilenler listesine ekleyerek ziyaret edilmiş olarak işaretleriz. Şimdi 1'in bitişik düğümlerini arayın. 0 zaten ziyaret edilenler listesinde olduğu için, onu yok sayıyoruz ve yığının en üstünde olan 2'yi ziyaret ediyoruz.

DFS Gösterimi - Adım 3

Ardından, 2. düğümü ziyaret edilmiş olarak işaretleriz. Bitişik düğümü 4 yığına eklenir.

DFS Çizim Adım 4

Ardından, yığının en üstünde ziyaret edilen 4'ü işaretliyoruz. Düğüm 4, zaten ziyaret edilmiş olan bitişiğinde yalnızca düğüm 2'ye sahiptir, bu nedenle onu görmezden geliriz.

DFS Çizim Adım 5

Bu aşamada, yığında yalnızca düğüm 3 bulunur. Komşu düğümü 0 zaten ziyaret edildi, bu nedenle onu görmezden geliyoruz. Şimdi 3'ü ziyaret edildi olarak işaretliyoruz.

DFS Çizim Adım 6

Şimdi yığın boştur ve ziyaret edilen liste, verilen grafiğin derinlik ilk geçişinin sırasını gösterir.

Verilen grafiği ve geçiş sırasını gözlemlersek, DFS algoritması için gerçekten grafiği derinlemesine gezdiğimizi ve ardından yeni düğümleri keşfetmek için onu tekrar geriye doğru izlediğimizi fark ederiz.

Derinlik İlk Arama Uygulaması

C ++ kullanarak DFS geçiş tekniğini uygulayalım.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Çıktı:

Verilen grafik için önce derinlik geçişi:

0 1 2 4 3

Örnekleme amaçlı kullandığımız programda grafiği bir kez daha kullandık. Tüm köşelerin ziyaret edildiğinden emin olmak için DFS algoritmasının (iki işleve ayrılmış) grafikteki her köşede yinelemeli olarak çağrıldığını görüyoruz.

Çalışma Zamanı Analizi

DFS'nin zaman karmaşıklığı BFS ile aynıdır, yani O (| V | + | E |) burada V köşe sayısıdır ve E belirli bir grafikteki kenar sayısıdır.

BFS'ye benzer şekilde, grafiğin az nüfuslu veya yoğun nüfuslu olmasına bağlı olarak, zaman karmaşıklığının hesaplanmasında baskın faktör sırasıyla köşeler veya kenarlar olacaktır.

Yinelemeli DFS

Yukarıda DFS tekniği için gösterilen uygulama doğası gereği özyinelemelidir ve bir işlev çağrı yığını kullanır. DFS uygulamak için başka bir varyasyonumuz var, ör. Yinelemeli derinlik arama ”. Bunda, ziyaret edilen köşeleri tutmak için açık yığını kullanıyoruz.

Aşağıda yinelemeli DFS için uygulamayı gösterdik. Bir kuyruk yerine yığın veri yapısını kullandığımız faktör dışında uygulamanın BFS ile aynı olduğuna dikkat edin.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Çıktı:

Yinelemeli Derinlik-ilk geçişin çıktısı:

0 3 2 4 1

Yinelemeli uygulamamızda kullandığımız grafiği kullanıyoruz. Çıktıdaki fark, yığını yinelemeli uygulamada kullanmamızdır. Yığınlar LIFO sırasını takip ettikçe, farklı bir DFS dizisi elde ederiz. Aynı sırayı elde etmek için, köşeleri ters sırada yerleştirmek isteyebiliriz.

BFS ve DFS

Şimdiye kadar, grafikler için hem geçiş tekniklerini, yani BFS ve DFS'yi tartıştık.

Şimdi ikisi arasındaki farklara bakalım.

BFSDFS
'Kapsamlı arama' anlamına gelir'Derinlik arama' anlamına gelir
Düğümler, enine seviye bazında incelenir.Düğümler, yalnızca yaprak düğümleri olana kadar derinlemesine araştırılır ve ardından diğer ziyaret edilmemiş düğümleri keşfetmek için geriye doğru izlenir.
BFS, kuyruk veri yapısı yardımıyla gerçekleştirilir.DFS, yığın veri yapısı yardımıyla gerçekleştirilir.
Performansta daha yavaş.BFS'den daha hızlı.
İki düğüm arasındaki en kısa yolu bulmada kullanışlıdır.Çoğunlukla grafiklerdeki döngüleri tespit etmek için kullanılır.

DFS Uygulamaları

  • Grafikteki Döngüleri Algılama: Bir grafikte DFS gerçekleştirirken bir arka kenar bulursak, grafiğin bir döngüsü olduğu sonucuna varabiliriz. Bu nedenle DFS, bir grafikteki döngüleri tespit etmek için kullanılır.
  • Yol bulma: İki köşe x ve y verildiğinde, DFS kullanarak x ve y arasındaki yolu bulabiliriz. Köşe x ile başlıyoruz ve sonra y ile karşılaşana kadar yığına giden yoldaki tüm köşeleri itiyoruz. Yığının içeriği x ve y arasındaki yolu verir.
  • Minimum Yayılma Ağacı ve En Kısa Yol: Ağırlıksız grafiğin DFS çapraz geçişi, bize minimum bir kapsayan ağaç ve düğümler arasındaki en kısa yolu verir.
  • Topolojik Sıralama: İşleri işler arasında verilen bağımlılıklardan planlamamız gerektiğinde topolojik sıralama kullanırız. Bilgisayar bilimi alanında, bunu çoğunlukla bağlayıcılardaki sembol bağımlılıklarını çözmek, veri serileştirmek, talimat zamanlaması vb. İçin kullanıyoruz. DFS, Topolojik sıralamada yaygın olarak kullanılmaktadır.

Sonuç

Son birkaç eğiticide, grafikler için iki geçiş tekniği, yani BFS ve DFS hakkında daha fazla araştırma yaptık. Her iki tekniğin uygulamalarını ve farklılıklarını gördük. BFS ve DFS, temelde bir grafiğin tüm düğümlerini ziyaret ederek aynı sonucu elde eder, ancak çıktının sırasına ve yapılma şekline göre farklılık gösterirler.

Her iki tekniğin de uygulanmasını gördük. BFS bir kuyruk kullanırken, DFS tekniği uygulamak için yığınlardan yararlanır. Bununla, grafikler için geçiş teknikleri hakkındaki öğreticiyi sonlandırıyoruz. Ağaçlarda da BFS ve DFS kullanabiliriz.

bilgisayardaki işletim sisteminin adı

Yaklaşan eğitimimizde bir grafiğin düğümleri arasındaki en kısa yolu bulmak için ağaçları ve birkaç algoritma hakkında daha fazla bilgi edineceğiz.

=> Tam C ++ Öğreticiler listesini Keşfetmek İçin Buraya Bakın.

Önerilen Kaynaklar

^