Menü

Bir Grafiği veya Ağacı Gezmek için Kapsamlı İlk Arama (BFS) C ++ Programı

  • Ana
  • Diğer
  • Bir Grafiği veya Ağacı Gezmek için Kapsamlı İlk Arama (BFS) C ++ Programı

breadth first search c program traverse graph

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

Bu Öğretici, Grafik veya Ağacın Enine Yönlendirildiği C ++ 'da Kapsamlı İlk Aramayı kapsar. Ayrıca BFS Algoritmasını ve Uygulamasını Öğreneceksiniz:

Bu açık C ++ öğreticisi, bir ağaç veya grafik üzerinde gerçekleştirilebilecek geçiş tekniklerinin ayrıntılı bir açıklamasını verecektir.

Geçiş, grafiğin veya bir ağacın her bir düğümünü ziyaret ettiğimiz tekniktir. İki standart geçiş yöntemi vardır.

  • Kapsamlı arama (BFS)
  • Önce derinlik arama (DFS)

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

fonksiyonel test ve fonksiyonel olmayan test

C ++

Ne öğreneceksin:

C ++ 'da Kapsamlı İlk Arama (BFS) Tekniği

Bu eğitimde, en geniş arama tekniğini ayrıntılı olarak tartışacağız.

Enine geçiş tekniğinde, grafik veya ağaç enine boydan boya geçilir. Bu teknik, kuyruk veri yapısını, köşeleri veya düğümleri depolamak ve ayrıca daha sonra hangi köşe / düğümün alınması gerektiğini belirlemek için kullanır.

Genişlik-önce algoritma kök düğüm ile başlar ve ardından tüm bitişik düğümleri geçer. Ardından en yakın düğümü seçer ve diğer tüm ziyaret edilmemiş düğümleri araştırır. Bu işlem, grafikteki tüm düğümler keşfedilene kadar tekrarlanır.

Enine İlk Arama Algoritması

Aşağıda BFS tekniği için algoritma verilmiştir.

G'yi, BFS algoritmasını kullanarak geçeceğimiz bir grafik olarak düşünün.

S grafiğin kök / başlangıç ​​düğümü olsun.

  • Aşama 1: S düğümü ile başlayın ve kuyruğa alın.
  • Adım 2: Grafikteki tüm düğümler için aşağıdaki adımları tekrarlayın.
  • Aşama 3: S'yi kuyruktan çıkarın ve işleyin.
  • 4. Adım: S'nin tüm bitişik düğümlerini sıraya koyun ve işleyin.
  • (DÖNGÜSÜNÜN SONU)
  • 6. Adım: ÇIKIŞ

Sözde kod

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

Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end

Resimlerle Geçişler

BFS Çizimleri Adım 1

0 başlangıç ​​düğümü veya kaynak düğüm olsun. İlk olarak, onu ziyaret edilen sıraya ve sıradaki tüm bitişik düğümlerine sıralıyoruz.

BFS Çizimler Adım 2

Sonra, işlemek için bitişik düğümlerden birini alırız, yani 1. Onu kuyruktan çıkararak ziyaret edilmiş olarak işaretleriz ve bitişik düğümlerini sıraya koyarız (2 ve 3 zaten sıraya girmiştir). 0 zaten ziyaret edildiğinden, onu görmezden geliyoruz.

satış noktası için ipad kullanma

BFS Çizimleri 3. Adım

Ardından, düğüm 2'yi sıradan çıkarır ve ziyaret edilmiş olarak işaretleriz. Daha sonra, bitişiğindeki 4 nolu düğüm kuyruğa eklenir.

BFS Çizimler Adım 4

Ardından, kuyruktan 3 tanesini çıkarır ve ziyaret edilmiş olarak işaretleriz. Düğüm 3, yalnızca bir bitişik düğüme sahiptir, yani zaten ziyaret edilmiş olan 0'dır. Bu nedenle, onu görmezden geliyoruz.

BFS Çizimler Adım 5

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

BFS Çizimleri 6. Adım

Daha sonra, ziyaret edilen listede bulunan sıra, verilen grafiğin enine ilk geçişidir.

