logo

TechCodeview

BFS algoritms

Šajā rakstā mēs apspriedīsim BFS algoritmu datu struktūrā. Meklēšana pēc platuma ir grafika šķērsošanas algoritms, kas sāk šķērsot grafiku no saknes mezgla un izpēta visus blakus esošos mezglus. Pēc tam tas atlasa tuvāko mezglu un izpēta visus neizpētītos mezglus. Izmantojot BFS šķērsošanai, jebkuru diagrammas mezglu var uzskatīt par saknes mezglu.

Ir daudz veidu, kā šķērsot grafiku, bet starp tiem BFS ir visbiežāk izmantotā pieeja. Tas ir rekursīvs algoritms, lai meklētu visas koka vai grafika datu struktūras virsotnes. BFS katru grafa virsotni iedala divās kategorijās – apmeklētās un neapmeklētās. Tas grafikā atlasa vienu mezglu un pēc tam apmeklē visus mezglus, kas atrodas blakus atlasītajam mezglam.

java xor

BFS algoritma pielietojumi

Platuma-vispirms-algoritma pielietojumi ir doti šādi:

  • BFS var izmantot, lai atrastu blakus esošās atrašanās vietas no noteiktas avota vietas.
  • Vienādranga tīklā BFS algoritmu var izmantot kā šķērsošanas metodi, lai atrastu visus blakus esošos mezglus. Lielākā daļa torrent klientu, piemēram, BitTorrent, uTorrent utt., izmanto šo procesu, lai tīklā atrastu 'sēklas' un 'vienaudžus'.
  • BFS var izmantot tīmekļa rāpuļprogrammās, lai izveidotu tīmekļa lapu indeksus. Tas ir viens no galvenajiem algoritmiem, ko var izmantot tīmekļa lapu indeksēšanai. Tas sāk pārvietošanos no avota lapas un seko saitēm, kas saistītas ar lapu. Šeit katra tīmekļa lapa tiek uzskatīta par diagrammas mezglu.
  • BFS tiek izmantots, lai noteiktu īsāko ceļu un minimālo pārklājuma koku.
  • BFS tiek izmantots arī Cheney tehnikā, lai dublētu atkritumu savākšanu.
  • To var izmantot Ford-Fulkerson metodē, lai aprēķinātu maksimālo plūsmu plūsmas tīklā.

Algoritms

Darbības, kas saistītas ar BFS algoritmu, lai izpētītu grafiku, ir norādītas šādi:

1. darbība: SET STATUS = 1 (gatavības stāvoklis) katram G mezglam

2. darbība: Ievietojiet sākuma mezglu A rindā un iestatiet tā STATUSS = 2 (gaidīšanas stāvoklis)

3. darbība: Atkārtojiet 4. un 5. darbību, līdz QUEUE ir tukša

4. darbība: Atvienojiet mezglu N. Apstrādājiet to un iestatiet tā STATUSS = 3 (apstrādāts stāvoklis).

5. darbība: Ievietojiet rindā visus N kaimiņus, kas atrodas gatavības stāvoklī (kuru STATUSS = 1) un iestatiet

viņu STATUSS = 2

(gaidīšanas stāvoklis)

[CILPAS BEIGAS]

6. darbība: IZEJA

algoritms bfs

BFS algoritma piemērs

Tagad, izmantojot piemēru, sapratīsim BFS algoritma darbību. Tālāk sniegtajā piemērā ir vērsts grafs ar 7 virsotnēm.

Meklēšanas algoritms platums vispirms

Iepriekš minētajā grafikā minimālo ceļu “P” var atrast, izmantojot BFS, kas sāksies no mezgla A un beigsies mezglā E. Algoritms izmanto divas rindas, proti, QUEUE1 un QUEUE2. QUEUE1 satur visus apstrādājamos mezglus, savukārt rindā QUEUE2 ir visi mezgli, kas tiek apstrādāti un dzēsti no QUEUE1.

Tagad sāksim izpētīt grafiku, sākot no mezgla A.

1. darbība - Vispirms pievienojiet A rindai1 un NULL rindai2.

 QUEUE1 = {A} QUEUE2 = {NULL}

2. darbība - Tagad izdzēsiet mezglu A no rindas1 un pievienojiet to rindai2. Ievietojiet visus mezgla A kaimiņus rindā1.

 QUEUE1 = {B, D} QUEUE2 = {A}

3. darbība - Tagad izdzēsiet mezglu B no rindas1 un pievienojiet to rindai2. Ievietojiet visus mezgla B kaimiņus rindā1.

 QUEUE1 = {D, C, F} QUEUE2 = {A, B}

4. darbība - Tagad izdzēsiet mezglu D no rindas1 un pievienojiet to rindai2. Ievietojiet visus mezgla D kaimiņus rindā1. Vienīgais mezgla D kaimiņš ir F, jo tas jau ir ievietots, tāpēc tas netiks ievietots vēlreiz.

 QUEUE1 = {C, F} QUEUE2 = {A, B, D}

5. darbība - Izdzēsiet mezglu C no rindas1 un pievienojiet to rindai2. Ievietojiet visus mezgla C kaimiņus rindā1.

unix izveidot direktoriju 
 QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C}

5. darbība - Izdzēsiet mezglu F no rindas1 un pievienojiet to rindai2. Ievietojiet visus mezgla F kaimiņus rindā1. Tā kā visi mezgla F kaimiņi jau ir klāt, mēs tos vairs neievietosim.

 QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F}

6. darbība - Dzēst mezglu E no rindas1. Tā kā visi kaimiņi jau ir pievienoti, mēs tos vairs neievietosim. Tagad visi mezgli ir apmeklēti, un mērķa mezgls E tiek sastapts rindā2.

kā izslēgt izstrādātāja režīmu Android 
 QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E}

BFS algoritma sarežģītība

BFS laika sarežģītība ir atkarīga no datu struktūras, ko izmanto grafika attēlošanai. BFS algoritma laika sarežģītība ir O(V+E) , jo sliktākajā gadījumā BFS algoritms pēta katru mezglu un malu. Grafā virsotņu skaits ir O(V), bet malu skaits ir O(E).

BFS kosmosa sarežģītību var izteikt kā O(V) , kur V ir virsotņu skaits.

BFS algoritma realizācija

Tagad apskatīsim BFS algoritma ieviešanu Java.

Šajā kodā mēs izmantojam blakus esošo sarakstu, lai attēlotu mūsu grafiku. Ieviešot Java platuma meklēšanas algoritmu, ir daudz vienkāršāk strādāt ar blakus esošo sarakstu, jo katram mezglam pievienoto mezglu sarakstam ir jāpārvietojas tikai tad, kad mezgls ir izņemts no rindas no rindas sākuma (vai sākuma).

Šajā piemērā grafiks, ko mēs izmantojam, lai parādītu kodu, ir norādīts šādi:

Meklēšanas algoritms platums vispirms 
 import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[vertex]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that&apos;s all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>