圖的深度優先搜尋演算法並生成DFS樹- IT閱讀

bfs (s）返回後，所有訪問過的頂點通過parent指標依次聯接，從整體上給出了頂點s 所屬連通或可達分量的一棵遍歷樹，稱作深度優先搜尋樹或DFS 樹（DFS tree ... 圖的深度優先搜尋演算法並生成DFS樹 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 圖的深度優先搜尋演算法並生成DFS樹 2019-02-10254 前面一篇文章介紹了圖的廣度優先搜尋演算法和BFS樹，這篇檔案筆者將介紹另一種圖的遍歷演算法-深度優先演算法 概述 深度優先搜尋（Depth-FirstSearch，DFS）選取下一頂點的策略，可概括為：優先選取最後一個被訪問到的頂點的鄰居。

以頂點s為基點的DFS搜尋，將首先訪問頂點s；再從s所有尚未訪問到的鄰居中任取其一，並以之為基點，遞迴地執行DFS搜尋。

故各頂點被訪問到的次序，類似於樹的先序遍歷而各頂點被訪問完畢的次序，則類似於樹的後序遍歷 圖的深度優先搜尋的程式碼實現 首先來看看再遍歷演算法中節點和弧使用到的屬性： 節點 privateintstatus=0;//狀態0undiscovered"未發現"1discovered"已發現"2visited"已完成" privateintparent=-1; privateintdTime=-1;//開始遍歷的時間 privateintfTime=-1;//結束遍歷的時間 弧 privateinttype; //弧型別：0CROSS跨邊1TREE（支撐樹） //2BACKWARD(該弧的起點和終點在支撐樹中存在終點到起點的路徑) //3FORWARD(該弧的起點和終點在支撐樹中存在其他路徑依然可以從起點到終點) 遍歷演算法 //從節點index開始遍歷 publicvoiddfsTree(intindex){ this.reload();//復位所有節點和弧狀態 //用來記錄某個節點被遍歷的時間 Integerclock=newInteger(0); ints=index; do{ if(allNodes[s].getStatus()==0){ dfs(s,clock); } }while(index!=(s=(++s%size)));//按序號檢查，防止遺漏index無法連通的節點 } publicvoiddfs(intindex,Integerclock){ //發現該節點 allNodes[index].setStatus(1); //記錄開始訪問的時間 allNodes[index].setdTime(++clock); //找出節點index的所有鄰居 for(inti=0;iparent->parent...==index case1: edge.setType(2); break; //如果該節點已經被訪問完畢。

則根據其遍歷結束時間來區分 case2: inttype=allNodes[index].getdTime()>allNodes[i].getdTime()?0:3; edge.setType(type); break; } } } //index節點訪問完畢 allNodes[index].setStatus(2); allNodes[index].setfTime(++clock); } 演算法的實質功能，由子演算法dfs（）遞迴地完成。

每一遞迴例項中，都先將當前節點v標記為“已發現”狀態，再逐一核對其各鄰居u的狀態並做相應處理。

待其所有鄰居均已處理完畢之後，將頂點v置為“訪問完畢”狀態，便可遞歸回溯。

若項點u尚處於“未發現”狀態，則將邊（v,u）歸類為樹邊，並將v置為u的parent。

此後，便可將u作為當前頂點，繼續遞迴地遍歷。

若項點u處於“已發現”狀態，則意味著在此處發現一個有向環路。

此時，在DFS遍歷樹中u必為v的祖先，故應將邊（v,u）歸類為後向邊BACKWARD。

這裡為每個頂點v都記錄了被發現的和訪問完成的時刻，對應的時間區間【dTime(v),fTime(v）】均稱作v的活躍期（activeduration）。

實際上，任意頂點v和u之間是否存在祖先/後代的“血緣”關係，完全取決於二者的活躍期是否相互包含。

對於有向圖，頂點u還可能處於“已發現”狀態。

此時，只要比對v與u的活躍期，即可判定在DFS樹中v是否為u的祖先。

若是，則邊（v,u）應歸類為前向邊FORWARD（forwardedge）；否則，二者必然來自相互獨立的兩個分支，邊（v,u）應歸類為跨邊（crossedge）。

如果v的dTime()小則為前向邊，否則為跨邊 bfs(s）返回後，所有訪問過的頂點通過parent指標依次聯接，從整體上給出了頂點s所屬連通或可達分量的一棵遍歷樹，稱作深度優先搜尋樹或DFS樹（DFStree）。

與BFS搜尋一樣，此時若還有其它的連通或可達分量，則可以其中任何頂點為基點，再次啟動DFS搜尋，來構成了DFS森林（DFSforest）。

例項 下圖針對含7個頂點和18條邊的某有向圖，給出了DFS搜尋的詳細過程。

注意觀察頂點時間標籤的設定，頂點狀態的演變，邊的分類和結果，以及DFS樹（森林）的生長過程： 粗邊框白色，為當前頂點；細邊框白色、雙邊框白色和黑色，分別為處於未發現、已發現和已完成狀態的頂點；dTime和fTime標籤，分別標註與各頂點的左右 最終結果如圖t所示，為包含兩棵DFS樹的一個DFS森林。

可以看出，選用不同的起始基點，生成的DFS樹（森林）也可能各異。

如本例中，若從D開始搜尋，則DFS森林可能如圖u所示。

複雜度 除了原圖本身，深度優先搜尋演算法所使用的空間，主要消耗於各頂點的時間標籤和狀態標記，以及各邊的分類標記，二者累計不超過0(n)+O(e)=O(n+e）。

當然，如採用以上程式碼的直接遞迴實現方式，作業系統為維護執行棧還需耗費一定量的空間一儘管這部分增量在漸進意義下還不足以動搖以上結論。

時間方面，不計對子函式dfs（）的呼叫，dfsTree（）本身對所有頂點的列舉共需0(n）時間。

不計dfs（）之間相互的遞迴呼叫，每個頂點、每條邊只在子函式dfs（）的某一遞迴例項中耗費O(1）時間，故累計亦不過0(n+e）時間。

綜合而言，深度優先搜尋演算法也可在O(n+e）時間內完成。

相關文章 圖的深度優先搜尋演算法並生成DFS樹 圖的廣度優先搜尋演算法並生成BFS樹 我的Java學習-資料結構裡圖的深度優先搜尋演算法 資料結構之實現無向圖的廣度優先搜尋演算法 資料結構——圖（3）——深度優先搜尋演算法（DFS）思想 圖的遍歷之深度優先搜尋演算法&&廣度優先優先演算法的實現 圖的遍歷演算法-深度優先搜尋演算法（dfs）和廣度優先搜尋演算法（bfs） 對於深度優先搜尋演算法的理解 PB中TreeView控制元件的深度優化搜尋演算法程式 利用深度優先搜尋演算法和廣度優先搜尋演算法解迷宮問題 搜尋_DFS(深度優先搜尋)_演算法分析 黑白迷宮問題——深度優先搜尋演算法 【DFS】不撞南牆不回頭—深度優先搜尋演算法[DeepFirstSearch] 算法系列—圖的深度優先搜尋（遞迴）/C++ 圖的深度優先搜尋及拓撲排序 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835