實作Graph與DFS、BFS圖形走訪演算法 - 寫點科普

DFS 就像試探著走迷宮，從起點開始、任意選一點與起點相鄰的點行走，行走過的點會被標記起來；再將下一個點視為起點、繼續選擇與該點相鄰的點行走… 寫點科普Kopuchat 專筆於科技史。

瞭解產業的運行規則，保有好奇、推理與觀察力的敏銳。

總覽 IC設計 資料中心 1G–4G 入門必知 實作Graph與DFS、BFS圖形走訪演算法 演算法筆記•程式教學 Writtenby:Lynn 2017-09-22 圖形的表示 圖形的表示有兩種方法：相鄰矩陣(AdjacencyMatrix)與相鄰串列(AdjacencyList)。

1.相鄰矩陣AdjacencyMatrix (1)無向圖 對一個頂點數為n的圖形，準備一個nxn矩陣A，其中： A[i,j]=1,if(i,j)邊存在 A[i,j]=0,if(i,j)邊不存在 觀察上圖可知： 由於D與自己形成迴圈，所以此對角線不全為0。

然而若此圖為SimpleGraph、頂點不能與自己形成迴圈，則對角線元素均為0。

此為無向圖，相鄰矩陣為對稱矩陣(SymmetricMatrix)。

由於邊(Vi,Vj)存在時、A[i,j]與A[j,i]的值均為1。

為了節省記憶體，可以只儲存相鄰矩陣的上半部或下半部，即上三角矩陣或下三角矩陣。

第一行加總與第一列加總會相等、為點A的分支度，第二行與第二列加總會相等、為點B的分支度…以此類推。

Q1:判斷邊(i,j)是否存在？ if A[i,j]=1then存在 else不存在 Time:O(1) Q2:求頂點i之degree？ 第i列或第i行元素加總即可 Time:O(n) Q3:求圖形邊數？ 邊數=(所有元素加總=所有點的Degree)÷2 Time:O(n2)   (2)有向圖 觀察上圖可知： 此圖為SimpleGraph、頂點不能與自己形成迴圈，則對角線元素均為0。

有向圖的相鄰矩陣未必為對稱矩陣(SymmetricMatrix)。

由於邊(Vi,Vj)存在時、不代表(Vi,Vj)會同時存在。

第一列加總為點A的分支度，第二列加總為點B的分支度…以此類推。

Q1:判斷邊(i,j)是否存在？ if A[i,j]=1then存在 else不存在 Time:O(1) Q2:求頂點i之Out-degree或In-degree？ 第i列元素加總=Out-degree 第i行元素加總=In-degree Time:O(n) Q3:求圖形邊數？ 所有頂點的Out-degree加總 Time:O(n2)   (3)相鄰矩陣的優缺 優點： 適合儲存邊數非常多的圖形。

適合經常要判斷邊是否存在的問題，複雜度僅O(1)。

缺點： 當圖形上的頂點數很多、邊數很少時，會形成稀疏矩陣(sparsematrix)，浪費記憶體空間。

求圖形上的邊數、判斷是否為連通圖、判斷有無Cycle形成，都需要O(n2)時間。

  2.相鄰串列AdjacencyLIst G=(V,E)，|V|=n、|E|=e。

若圖形包含n個頂點，則使用n個LinkedLis存放該圖形，每個LinkedList都代表一個頂點、和與其相鄰的頂點。

(1)無向圖 Q1:判斷邊(i,j)是否存在？ 檢查Vi的鏈結串列中是否有jNode存在。

Time:O(Vi串列長度) ≤O(所有Node數)=O(e) Q2:求頂點i之Degree？ 求Vi串列長度 Time:O(Vi串列長度) Q3:求圖形邊數？ ViLinkedListNodes意即Vi的串列長度、Vi串列的Node總數。

