Menu

Breadth First Search (BFS) Program w C ++ do przechodzenia przez wykres lub drzewo

  • Główny
  • Inny
  • Breadth First Search (BFS) Program w C ++ do przechodzenia przez wykres lub drzewo

breadth first search c program traverse graph

Wypróbuj Nasz Instrument Do Eliminowania Problemów

Ten samouczek obejmuje pierwsze przeszukiwanie wszerz w C ++, w którym wykres lub drzewo jest przemieszczane wszerz. Nauczysz się również algorytmu i implementacji BFS:

Ten jawny samouczek języka C ++ zawiera szczegółowe wyjaśnienie technik przechodzenia, które można wykonać na drzewie lub na wykresie.

Traversal to technika, za pomocą której odwiedzamy każdy węzeł wykresu lub drzewa. Istnieją dwie standardowe metody przemierzania.

  • Przeszukiwanie wszerz (BFS)
  • Przeszukiwanie w głąb (DFS)

=> Zobacz tutaj, aby poznać pełną listę samouczków języka C ++.

java 8 pytania i odpowiedzi do wywiadu

Wyszukiwanie wszerz w C ++

Czego się nauczysz:

Technika Breadth First Search (BFS) w C ++

W tym samouczku omówimy szczegółowo technikę wyszukiwania wszerz.

W technice przechodzenia wszerz po wykresie lub drzewie przechodzi się wszerz. Technika ta wykorzystuje strukturę danych kolejki do przechowywania wierzchołków lub węzłów, a także do określenia, który wierzchołek / węzeł powinien zostać zajęty jako następny.

Algorytm wszerz zaczyna się od węzła głównego, a następnie przechodzi przez wszystkie sąsiednie węzły. Następnie wybiera najbliższy węzeł i bada wszystkie inne nieodwiedzone węzły. Ten proces powtarza się, dopóki wszystkie węzły na wykresie nie zostaną zbadane.

Algorytm wyszukiwania wszerz

Poniżej podano algorytm techniki BFS.

Rozważmy G jako wykres, przez który będziemy przemierzać algorytm BFS.

Niech S będzie węzłem głównym / początkowym wykresu.

  • Krok 1: Zacznij od węzła S i umieść go w kolejce.
  • Krok 2: Powtórz poniższe kroki dla wszystkich węzłów na wykresie.
  • Krok 3: Usuń S z kolejki i przetwórz go.
  • Krok 4: Umieść w kolejce wszystkie sąsiednie węzły S i przetwórz je.
  • (KONIEC PĘTLI)
  • Krok 6: WYJŚCIE

Pseudo kod

Pseudokod dla techniki BFS jest podany poniżej.

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

Przejścia z ilustracjami

Ilustracje BFS Krok 1

Niech 0 będzie początkowym węzłem lub węzłem źródłowym. Najpierw umieszczamy go w kolejce odwiedzanej i wszystkich sąsiednich węzłów w kolejce.

Ilustracje BFS Krok 2

Następnie bierzemy jeden z sąsiednich węzłów do przetworzenia, tj. 1. Oznaczamy go jako odwiedzony, usuwając go z kolejki i umieszczając w kolejce sąsiednie węzły (2 i 3 są już w kolejce). Ponieważ 0 jest już odwiedzone, ignorujemy je.

co to jest system operacyjny komputera

Ilustracje BFS Krok 3

Następnie usuwamy węzeł 2 z kolejki i oznaczamy go jako odwiedzony. Następnie sąsiedni węzeł 4 jest dodawany do kolejki.

Ilustracje BFS Krok 4

Następnie usuwamy 3 z kolejki i oznaczamy jako odwiedzone. Węzeł 3 ma tylko jeden sąsiedni węzeł, tj. 0, który jest już odwiedzony. Dlatego ignorujemy to.

Ilustracje BFS Krok 5

Na tym etapie w kolejce jest tylko węzeł 4. Jego sąsiedni węzeł 2 jest już odwiedzony, dlatego go ignorujemy. Teraz oznaczamy 4 jako odwiedzone.

Ilustracje BFS Krok 6

