Мени

Програм за претрагу ширине први (БФС) Ц ++ за прелазак преко графа или стабла

  • Главни
  • Остало
  • Програм за претрагу ширине први (БФС) Ц ++ за прелазак преко графа или стабла

breadth first search c program traverse graph

Испробајте Наш Инструмент За Елиминисање Проблема

Овај приручник покрива прву претрагу ширине на језику Ц ++ у којој се графикон или дрво прелази у ширину. Такође ћете научити БФС алгоритам и имплементацију:

Овај експлицитни Ц ++ водич ће вам дати детаљно објашњење техника преласка које се могу извести на дрвету или графикону.

Прелазак је техника помоћу које посећујемо сваки чвор графикона или стабла. Постоје две стандардне методе преласка.

  • Претрага по ширини (БФС)
  • Дубинско прво претраживање (ДФС)

=> Погледајте овде како бисте истражили целу листу водича за Ц ++.

функционално испитивање и нефункционално испитивање

Ширина претраге на језику Ц ++

Шта ћете научити:

Техника прве претраге ширине (БФС) на језику Ц ++

У овом упутству детаљно ћемо размотрити технику претраживања по ширини.

У техници преласка у ширину, графикон или дрво прелазе се у ширину. Ова техника користи структуру података о реду за чување врхова или чворова и такође за одређивање који врх / чвор треба да се заузме следећи.

Ширина алгоритма започиње са коренским чвором, а затим прелази све суседне чворове. Затим бира најближи чвор и истражује све остале непосећене чворове. Овај поступак се понавља све док се не истраже сви чворови на графикону.

Ширина-први алгоритам претраживања

Доље је дат алгоритам за БФС технику.

Сматрајте Г графом који ћемо прећи помоћу БФС алгоритма.

Нека је С коријен / почетни чвор графикона.

  • Корак 1: Почните са чвором С и ставите га у ред.
  • Корак 2: Поновите следеће кораке за све чворове на графикону.
  • Корак 3: Декуеуе С и обрадити.
  • Корак 4: Постави у ред све суседне чворове С и обради их.
  • (КРАЈ петље)
  • Корак 6: ЕКСИТ

Псеудоцоде

Псеудо-код за БФС технику дат је у наставку.

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

Прелази са илустрацијама

БФС илустрације 1. корак

Нека 0 буде почетни чвор или изворни чвор. Прво га стављамо у ред за обилазак и све суседне чворове у реду.

БФС илустрације 2. корак

Даље, узимамо један од суседних чворова за обраду, тј. 1. Означавамо га као посећен уклањањем из реда и стављамо суседне чворове у ред (2 и 3 су већ у реду). Како је 0 већ посећено, ми га игноришемо.

апликација која вам омогућава да шпијунирате други телефон

БФС илустрације 3. корак

Затим чвор 2 уклањамо из редова и означавамо га као посећени. Затим се суседни чвор 4 додаје у ред.

БФС илустрације 4. корак

Даље уклањамо ред 3 из реда и означавамо га као посећен. Чвор 3 има само један суседни чвор, тј. 0 који је већ посећен. Дакле, ми то игноришемо.

БФС илустрације 5. корак

У овој фази је само чвор 4 присутан у реду. Његов суседни чвор 2 је већ посећен, па га зато игноришемо. Сада означавамо 4 као посећене.

БФС илустрације 6. корак

Даље, секвенца присутна на посећеној листи је прво прелазак у ширину датог графикона.

Ако посматрамо дати граф и секвенцу преласка, можемо приметити да за БФС алгоритам заиста прелазимо граф у ширини и прелазимо на следећи ниво.

Имплементација БФС-а

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

Излаз:

који програм отвара јсон датотеку

Прелазак ширине и ширине за дати граф (са 0 као почетни чвор):

0 1 2 3 4

Имплементирали смо БФС у горе наведени програм. Имајте на уму да је графикон у облику листе суседности, а затим користимо итератор за итерацију кроз листу и извођење БФС-а.

Користили смо исти графикон који смо користили у илустративне сврхе као улаз у програм за упоређивање редоследа преласка.

Рунтиме Аналисис

Ако је В број врхова, а Е број ивица графикона, тада се временска сложеност за БФС може изразити као О (| В | + | Е |) . Кад ово кажемо, то такође зависи од структуре података коју користимо за представљање графикона.

Ако користимо листу суседности (као у нашој примени), тада је сложеност времена О (| В | + | Е |).

Ако користимо матрицу суседности, тада је временска сложеност О (В ^ 2) .

Поред коришћених структура података, постоји и фактор да ли је графикон густо насељен или ретко попуњен.

Када број врхова премаши број ивица, тада се каже да је граф слабо повезан јер ће бити много неповезаних врхова. У овом случају, временска сложеност графика биће О (В).

С друге стране, понекад графикон може имати већи број ивица од броја врхова. У таквом случају се каже да је граф густо насељен. Временска сложеност таквог графика је О (Е).

Да закључимо, шта значи израз О (| В | + | Е |) у зависности од тога да ли је граф густо или ретко насељен, доминирајући фактор тј. Ивице или врхови ће у складу с тим одредити временску сложеност графа.

Примене БФС преласка

  • Отпад: Техника сакупљања смећа, „Цхенеиев алгоритам“, користи прелазак у ширину за копирање одвоза смећа.
  • Емитовање у мрежама: Пакет путује од једног до другог чвора помоћу БФС технике у мрежи за емитовање да би стигао до свих чворова.
  • ГПС навигација: БФС можемо користити у ГПС навигацији да бисмо пронашли све суседне или суседне чворове локације.
  • Веб локације друштвених мрежа: С обзиром на особу „П“, можемо пронаћи све људе на даљини, „д“ од п помоћу БФС до нивоа д.
  • Пеер то Пеер мреже: Опет се БФС може користити у равноправним мрежама за проналажење свих суседних чворова.
  • Најкраћи пут и минимално распонско дрво на непреважаном графикону: БФС техника се користи за проналажење најкраће путање, тј. Путање са најмањим бројем ивица у не-пондерисаном графикону. Слично томе, такође можемо пронаћи дрво минималног распона помоћу БФС-а у не-пондерисаном графикону.

Закључак

Техника претраживања у ширину је метода која се користи за прелазак свих чворова графикона или стабла на ширину.

Ова техника се углавном користи за проналажење најкраће путање између чворова графикона или у апликацијама које захтевају да посетимо сваки суседни чвор као у мрежама.

=> Кликните овде за бесплатни курс Ц ++.

Препоручено читање

^