Меню

Дълбоко първо търсене (DFS) C ++ програма за пресичане на графика или дърво

  • Основен
  • Други
  • Дълбоко първо търсене (DFS) C ++ програма за пресичане на графика или дърво

depth first search c program traverse graph

Опитайте Нашия Инструмент За Премахване На Проблемите

Този урок покрива първоначално търсене на дълбочина (DFS) в C ++, в който се пресича графика или дърво в дълбочина. Също така ще научите алгоритъма и внедряването на DFS:

Търсенето с дълбочина първо (DFS) е още една техника, използвана за пресичане на дърво или графика.

DFS започва с корен възел или начален възел и след това изследва съседните възли на текущия възел, като навлиза по-дълбоко в графиката или дървото. Това означава, че в DFS възлите се изследват задълбочено, докато не се срещне възел без деца.

След като се достигне листният възел, DFS се връща назад и започва да изследва още някои възли по подобен начин.

=> Внимавайте тук за ръководството за обучение за начинаещи C ++.

Дълбочина първо търсене

Какво ще научите:

Дълбочина първо търсене (DFS) в C ++

За разлика от BFS, в който ние изследваме възлите по ширина, в DFS ние изследваме възлите по дълбочина. В DFS използваме структура от данни за стека за съхраняване на изследваните възли. Ръбовете, които ни водят до неизследвани възли, се наричат ​​„ръбове за откриване“, докато ръбовете, водещи до вече посетени възли, се наричат ​​„блокови ръбове“.

След това ще видим алгоритъма и псевдокода за техниката DFS.

DFS алгоритъм

  • Етап 1: Поставете основния възел или началния възел на дърво или графика в стека.
  • Стъпка 2: Изкарайте горния елемент от стека и го добавете към посетения списък.
  • Стъпка 3: Намерете всички съседни възли на възела, маркиран като посетен, и добавете тези, които все още не са посетени, към стека.
  • Стъпка 4 : Повторете стъпки 2 и 3, докато стекът се изпразни.

Псевдокод

Псевдокодът за DFS е даден по-долу.

Псевдокодът за DFS

От горния псевдокод забелязваме, че алгоритъмът DFS се извиква рекурсивно за всеки връх, за да се гарантира, че всички върхове са посетени.

Обхождания с илюстрации

Нека сега илюстрираме обхождането на DFS на графика. За по-голяма яснота ще използваме същата графика, която използвахме в илюстрацията на BFS.

DFS илюстрации с траверсали

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

Натиснете всички съседни възли в стека

След това вземаме един от съседните възли за обработка, т.е. горната част на стека, която е 1. Маркираме го като посетен, като го добавяме към посетения списък. Сега потърсете съседните възли на 1. Тъй като 0 вече е в посетения списък, ние го игнорираме и посещаваме 2, който е горната част на стека.

DFS илюстрация - Стъпка 3

След това маркираме възел 2 като посетен. Съседният му възел 4 се добавя към стека.

DFS илюстрация Стъпка 4

След това маркираме 4, който е горната част на стека, както е посетен. Възел 4 има само възел 2 като негов съседен, който вече е посетен, поради което го игнорираме.

DFS илюстрация Стъпка 5

На този етап в стека присъства само възел 3. Съседният му възел 0 вече е посетен, поради което го игнорираме. Сега отбелязваме 3 като посетени.

DFS илюстрация Стъпка 6

Сега стекът е празен и посетеният списък показва последователността на първоначалното обхождане на дълбочината на дадената графика.

Ако наблюдаваме дадената графика и последователността на обхождането, забелязваме, че за алгоритъма DFS наистина прекосяваме графика в дълбочина и след това я връщаме отново, за да изследваме нови възли.

Внедряване на дълбочина-първо търсене

Нека да приложим техниката на обхождане DFS, използвайки C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Изход:

Обхождане с дълбочина първо за дадената графика:

0 1 2 4 3

