
何謂圖形(Graph)
是由頂點和邊所組成。
圖形定義
- 無向圖形(Undirected Graph):邊是無方向性的
- 有向圖形(Directed Graph):邊是有方向性的
圖形的表示法
- 相鄰矩陣(Adjacency Matrix)
- 相鄰串列(Adjacency Lists)
圖形的走訪方式
- 深度優先搜尋法(De[th-First Search; DFS)
以深度(路徑長度)優先,可以用遞迴和堆疊控制要走訪的頂點
- 廣度優先搜尋法(Bradth-First Search;BFS)
以廣度(分支度)優先,可以用佇列來控制要走訪的頂點
圖形的走訪應用
- 找出一個無向圖形的擴張樹
- 判斷無向圖形是否為一個相連圖形
- 找出一個無相圖的相連子圖