breadth first search c program traverse graph
Този урок обхваща първо търсене на широчина в C ++, в което графиката или дървото се обхождат по ширина. Също така ще научите алгоритъма и изпълнението на BFS:
Този изричен урок за C ++ ще ви даде подробно обяснение на техниките за обхождане, които могат да бъдат изпълнени на дърво или графика.
Обхождането е техниката, при която посещаваме всеки възел на графиката или дърво. Има два стандартни метода на обхождане.
- Първо търсене на широчина (BFS)
- Търсене с дълбочина първо (DFS)
=> Вижте тук, за да разгледате пълния списък с уроци за C ++.
най-добрите места за гледане на безплатни аниме
Какво ще научите:
Техника за първо търсене на широчина (BFS) в C ++
В този урок ще обсъдим подробно техниката за първоначално търсене.
При техниката за обхождане първо на ширина, графиката или дървото се обхождат по ширина. Тази техника използва структурата на данните за опашката, за да съхранява върховете или възлите, а също и за да определи кой връх / възел трябва да се поеме след това.
Широкият алгоритъм започва с коренния възел и след това обхожда всички съседни възли. След това избира най-близкия възел и изследва всички останали непосетени възли. Този процес се повтаря, докато се проучат всички възли в графиката.
Алгоритъм за първо търсене на широчина
По-долу е даден алгоритъмът за BFS техника.
Разгледайте G като графика, която ще преминем, използвайки алгоритъма BFS.
Нека S е коренът / началният възел на графиката.
- Етап 1: Започнете с възел S и го поставете в опашката.
- Стъпка 2: Повторете следните стъпки за всички възли в графиката.
- Стъпка 3: Отменете S и го обработете.
- Стъпка 4: Задайте в опашка всички съседни възли на S и ги обработете.
- [КРАЙ НА ЛИП]
- Стъпка 6: ИЗХОД
Псевдокод
Псевдокодът за BFS техниката е даден по-долу.
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
Обхождания с илюстрации
Нека 0 е начален възел или възел източник. Първо го поставяме в опашката в посетената опашка и всички съседни възли в опашката.
След това вземаме един от съседните възли за обработка, т.е. 1. Маркираме го като посетен, като го премахваме от опашката и поставяме съседните му възли в опашката (2 и 3 вече са на опашка). Тъй като 0 вече е посетен, ние го игнорираме.
потребителски интерфейс на база данни и софтуер за заявки
След това деактивираме възел 2 и го маркираме като посетен. След това съседният му възел 4 се добавя към опашката.
След това премахваме 3 от опашката и я маркираме като посетена. Възел 3 има само един съседен възел, т.е. 0, който вече е посетен. Следователно ние го игнорираме.
На този етап в опашката присъства само възел 4. Съседният му възел 2 вече е посетен, поради което го игнорираме. Сега отбелязваме 4 като посетени.
На следващо място, последователността, присъстваща в посетения списък, е обхождането първо на широчината на дадената графика.
Ако наблюдаваме дадената графика и последователността на обхода, можем да забележим, че за алгоритъма BFS ние наистина прекосяваме графиката в ширина и след това преминаваме към следващото ниво.
Прилагане на 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): '< Изход:
най-добрият уебсайт за гледане на безплатни аниме
Обхват - първо обхват за дадената графика (с 0 като начален възел):
0 1 2 3 4
Внедрихме BFS в горната програма. Имайте предвид, че графиката е под формата на списък за съседство и след това използваме итератор, за да прегледаме списъка и да изпълним BFS.
Използвахме същата графика, която използвахме за целите на илюстрацията като вход към програмата за сравняване на последователността на обхождане.
Анализ по време на изпълнение
Ако V е броят на върховете и E е броят на ръбовете на графика, тогава сложността на времето за BFS може да бъде изразена като O (|V|+|E|) . Като казахме това, това също зависи от структурата на данните, която използваме за представяне на графиката.
Ако използваме списъка за съседство (както при нашето изпълнение), тогава сложността на времето е O (|V|+|E|).
Ако използваме матрицата на съседство, тогава сложността на времето е O (V ^ 2) .
Освен използваните структури от данни, има и фактор дали графиката е гъсто населена или слабо населена.
Когато броят на върховете надвишава броя на ръбовете, тогава се казва, че графиката е слабо свързана, тъй като ще има много несвързани върхове. В този случай времевата сложност на графиката ще бъде O (V).
От друга страна, понякога графиката може да има по-голям брой ръбове от броя на върховете. В такъв случай се казва, че графиката е гъсто населена. Сложността във времето на такава графика е O (E).
В заключение, значението на израза O (| V | + | E |) зависи от това дали графиката е гъсто или рядко населена, доминиращият фактор, т.е.
Приложения на BFS Traversal
- Събиране на боклук: Техниката за събиране на боклука, „Алгоритъм на Чейни“, използва първоначално обхождане за копиране на събирането на боклука.
- Излъчване в мрежи: Пакетът пътува от един възел до друг, използвайки BFS техниката в излъчващата мрежа, за да достигне до всички възли.
- GPS навигация: Можем да използваме BFS в GPS навигация, за да намерим всички съседни или съседни възли за местоположение.
- Уебсайтове за социални мрежи: Като се има предвид човек „P“, можем да намерим всички хора на разстояние, „d“ от p, използвайки BFS до d нивата.
- Партньорски мрежи: Отново BFS може да се използва в равнопоставени мрежи за намиране на всички съседни възли.
- Най-кратък път и минимално обхващащо се дърво в нетеглената графика: Техниката BFS се използва за намиране на най-краткия път, т.е.път с най-малък брой ръбове в нетеглената графика. По същия начин можем да намерим и минимално обхващащо дърво, използвайки BFS в непретеглената графика.
Заключение
Техниката за търсене първо по ширина е метод, който се използва за обхождане на всички възли на графика или дърво по широк начин.
Тази техника се използва най-вече за намиране на най-краткия път между възлите на графика или в приложения, които изискват да посетим всеки съседен възел като в мрежите.
=> Щракнете тук за безплатния курс C ++.
Препоръчително четене
- Двоично дърво за търсене C ++: Внедряване на BST и операции с примери
- Структура на данните от B Tree и B + Tree в C ++
- Внедряване на графики в C ++ с използване на списък за съседство
- Структура на данните на двоичното дърво в C ++
- 12 най-добри инструменти за създаване на линейни графики за създаване на зашеметяващи линейни графики [2021 РЕЙТИНГИ]
- Структура на данните за дърво и купчина AVL в C ++
- Дървета в C ++: Основна терминология, техники за преминаване и типове дървета на C ++
- Графика за причините и последиците - Техника за писане на динамични тестове за максимално покритие с по-малко тестови случаи