За пореден път използвахме графиката в програмата, която използвахме за целите на илюстрацията. Виждаме, че алгоритъмът DFS (разделен на две функции) се извиква рекурсивно на всеки връх в графиката, за да се гарантира, че всички върхове са посетени.

Анализ по време на изпълнение

Сложността във времето на DFS е същата като BFS, т.е. O (|V|+|E|) където V е броят на върховете, а E е броят на ребрата в дадена графика.

Подобно на BFS, в зависимост от това дали графиката е малко населена или гъсто населена, доминиращият фактор ще бъдат съответно върхове или ребра при изчисляването на сложността на времето.

Итеративни DFS

Показаното по-горе изпълнение за техниката DFS има рекурсивен характер и използва стек от извиквания на функции. Имаме друг вариант за внедряване на DFS, т.е. ' Итеративно търсене с дълбочина първо ”. В това използваме изричния стек, за да задържим посетените върхове.

Показахме изпълнението на итеративен DFS по-долу. Имайте предвид, че изпълнението е същото като BFS, с изключение на фактора, че използваме структурата на стека данни вместо опашка.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Изход:

Резултат от итеративно обхождане на дълбочина:

0 3 2 4 1

Използваме същата графика, която използвахме в нашата рекурсивна реализация. Разликата в изхода е, защото използваме стека в итеративното изпълнение. Тъй като стековете следват реда LIFO, получаваме различна последователност от DFS. За да получим същата последователност, може да поискаме да вмъкнем върховете в обратен ред.

BFS срещу DFS

Досега сме обсъждали и двете техники на обхождане за графики, т.е. BFS и DFS.

Сега нека разгледаме разликите между двете.

BFSDFS
Стендове за „Широчина първо търсене“Стои за „търсене с дълбочина първо“
Възлите се изследват в ширина, ниво на ниво.Възлите се изследват в дълбочина, докато има само листни възли и след това се проследяват, за да се изследват други непосетени възли.
BFS се извършва с помощта на структура на данните за опашката.DFS се извършва с помощта на структурата на стека данни.
По-бавно изпълнение.По-бързо от BFS.
Полезно при намирането на най-краткия път между два възела.Използва се най-вече за откриване на цикли в графики.

Приложения на DFS

  • Откриване на цикли в графиката: Ако намерим заден ръб, докато изпълняваме DFS в графика, можем да заключим, че графиката има цикъл. Следователно DFS се използва за откриване на циклите в графика.
  • Намиране на път: Като се имат предвид два върха x и y, можем да намерим пътя между x и y, използвайки DFS. Започваме с връх x и след това натискаме всички върхове по пътя към стека, докато срещнем y. Съдържанието на стека дава пътя между x и y.
  • Минимално обхващащо се дърво и най-кратък път: DFS обхождането на непретеглената графика ни дава минимално обхващащо дърво и най-кратък път между възлите.
  • Топологично сортиране: Използваме топологично сортиране, когато трябва да планираме заданията от дадените зависимости между заданията. В областта на компютърните науки го използваме най-вече за разрешаване на зависимостите на символи в линкери, сериализация на данни, планиране на инструкции и др. DFS се използва широко при топологично сортиране.

Заключение

В последните няколко урока разгледахме повече за двете техники на обхождане за графики, т.е. BFS и DFS. Видяхме разликите, както и приложенията на двете техники. BFS и DFS основно постигат един и същ резултат от посещението на всички възли на графика, но те се различават в реда на изхода и начина, по който се извършва.

Виждали сме и прилагането на двете техники. Докато BFS използва опашка, DFS използва стекове, за да внедри техниката. С това завършваме урока за техники за обхождане на графики. Също така можем да използваме BFS и DFS върху дървета.

най - добрият безплатен компютър за почистване на Windows 7

Ще научим повече за обхващането на дървета и няколко алгоритма за намиране на най-краткия път между възлите на графика в нашия предстоящ урок.

=> Вижте тук, за да разгледате пълния списък с уроци за C ++.

Препоръчително четене

^