У овом чланку ћемо разговарати о БФС алгоритму у структури података. Претрага у ширину је алгоритам обиласка графа који почиње да прелази граф од коренског чвора и истражује све суседне чворове. Затим бира најближи чвор и истражује све неистражене чворове. Док користите БФС за прелазак, било који чвор на графу се може сматрати основним чвором.
Постоји много начина да се пређе граф, али међу њима је БФС приступ који се најчешће користи. То је рекурзивни алгоритам за претраживање свих врхова структуре података дрвета или графа. БФС ставља сваки врх графа у две категорије - посећене и непосећене. Он бира један чвор у графу и, након тога, посећује све чворове који су суседни изабраном чвору.
Примене БФС алгоритма
Примене алгоритма у ширину су дате на следећи начин -
- БФС се може користити за проналажење суседних локација са дате изворне локације.
- У пеер-то-пеер мрежи, БФС алгоритам се може користити као метода преласка за проналажење свих суседних чворова. Већина торрент клијената, као што су БитТоррент, уТоррент, итд., користе овај процес за проналажење „семена“ и „вршњака“ у мрежи.
- БФС се може користити у веб претраживачима за креирање индекса веб страница. То је један од главних алгоритама који се може користити за индексирање веб страница. Почиње да прелази са изворне странице и прати везе повезане са страницом. Овде се свака веб страница сматра чвором на графу.
- БФС се користи за одређивање најкраће путање и минималног разапињућег стабла.
- БФС се такође користи у Цхенеиевој техници за дуплирање сакупљања смећа.
- Може се користити у методи Форд-Фулкерсон за израчунавање максималног протока у мрежи протока.
Алгоритам
Кораци укључени у БФС алгоритам за истраживање графикона су дати на следећи начин -
Корак 1: СЕТ СТАТУС = 1 (спремно стање) за сваки чвор у Г
Корак 2: Ставите почетни чвор А у ред и поставите његов СТАТУС = 2 (стање чекања)
убунту која команда
Корак 3: Поновите кораке 4 и 5 док КУЕУЕ не буде празан
4. корак: Искључите чвор Н. Обрадите га и поставите његов СТАТУС = 3 (обрађено стање).
5. корак: Ставите у ред све суседе Н који су у стању приправности (чији СТАТУС = 1) и поставите
њихов СТАТУС = 2
цомпарето метода јава
(стање чекања)
[КРАЈ ПЕТЉЕ]
Корак 6: ИЗЛАЗ
Пример БФС алгоритма
Сада, хајде да разумемо рад БФС алгоритма користећи пример. У доле наведеном примеру постоји усмерени граф који има 7 врхова.
У горњем графикону, минимална путања 'П' се може пронаћи коришћењем БФС-а који ће почети од чвора А и завршити у чвору Е. Алгоритам користи два реда, односно КУЕУЕ1 и КУЕУЕ2. КУЕУЕ1 садржи све чворове који ће се обрадити, док КУЕУЕ2 држи све чворове који су обрађени и избрисани из КУЕУЕ1.
Сада, почнимо да испитујемо граф почевши од чвора А.
Корак 1 - Прво додајте А у ред1 и НУЛЛ у ред2.
QUEUE1 = {A} QUEUE2 = {NULL} Корак 2 - Сада, избришите чвор А из реда1 и додајте га у ред2. Убаци све суседе чвора А у ред1.
QUEUE1 = {B, D} QUEUE2 = {A} Корак 3 - Сада, избришите чвор Б из реда1 и додајте га у ред2. Убаци све суседе чвора Б у ред1.
центрирање слика у цсс-у
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Корак 4 - Сада, избришите чвор Д из реда1 и додајте га у ред2. Убаци све суседе чвора Д у ред1. Једини сусед чвора Д је Ф пошто је већ уметнут, тако да неће бити поново уметнут.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Корак 5 - Избришите чвор Ц из реда1 и додајте га у ред2. Уметните све суседе чвора Ц у ред1.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Корак 5 - Избришите чвор Ф из реда1 и додајте га у ред2. Убаци све суседе чвора Ф у ред1. Пошто су сви суседи чвора Ф већ присутни, нећемо их поново убацивати.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Корак 6 - Избришите чвор Е из реда1. Пошто су сви његови суседи већ додати, па их нећемо поново убацивати. Сада су сви чворови посећени, а циљни чвор Е се налази у реду2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Сложеност БФС алгоритма
Временска сложеност БФС зависи од структуре података која се користи за представљање графикона. Временска сложеност БФС алгоритма је О(В+Е) , пошто у најгорем случају, БФС алгоритам истражује сваки чвор и ивицу. У графу, број темена је О(В), док је број ивица О(Е).
цсс листе
Просторна сложеност БФС може се изразити као О(В) , где је В број врхова.
Имплементација БФС алгоритма
Сада, да видимо имплементацију БФС алгоритма у Јави.
У овом коду користимо листу суседности да представимо наш граф. Имплементација алгоритма за прво претраживање у ширину у Јави чини много лакшим бављење листом суседности јер морамо само да прођемо кроз листу чворова који су прикачени за сваки чвор када се чвор избаци из реда (или почетка) реда.
У овом примеру, графикон који користимо да демонстрирамо код је дат на следећи начин -
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's all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>