Verilen grafiği ve geçiş sırasını gözlemlersek, BFS algoritması için gerçekten de grafiği enine boydan boya geçip bir sonraki seviyeye geçtiğimizi fark edebiliriz.

BFS Uygulaması

#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '<

Çıktı:

en iyi sabit disk klonlama yazılımı Windows 10

Verilen grafik için Genişlik-İlk Geçiş (başlangıç ​​düğümü olarak 0 ile):

0 1 2 3 4

BFS'yi yukarıdaki programda uyguladık. Grafiğin bir bitişiklik listesi biçiminde olduğuna dikkat edin ve ardından listeyi yinelemek ve BFS gerçekleştirmek için bir yineleyici kullanırız.

Geçiş sırasını karşılaştırmak için programa girdi olarak örnekleme amacıyla kullandığımız grafiği kullandık.

Çalışma Zamanı Analizi

V köşelerin sayısı ve E bir grafiğin kenarlarının sayısı ise, BFS için zaman karmaşıklığı şu şekilde ifade edilebilir: O (| V | + | E |) . Bunu söyledikten sonra, grafiği temsil etmek için kullandığımız veri yapısına da bağlıdır.

Bitişiklik listesini kullanırsak (uygulamamızdaki gibi), zaman karmaşıklığı şu şekildedir: O (| V | + | E |).

Bitişik matrisini kullanırsak, zaman karmaşıklığı şu şekildedir: O (V ^ 2) .

Kullanılan veri yapılarının yanı sıra, grafiğin yoğun şekilde mi yoksa seyrek olarak mı doldurulduğuna dair bir faktör de vardır.

Köşelerin sayısı kenarların sayısını aştığında, birçok bağlantısız köşe olacağından grafiğin seyrek olarak bağlı olduğu söylenir. Bu durumda grafiğin zaman karmaşıklığı O (V) olacaktır.

Öte yandan, bazen grafiğin köşe sayısından daha fazla sayıda kenarı olabilir. Böyle bir durumda grafiğin yoğun nüfuslu olduğu söylenir. Böyle bir grafiğin zaman karmaşıklığı O (E) 'dir.

Sonuç olarak, O (| V | + | E |) ifadesinin ne anlama geldiği, grafiğin yoğun veya seyrek olarak doldurulmuş olmasına bağlıdır; baskın faktör, yani kenarlar veya köşeler buna göre grafiğin zaman karmaşıklığını belirleyecektir.

BFS Geçiş Uygulamaları

  • Çöp toplama: Çöp toplama tekniği olan 'Cheney'in algoritması', çöp toplamayı kopyalamak için enine geçişi kullanır.
  • Ağlarda Yayın: Bir paket, tüm düğümlere ulaşmak için yayın ağındaki BFS tekniğini kullanarak bir düğümden diğerine geçer.
  • GPS navigasyon: Tüm bitişik veya komşu konum düğümlerini bulmak için GPS navigasyonunda BFS kullanabiliriz.
  • Sosyal ağ siteleri: Bir kişi 'P' verildiğinde, belirli bir mesafedeki tüm insanları bulabiliriz, 'd' BFS kullanarak p'den d seviyelerine kadar.
  • Eşler Arası Ağlar: Yine BFS, tüm bitişik düğümleri bulmak için eşler arası ağlarda kullanılabilir.
  • Ağırlıksız Grafikteki En Kısa Yol ve Minimum Kapsama Ağacı: BFS tekniği, en kısa yolu, yani ağırlıksız grafikte en az sayıda kenara sahip yolu bulmak için kullanılır. Benzer şekilde, ağırlıksız grafikte BFS kullanarak minimum bir kapsayan ağaç da bulabiliriz.

Sonuç

Enine arama tekniği, bir grafiğin veya bir ağacın tüm düğümlerini enine boyda geçmek için kullanılan bir yöntemdir.

Bu teknik çoğunlukla bir grafiğin düğümleri arasındaki en kısa yolu bulmak için veya ağlarda olduğu gibi her bitişik düğümü ziyaret etmemizi gerektiren uygulamalarda kullanılır.

=> Ücretsiz C ++ Kursu İçin Buraya Tıklayın.

Önerilen Kaynaklar

^