Time:O(n+e) 問：為何不是O(n*e)？ s=0; fori=1tondo//連同失敗、跑n+1次:O(n)Time { while(Vi串列尚未scan完畢)//Node總數，和邊數e成正比 { s++;//O(e) } } e=s/2;//1次 ->Time:O(n+e)   (2)有向圖 Q1:判斷邊(i,j)是否存在？ 檢查Vi的鏈結串列中是否有jNode存在。

Time:O(Vi串列長度) ≤O(所有Node數)=O(e) Q2:求頂點i之Out-degree與In-degree？ 求Vi串列長度=Out-degree 檢視所有串列，找出iNode的出現次數 =In-degree Time:O(n+e) Q3:求圖形邊數？ ViLinkedListNodes意即Vi的串列長度、Vi串列的Node總數。

Time:O(n+e) s=0; fori=1tondo//連同失敗、跑n+1次:O(n)Time { while(Vi串列尚未scan完畢)//Node總數，和邊數e成正比 { s++;//O(e) } } e=s;//1次 ->Time:O(n+e) (3)相鄰矩陣的優缺 優點： 適合儲存頂點數多、但邊數很少的圖形。

能較彈性地使用記憶體，但實作較為複雜。

求圖形上的邊數、判斷是否為連通圖、判斷有無Cycle形成，僅需O(n+e)時間。

（假設圖形的頂點個數n、邊數e。

用相鄰串列存放無向圖時，作為LinkedListhead的headnode有n個、Node數有2e個；存放有向圖時，headnode數有n個、Node數有e個，因此圖形的運算時間皆為O(n+e)） 缺點： 經常要判斷邊是否存在的問題，複雜度為O(e)。

求圖形上的邊數、判斷是否為連通圖、判斷有無Cycle形成，都需要 O(n2)時間。

  實作相鄰串列的程式碼 這邊我們利用C++STL的deque功能來建立可以前後增加刪除的陣列。

#include #include usingnamespacestd; classGraphNode{ public: intid; dequeadjacency; intdiscovered; GraphNode(int_id){ id=_id; discovered=0; } voiddump(){ printf("Vertex:%d,I'madjacentto:",id); inti; for(i=0;iNodeList; intmain(){ intnode_count,edge_count; printf("Enternoofvertices:"); scanf("%d",&node_count); printf("Enternoofedges:"); scanf("%d",&edge_count); inti,j; for(i=0;iadjacency.push_back(node_2); NodeList[node_2]->adjacency.push_back(node_1); } for(i=0;idump(); } return0; } 實作範例圖： 結果：   圖形走訪(GraphTraversal) 深度優先搜尋DFS(DepthFirstSearch) DFS就像試探著走迷宮，從起點開始、任意選一點與起點相鄰的點行走，行走過的點會被標記起來；再將下一個點視為起點、繼續選擇與該點相鄰的點行走…直到發現所有的點都已被標記過，即相鄰此點的所有點都已經走過了，則退回上一個分叉路口，繼續探訪。

直到所有的點都被標記過了，則搜索完畢。

