Pirmoji pločio paieška (BFS) yra esminis dalykas grafiko perėjimo algoritmas . Tai apima apsilankymą visuose prijungtuose grafiko mazguose kiekvienam lygiui. Šiame straipsnyje apžvelgsime sąvoką BFS ir kaip jis gali būti veiksmingai pritaikytas grafikams

Turinys

• „Breadth First Search“ arba BFS diagramai
• Ryšys tarp BFS grafui ir BFS medžiui
• Pirmoji pločio paieška (BFS) grafiko algoritmui
• Kaip veikia BFS algoritmas?
• BFS for Graph įgyvendinimas naudojant gretimų sąrašą
• Plotumo pirmosios paieškos (BFS) algoritmo sudėtingumas
• BFS taikymas grafikuose
• Problemos, susijusios su pločio paieška arba grafiko BFS
• DUK apie grafiko paiešką pagal plotį pirmiausia (BFS).

Diagramos paieška pagal plotį pirmiausia (BFS):

Pirmoji pločio paieška (BFS) yra grafiko apėjimo algoritmas, kuris ištiria visas grafiko viršūnes esamame gylyje, prieš pereinant prie viršūnių kitame gylio lygyje. Jis prasideda nuo nurodytos viršūnės ir aplanko visus savo kaimynus, prieš pereidamas į kitą kaimynų lygį. BFS dažniausiai naudojamas algoritmuose, skirtuose kelio paieškai, sujungtiems komponentams ir trumpiausio kelio problemoms grafikuose.

Ryšys tarp BFS for Graph ir BFS for Tree:

Diagramos skersmuo pirmas skersmuo (BFS) yra panašus į Plotis – pirmasis medžio apvažiavimas .

Vienintelis laimėjimas čia yra tas, kad, priešingai medžiai , grafikus gali būti ciklų, todėl galime vėl patekti į tą patį mazgą. Kad mazgas nebūtų apdorotas daugiau nei vieną kartą, viršūnes skirstome į dvi kategorijas:

• Aplankė ir
• Nelankytas.

Būlio aplankytas masyvas naudojamas aplankytoms viršūnėms pažymėti. Paprastumo dėlei daroma prielaida, kad visos viršūnės pasiekiamos iš pradinės viršūnės. BFS naudoja a Grafiko algoritmo paieška pagal plotį pirmiausia (BFS):

Aptarkime BFS algoritmą:

1. Inicijavimas: Įtraukite pradinį mazgą į eilę ir pažymėkite jį kaip aplankytą.
2. Tyrinėjimas: Kol eilė nėra tuščia:
   • Ištraukite mazgą iš eilės ir apsilankykite jame (pvz., išspausdinkite jo vertę).
   • Kiekvienam nelankytam iškelto mazgo kaimynui:
     • Į eilę įtraukite kaimyną.
     • Pažymėkite kaimyną kaip aplankytą.
3. Nutraukimas: Kartokite 2 veiksmą, kol eilė bus tuščia.

Šis algoritmas užtikrina, kad visi grafiko mazgai būtų aplankomi pirmiausia, pradedant nuo pradinio mazgo.

Kaip veikia BFS algoritmas?

Pradedant nuo šaknies, pirmiausia aplankomi visi tam tikro lygio mazgai, o tada perkeliami kito lygio mazgai, kol aplankomi visi mazgai.

Tam naudojama eilė. Visi gretimi dabartinio lygio neaplankyti mazgai nustumiami į eilę, o dabartinio lygio mazgai pažymimi aplankyti ir iškeliami iš eilės.

Iliustracija:

Supraskime algoritmo veikimą naudodami šį pavyzdį.

1 žingsnis: Iš pradžių eilė ir lankomi masyvai yra tušti.

Eilė ir lankomi masyvai iš pradžių tušti.

2 žingsnis: Įstumkite mazgą 0 į eilę ir pažymėkite jį aplankytą.

dhanashree verma

Įstumkite mazgą 0 į eilę ir pažymėkite jį aplankytą.

3 veiksmas: Pašalinkite 0 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus bei įstumkite juos į eilę.

Pašalinkite 0 mazgą iš eilės priekio ir aplankė nelankytus kaimynus ir įstumkite į eilę.

4 veiksmas: Pašalinkite 1 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus ir įstumkite juos į eilę.

Pašalinkite 1 mazgą iš eilės priekio ir aplankė nelankytus kaimynus ir stumkite

5 veiksmas: Pašalinkite 2 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus bei įstumkite juos į eilę.

Pašalinkite 2 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus bei įstumkite juos į eilę.