Następnie sekwencja obecna na liście odwiedzonych jest pierwszym przejściem wszerz danego wykresu.

Jeśli obserwujemy dany wykres i sekwencję przemierzania, możemy zauważyć, że w przypadku algorytmu BFS rzeczywiście przechodzimy przez wykres wszerz, a następnie przechodzimy do następnego poziomu.

Wdrożenie BFS

#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): '<

Wynik:

tablice i funkcje c ++

Przejście wszerz dla danego wykresu (z 0 jako węzłem początkowym):

0 1 2 3 4

Wdrożyliśmy BFS w powyższym programie. Zauważ, że wykres ma postać listy sąsiedztwa, a następnie używamy iteratora do iteracji po liście i wykonywania BFS.

Użyliśmy tego samego wykresu, którego użyliśmy do celów ilustracyjnych, jako danych wejściowych do programu do porównania sekwencji przechodzenia.

Analiza czasu działania

Jeśli V jest liczbą wierzchołków, a E jest liczbą krawędzi grafu, to złożoność czasową dla BFS można wyrazić jako O (| V | + | E |) . Powiedziawszy to, zależy to również od struktury danych, której używamy do przedstawienia wykresu.

Jeśli używamy listy sąsiedztwa (jak w naszej implementacji), to złożoność czasowa wynosi O (| V | + | E |).

Jeśli użyjemy macierzy sąsiedztwa, to złożoność czasowa wynosi O (V ^ 2) .

Oprócz zastosowanych struktur danych istnieje również czynnik, czy wykres jest gęsto zapełniony, czy rzadko.

Kiedy liczba wierzchołków przekracza liczbę krawędzi, wówczas mówi się, że graf jest słabo połączony, ponieważ będzie wiele rozłączonych wierzchołków. W tym przypadku złożoność czasowa wykresu będzie wynosić O (V).

Z drugiej strony, czasami wykres może mieć większą liczbę krawędzi niż liczba wierzchołków. W takim przypadku mówi się, że wykres jest gęsto wypełniony. Złożoność czasowa takiego wykresu wynosi O (E).

Podsumowując, to, co oznacza wyrażenie O (| V | + | E |), zależy od tego, czy wykres jest gęsto czy słabo zapełniony, dominujący czynnik, tj. Krawędzie lub wierzchołki, określi odpowiednio złożoność czasową wykresu.

Zastosowania BFS Traversal

  • Zbieranie śmieci: Technika zbierania elementów bezużytecznych, „algorytm Cheneya”, wykorzystuje przechodzenie wszerz do kopiowania funkcji czyszczenia pamięci.
  • Nadawanie w sieciach: Pakiet przemieszcza się z jednego węzła do drugiego przy użyciu techniki BFS w sieci rozgłoszeniowej, aby dotrzeć do wszystkich węzłów.
  • Nawigacja GPS: Możemy użyć BFS w nawigacji GPS, aby znaleźć wszystkie sąsiednie lub sąsiednie węzły lokalizacji.
  • Serwisy społecznościowe: Mając osobę „P”, możemy znaleźć wszystkie osoby w odległości „d” od p, używając BFS do poziomów d.
  • Sieci równorzędne: Ponownie BFS może być używany w sieciach peer to peer, aby znaleźć wszystkie sąsiednie węzły.
  • Najkrótsza ścieżka i minimalne drzewo rozpinające na nieważonym wykresie: Technika BFS służy do znalezienia najkrótszej ścieżki, tj. Ścieżki z najmniejszą liczbą krawędzi na wykresie nieważonym. Podobnie możemy również znaleźć minimalne drzewo rozpinające za pomocą BFS na wykresie nieważonym.

Wniosek

Technika przeszukiwania wszerz jest metodą używaną do przeszukiwania wszystkich węzłów grafu lub drzewa wszerz.

Technika ta jest najczęściej używana do znajdowania najkrótszej ścieżki między węzłami grafu lub w aplikacjach, które wymagają od nas odwiedzenia każdego sąsiedniego węzła, jak w sieciach.

=> Kliknij tutaj, aby uzyskać bezpłatny kurs C ++.

rekomendowane lektury

^