虛擬碼(ds版) DFS(V:起點) visited[V]=TRUE; foreachvertexWadjacenttoVdo if(notvisited[W])then DFS(W); endif endfor 虛擬碼(Algo版) u.color=頂點u的顏色 White:尚未拜訪過(undiscovered) Gray:若u為discovered，但u的相鄰點v為undiscovered Black:結束u與其所有相鄰點的拜訪 u.d=起點s到u點的距離(=邊數=路徑長) u.π=u的父點(意即從哪個點連到u) DFS(G){ foreachvertexuinG//設初始值,Time:O(V) { u.color=White;//所有點設為白色 u.π=Nil;//所有點的父點皆未知 } time=0; foreachvertexuinG//Time:O(V) { if(u.color==White)then { DFS-Visit(G,u); } } } DFS-Visit(G,u){ time=time+1; u.d=time;//u首度被discovered之time u.color=Gray;//被拜訪，尚未結束 foreachvertexvinG.adj[u] { if(v.color==White)then { v.π=u; DFS-Visit(G,V); } } u.color=Black;//u已結束 time=time+1; u.f=time;//u的finishedtime } =>Time=O(V+E) 程式碼 #include #include usingnamespacestd; classGraphNode{ public: intid; dequeadjacency; intdiscovered; GraphNode(int_id){ id=_id; discovered=0; } voiddump(){ printf("Vertex:%d,I'madjacentto:",id); inti; for(i=0;iNodeList; voidDFS(intvertex){ GraphNode*curr=NodeList[vertex]; curr->discovered=1; printf("%d",vertex); inti,next; for(i=0;iadjacency.size();i++){ next=curr->adjacency[i]; if(NodeList[next]->discovered==0){ DFS(next); } } } intmain(){ intnode_count,edge_count; printf("Enternoofvertices:"); scanf("%d",&node_count); printf("Enternoofedges:"); scanf("%d",&edge_count); inti,j; for(i=0;iadjacency.push_back(node_2); NodeList[node_2]->adjacency.push_back(node_1); } for(i=0;idump(); } printf("DFSTraversal:"); DFS(0); printf("\n"); return0; } 實作範例圖： 結果：   廣度優先走訪BFS(BreadthFirstSearch) BFS以某個頂點作為起始點，一開始拜訪該頂點、再接著拜訪該頂點的所有相鄰頂點，接下來再拜訪下一層的頂點，直到所有的頂點皆拜訪過為止。

虛擬碼(DS版) BFS(V:起點) //Assumevisited[1..n] visited[V]=TRUE; Create(Q); Enqueue(Q,V); while(notIsempty(Q))do u=Dequeue(Q); foreachvertexwadjacenttoudo{ foreachvertexWadjacenttoVdo if(notvisited[W])then DFS(W); 虛擬碼(ALGO版) u.color=表示頂點u的顏色 White:尚未拜訪(undiscover) Gray:若u為discovered，但u的相鄰點 v為undiscovered Black:結束u與其所有相鄰點的拜訪 u.d=起點s到u點的距離(=邊數=路徑長) u.π=u的父點(意即從哪個點連到u) 除了頂點的資料結構之外，還需要一個queue來管理灰色的頂點，代號Q。

BFS(G,s){//s為起點 foreachvertexuinG-{s}//初始值設定,Time:O(V) { u.color=white;//將起點以外的所有點設為白色 u.d=∞; u.π=Nil;//父點皆未知 } //拜訪起點 s.color=Gray; s.d=0; s.π=Nil; //建立空佇列Q CreateQ(Q); //將起點s加入Q Enqueue(Q,s); //Q不為空時 while(notIsEmpty(Q))do { u=Dequeue(Q);//O(1)*V次,Time:O(V) foreachvinG.adj[u]do//Time:O(E) { if(v.color==White)then { v.color=Gray; v.d=u.d+1; v.π=u; Enqueue(Q,v); } } u.color=Black; } } =>O(V)+O(V)+O(E)=O(V+E) 程式碼 #include #include usingnamespacestd; classGraphNode{ public: intid; dequeadjacency; intdiscovered; GraphNode(int_id){ id=_id; discovered=0; } voiddump(){ printf("Vertex:%d,I'madjacentto:",id); inti; for(i=0;iNodeList; voidBFS(intstart){ dequeque; que.push_back(start); NodeList[start]->discovered=1; intcurr_id,adj_id; GraphNode*curr_node; GraphNode*adj_node; while(que.size()!=0){ curr_id=que[0]; que.pop_front(); printf("%d",curr_id); curr_node=NodeList[curr_id]; for(inti=0;iadjacency.size();i++){ adj_id=curr_node->adjacency[i]; adj_node=NodeList[adj_id]; if(adj_node->discovered==0){ adj_node->discovered=1; que.push_back(adj_id); } } } } intmain(){ intnode_count,edge_count; printf("Enternoofvertices:"); scanf("%d",&node_count); printf("Enternoofedges:"); scanf("%d",&edge_count); inti,j; for(i=0;iadjacency.push_back(node_2); NodeList[node_2]->adjacency.push_back(node_1); } for(i=0;idump(); } printf("BFSTraversal:"); BFS(0); printf("\n"); return0; } 實作範例圖： 結果： 分享此文：TwitterFacebook 相關 GraphBFSDFS深度優先廣度優先Lastmodified:2021-07-13 PreviousStory:插入排序(InsertionSort) NextStory:C++入門教學：輸入/輸出與運算 AbouttheAuthor/Lynn 90年後女孩紙一個，獨立營運寫點科普網站：讓一般人有機會瞭解生活中常見產業或技術的基礎概念，就像科普一樣，期許能藉由網誌傳遞好奇、探究、思考的價值。

4Repliesto“實作Graph與DFS、BFS圖形走訪演算法” Carl表示: 2018-05-0911:58:27 您好，請問 相鄰串列AdjacencyLIst中無向圖”Q3:求圖形邊數？”中， 為什麼您演算法的bigO是O(n+e)而不是O(n*e)呢？ forloop裡面包一個whileloop，相乘不應該為O(n*e)嗎？ 謝謝 回覆 capy表示: 2019-08-2916:03:12 e應該是指總邊的個數，雖然for裡面會去loop每一個相鄰的邊，但總數上限就是整張圖邊的個數。

所以是O(n+e)。

回覆 ajaj表示: 2020-05-2511:00:11 forloop裡面雖然包了一個whileloop，但整個的計算是2*e，所以裡面視為O(e)而外面的forloop為O(n) 回覆 Leetcode北美經典主題面試前刷完推薦題，信心大增–錢科實驗室表示: 2020-07-2915:41:01 […]參考資料1.BFS,DFS:概念,程式碼[…] 回覆 發佈留言取消回覆發佈留言必須填寫的電子郵件地址不會公開。

必填欄位標示為*留言顯示名稱* 電子郵件地址* 個人網站網址 在瀏覽器中儲存顯示名稱、電子郵件地址及個人網站網址，以供下次發佈留言時使用。

用電子郵件通知我後續的迴響。

新文章使用電子郵件通知我。

Δ 如何找到寫點科普 《寫點科普》是一個專筆於產業史、專有名詞科普與趨勢評析的部落格。

瞭解產業的運行規則，保有好奇、推理與觀察力的敏銳。

我是本站唯一作者Lynn，你可以透過以下方式聯繫我： Facebook:寫點科普 Email:[email protected] Instagram：kopuchat Clubhouse:@kopuchat 贊助這個寫作計畫 本站創立初衷為透過知識傳播，增加台灣產業認知豐富度。

故創立以來堅持不放廣告破壞閱讀體驗，本人也不轉移到商業平台付費鎖文章。

未來保證也不會。

也希望有您的支持，能讓Lynn用來支付架站營運費用與研究成本，以持續為讀者提供深度分析文章與舒適的閱讀環境。

網誌統計 累計瀏覽人次[wpstatisticsstat=visitorstime=total] 累計贊助人次829 累計訂閱人次2501 標籤雲5G ARM C/C++ DRAM FACEBOOK Google Hinton IBM Intel iPhone IPO Lynn寫點週報 NeuralNetwork SEMI SEO UI設計 三星 中美貿易戰 人工智慧 創投 半導體 台灣 台積電 喬姆斯基 基金 排序法 晶圓代工 格羅方德 機器學習 深度學習 物聯網 特斯拉 產業 異質整合 美光 華為 蘋果 處理器 記憶體 設計 遊戲 邏輯電路 雲端運算 風險 高通 站內文章搜尋 最新留言「Will」在〈快速排序(QuickSort)〉發佈留言「保特瓶」在〈經濟衰退危機？用村莊案例看懂「美債殖利率倒掛」現象〉發佈留言「Albert」在〈看ARM如何搶走英特爾的x86市場––CPU市場上的逆襲！〉發佈留言「John」在〈雲端到終端AI運算將無處不在，從COMPUTEX2021Virtual洞察人工智慧與AIoT應用趨勢〉發佈留言「當精準定位成為可能，人們還有隱私嗎？淺談5G通訊如何達到「高精準度定位」-寫點科普Kopuchat」在〈從基地台到5G手機–淺談全球5G通訊市場發展現況〉發佈留言「Mei」在〈看ARM如何搶走英特爾的x86市場––CPU市場上的逆襲！〉發佈留言「JoeChiu」在〈晶圓代工爭霸戰：半導體知識（前傳）〉發佈留言全部文章 IC原理(6) 0與1的世界(4) SoC晶片(2) 人工智慧(6) AI簡史(1) 機器學習(5) 半導體(31) IC設計(9) 專家分享(14) 晶圓代工(8) 數位行銷(17) UI設計(6) 入門必知(11) 程式教學(23) C/C++(7) Git(2) Python(3) 演算法筆記(11) 精品時尚(3) 奢侈品(2) 快時尚(1) 美股SaaS(13) Google(2) 熱門IPO(5) 特斯拉(6) 行動APP(18) 數位生態(12) 熱門應用(6) 記憶體(6) 市場動向(2) 記憶體原理(4) 通訊(12) 1G–4G(4) 5G(8) 遊戲(8) 全球遊戲(1) 台灣遊戲(4) 遊戲史(3) 金融(19) 投資學(5) 投資銀行(8) 總體經濟(6) 關於(5) 雜談(14) 雲端運算(6) 資料中心(5) 邊緣運算(1) 電腦起源(7) 形式語言(4) 科技史(3) Facebook Instagram 站內文章分類站內文章分類 選取分類 IC原理  (6)    0與1的世界  (4)    SoC晶片  (2) 人工智慧  (6)    AI簡史  (1)    機器學習  (5) 半導體  (31)    IC設計  (9)    專家分享  (14)    晶圓代工  (8) 數位行銷  (17)    UI設計  (6)    入門必知  (11) 程式教學  (23)    C/C++  (7)    Git  (2)    Python  (3)    演算法筆記  (11) 精品時尚  (3)    奢侈品  (2)    快時尚  (1) 美股SaaS  (13)    Google  (2)    熱門IPO  (5)    特斯拉  (6) 行動APP  (18)    數位生態  (12)    熱門應用  (6) 記憶體  (6)    市場動向  (2)    記憶體原理  (4) 通訊  (12)    1G–4G  (4)    5G  (8) 遊戲  (8)    全球遊戲  (1)    台灣遊戲  (4)    遊戲史  (3) 金融  (19)    投資學  (5)    投資銀行  (8)    總體經濟  (6) 關於  (5) 雜談  (14) 雲端運算  (6)    資料中心  (5)    邊緣運算  (1) 電腦起源  (7)    形式語言  (4)    科技史  (3) 最新文章 【SEMICON】ESG投資已成趨勢，看台灣半導體產業如何攜手打造綠色永續供應鏈 【SEMICON】供應鏈如何數位轉型？從高科技智慧製造論壇看企業導入案例 【SEMICON】電動車、5G通訊跟高速運算為什麼都需要它？解析化合物半導體SiC與GaN的應用潛力 雲端到終端AI運算將無處不在，從COMPUTEX2021Virtual洞察人工智慧與AIoT應用趨勢 最新留言「Will」在〈快速排序(QuickSort)〉發佈留言「保特瓶」在〈經濟衰退危機？用村莊案例看懂「美債殖利率倒掛」現象〉發佈留言「Albert」在〈看ARM如何搶走英特爾的x86市場––CPU市場上的逆襲！〉發佈留言 寫點科普，請給指教 專筆於科技史。

瞭解產業的運行規則，保有好奇、推理與觀察力的敏銳。

文章合作或轉載需求 90年後喜愛科技的女孩紙一個，獨立運營寫點科普網站。

目前是北漂在中國北京的台灣人。

有任何合作洽談需求，歡迎私訊粉專或寫信到這支Email來吧: [email protected] Facebook Instagram Twitter YouTube PoweredbyWordPressandLookout.