6 veiksmas: Pašalinkite 3 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus ir įstumkite juos į eilę.
Matome, kad kiekvienas 3 mazgo kaimynas yra aplankytas, todėl pereikite prie kito mazgo, esančio eilės priekyje.

Pašalinkite 3 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus ir įstumkite juos į eilę.

7 žingsniai: Pašalinkite 4 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus ir įstumkite juos į eilę.
Matome, kad visi 4 mazgo kaimynai yra lankomi, todėl pereikite prie kito mazgo, esančio eilės priekyje.

Pašalinkite 4 mazgą iš eilės priekio ir aplankykite nelankytus kaimynus ir įstumkite juos į eilę.

Dabar eilė tampa tuščia, todėl nutraukite šį iteracijos procesą.

BFS diegimas diagramai naudojant gretimų sąrašą:

#include  #include  #include  using namespace std; // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(vector>& adjList, int startMazgas, vektorius & aplankyta) { // Sukurkite eilę BFS eilei q;  // Pažymėkite dabartinį mazgą kaip aplankytą ir įtraukite jį į eilę [startNode] = true;  q.push(startNode);  // Pakartokite eilę, o (!q.empty()) { // Iškelkite viršūnę iš eilės ir išspausdinkite ją int currentNode = q.front();  q.pop();  cout<< currentNode << ' ';  // Get all adjacent vertices of the dequeued vertex  // currentNode If an adjacent has not been visited,  // then mark it visited and enqueue it  for (int neighbor : adjList[currentNode]) {  if (!visited[neighbor]) {  visited[neighbor] = true;  q.push(neighbor);  }  }  } } // Function to add an edge to the graph void addEdge(vector>& adjSąrašas, int u, int v) { adjSąrašas[u].push_back(v); } int main() { // Viršūnių skaičius grafe int viršūnės = 5;  // Grafiko vektoriaus gretimų sąrašo atvaizdavimas> adjList(viršūnės);  // Pridėti briaunų į grafiką addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Pažymėkite visas viršūnes kaip neaplankytus vektorius aplankytas(viršūnės, false);  // Atlikite BFS perėjimą pradedant nuo viršūnės 0 cout<< 'Breadth First Traversal starting from vertex '  '0: ';  bfs(adjList, 0, visited);  return 0; }>

#include  #include  #define MAX_VERTICES 100 // Structure to represent a node in adjacency list struct Node {  int data;  struct Node* next; }; // Function to create a new node struct Node* createNode(int data) {  struct Node* newNode  = (struct Node*)malloc(sizeof(struct Node));  newNode->duomenys = duomenys;  newNode->ext = NULL;  grąžinti naująNode; } // Funkcija pridėti briauną į grafiką void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v);  naujasMazgas->kitas = adjList[u];  adjList[u] = naujasMazgas; } // Funkcija atlikti pirmąją paiešką grafe // vaizduojama naudojant gretimų sąrašą void bfs(struct Node* adjList[], int viršūnės, int startMazgas, aplankytas int[]) { // Sukurti eilę BFS int eilei[ MAX_VERTICES];  int priekyje = 0, gale = 0;  // Pažymėkite dabartinį mazgą kaip aplankytą ir įtraukite jį į eilę [startNode] = 1;  queue[rear++] = startNode;  // Pakartokite eilę, o (priekyje != gale) { // Nuimkite viršūnę iš eilės ir išspausdinkite ją int currentNode = eilė[priekis++];  printf('%d ', currentNode);  // Gauti visas gretimas iškeltos viršūnės viršūnes // currentMazgas Jei gretima nebuvo aplankyta, // tada pažymėkite ją aplankytą ir įtraukite į eilę struct Mazgas* temp = adjSąrašas[dabartinisMazgas];  while (temp != NULL) { int kaimynas = temp->duomenys;  if (!aplankė[kaimynas]) { aplankė[kaimynas] = 1;  eilė[galinis++] = kaimynas;  } temp = temp->kitas;  } } } int main() { // Grafo viršūnių skaičius int viršūnės = 5;  // Grafo struktūros gretimų sąrašo atvaizdavimas Mazgas* adjSąrašas[viršūnės];  už (int i = 0; i< vertices; ++i)  adjList[i] = NULL;  // Add edges to the graph  addEdge(adjList, 0, 1);  addEdge(adjList, 0, 2);  addEdge(adjList, 1, 3);  addEdge(adjList, 1, 4);  addEdge(adjList, 2, 4);  // Mark all the vertices as not visited  int visited[vertices];  for (int i = 0; i < vertices; ++i)  visited[i] = 0;  // Perform BFS traversal starting from vertex 0  printf(  'Breadth First Traversal starting from vertex 0: ');  bfs(adjList, vertices, 0, visited);  return 0; }>

import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph {  int vertices;  LinkedList [] adjList;  @SuppressWarnings('nepažymėta') Grafas(int viršūnės) { this.vertices = viršūnės;  adjList = naujas LinkedList[viršūnės];  už (int i = 0; i< vertices; ++i)  adjList[i] = new LinkedList();  }  // Function to add an edge to the graph  void addEdge(int u, int v) { adjList[u].add(v); }  // Function to perform Breadth First Search on a graph  // represented using adjacency list  void bfs(int startNode)  {  // Create a queue for BFS  Queue eilė = naujas LinkedList();  loginis [] aplankytas = naujas loginis [viršūnės];  // Pažymėkite dabartinį mazgą kaip aplankytą ir įtraukite jį į eilę [startNode] = true;  queue.add(startNode);  // Pakartokite eilę, o (!queue.isEmpty()) { // Iškelkite viršūnę iš eilės ir išspausdinkite ją int currentNode = queue.poll();  System.out.print(currentNode + ' ');  // Gauti visas gretimas iškeltos eilės viršūnes // viršūnė currentNode Jei gretima // nebuvo aplankyta, pažymėkite ją aplankytą ir // įtraukite į eilę (int kaimynas : adjSąrašas[dabartinis mazgas]) { if (!aplankytas[kaimynas] ) { lankėsi[kaimynas] = tiesa;  queue.add(kaimynas);  } } } } } public class Main { public static void main(String[] args) { // Grafo viršūnių skaičius int viršūnės = 5;  // Grafo kūrimas Grafas graph = new Graph(vertices);  // Grafo grafo kraštinių įtraukimas.addEdge(0, 1);  graph.addEdge(0, 2);  graph.addEdge(1, 3);  graph.addEdge(1, 4);  graph.addEdge(2, 4);  // Atlikite BFS perėjimą, pradedant nuo viršūnės 0 System.out.print( 'Pločio pirmas praėjimas pradedant nuo viršūnės 0: ');  graph.bfs(0);  } }>>Python3

using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph {  int vertices;  List [] adjList;  public Graph(int viršūnės) { this.vertices = viršūnės;  adjList = naujas sąrašas [ viršūnės ];  už (int i = 0; i< vertices; ++i)  adjList[i] = new List ();  } // Funkcija pridėti briauną į grafiką public void AddEdge(int u, int v) { adjList[u].Add(v); } // Funkcija atlikti pirmąją paiešką grafike // vaizduojama naudojant gretimų sąrašą public void BFS(int startNode) { // Sukurti eilę BFS eilei eilė = nauja eilė ();  bool[] aplankytas = naujas bool[viršūnės];  // Pažymėkite dabartinį mazgą kaip aplankytą ir įtraukite jį į eilę [startNode] = true;  eilė.Enqueue(startNode);  // Pakartokite eilėje while (eilė.Skaičius != 0) { // Iš eilės iškelkite viršūnę ir išspausdinkite ją int currentNode = queue.Dequeue();  Console.Write(currentNode + ' ');  // Gauti visas gretimas iškeltos eilės viršūnes // viršūnė currentNode Jei gretima // nebuvo aplankyta, tada pažymėkite ją aplankytą ir // įeikite ją į eilę foreach(int kaimynas adjList[currentNode]) { if (!visited[neighbor] ) { lankėsi[kaimynas] = tiesa;  eilė.Eilė(kaimynas);  } } } } } class MainClass { public static void Main(string[] args) { // Grafo viršūnių skaičius int viršūnės = 5;  // Sukurti grafiką Grafas graph = new Graph(vertices);  // Pridėti briaunas į grafo grafiką.AddEdge(0, 1);  grafikas.AddEdge(0, 2);  grafikas.AddEdge(1, 3);  grafikas.AddEdge(1, 4);  grafikas.AddEdge(2, 4);  // Atlikite BFS perėjimą pradedant nuo viršūnės 0 Console.Write( 'Breadth First Traversal pradedant nuo viršūnės 0: ');  grafikas.BFS(0);  } }>>Javascript

Breadth First Traversal starting from vertex 0: 0 1 2 3 4>

Laiko sudėtingumas: O(V+E), kur V – mazgų skaičius, o E – briaunų skaičius.
Pagalbinė erdvė: O(V)

Plotumo pirmosios paieškos (BFS) algoritmo sudėtingumo analizė:

BFS algoritmo laiko sudėtingumas: O(V + E)

• BFS tiria visas grafiko viršūnes ir briaunas. Blogiausiu atveju jis vieną kartą aplanko kiekvieną viršūnę ir kraštą. Todėl BFS laiko sudėtingumas yra O(V + E), kur V ir E yra viršūnių ir briaunų skaičius duotame grafe.

BFS algoritmo erdvės sudėtingumas: O(V)

• BFS naudoja eilę, kad galėtų sekti viršūnes, kurias reikia aplankyti. Blogiausiu atveju eilėje gali būti visos grafo viršūnės. Todėl BFS erdvės sudėtingumas yra O(V), kur V ir E yra viršūnių ir briaunų skaičius duotame grafe.

BFS taikymas diagramose:

BFS turi įvairių pritaikymų grafų teorijoje ir kompiuterių moksle, įskaitant:

• Trumpiausio kelio radimas: BFS galima naudoti norint rasti trumpiausią kelią tarp dviejų nesvertinio grafiko mazgų. Stebint kiekvieno mazgo pirminį adresą perėjimo metu, galima atkurti trumpiausią kelią.
• Ciklo aptikimas: BFS gali būti naudojamas aptikti ciklus grafike. Jei mazgas aplankomas du kartus, tai rodo ciklo buvimą.
• Sujungti komponentai: BFS gali būti naudojamas sujungtiems komponentams identifikuoti grafike. Kiekvienas prijungtas komponentas yra mazgų, kuriuos galima pasiekti vienas iš kito, rinkinys.
• Topologinis rūšiavimas: BFS gali būti naudojamas topologiniam rūšiavimui atlikti nukreiptame acikliniame grafe (DAG). Topologinis rūšiavimas išdėsto mazgus tiesine tvarka taip, kad bet kurioje briaunoje (u, v) u būtų prieš v.
• Dvejetainių medžių lygio tvarka: BFS gali būti naudojamas norint atlikti dvejetainio medžio lygio tvarka. Šis perėjimas aplanko visus to paties lygio mazgus prieš pereinant į kitą lygį.
• Tinklo maršrutas: BFS gali būti naudojamas norint rasti trumpiausią kelią tarp dviejų tinklo mazgų, todėl jis naudingas nukreipiant duomenų paketus tinklo protokoluose.

Problemos, susijusios su grafiko paieška „Breadth First“ arba BFS:

DUK apie grafiko paiešką pagal plotį pirmiausia:

Klausimas 1: Kas yra BFS ir kaip jis veikia?

Atsakymas: BFS yra grafiko perėjimo algoritmas, kuris sistemingai tyrinėja grafiką, aplankydamas visas tam tikro lygio viršūnes, prieš pereinant į kitą lygį. Jis pradedamas nuo pradinės viršūnės, įtraukiamas į eilę ir pažymimas kaip aplankytas. Tada jis pašalina viršūnę iš eilės, aplanko ją ir į eilę įtraukia visus nelankytus kaimynus. Šis procesas tęsiamas tol, kol eilė bus tuščia.

2 klausimas: Kokios yra BFS programos?

Atsakymas: BFS turi įvairių programų, įskaitant trumpiausio kelio nesvertiniame grafike radimą, ciklų aptikimą diagramoje, nukreipto aciklinio grafiko (DAG) topologinį rūšiavimą, susietų komponentų radimą grafike ir galvosūkių, pvz., labirintų ir Sudoku, sprendimą.

3 klausimas: Koks yra BFS laiko sudėtingumas?

Atsakymas: BFS laiko sudėtingumas yra O(V + E), kur V – viršūnių skaičius, o E – kraštinių skaičius grafe.

4 klausimas: Koks yra BFS erdvės sudėtingumas?

Atsakymas: BFS erdvės sudėtingumas yra O(V), nes jis naudoja eilę, kad galėtų sekti viršūnes, kurias reikia aplankyti.

5 klausimas: Kokie yra BFS naudojimo pranašumai?

Atsakymas: BFS yra paprasta įdiegti ir veiksminga ieškant trumpiausio kelio nesvertiniame grafike. Tai taip pat garantuoja, kad visos grafiko viršūnės yra aplankytos.

Susiję straipsniai:

• Naujausi straipsniai apie BFS
• Pirmasis gylis
• Pirmojo pločio praėjimo taikymai
• Pirmosios gilumos paieškos programos
• Laiko ir erdvės sudėtingumas – pirmoji paieška (BFS)