B6.png

 

圖形(Graph):是由頂點和邊所組成。

[定義]

1.無向圖形(Undirected Graph):邊是無方向性的

2.有向圖形(Directed Graph):邊是有方向性的

 

※圖形的表示法

   ◎相鄰矩陣(Adjacency Matrix)

   ◎相鄰串列(Adjacency Lists)

 

※圖形的走訪方式

   ◎深度優先搜尋法(De[th-First Search; DFS)

    以深度(路徑長度)優先,可以用遞迴和堆疊控制要走訪的頂點

   ◎廣度優先搜尋法(Bradth-First Search;BFS)

    以廣度(分支度)優先,可以用佇列來控制要走訪的頂點

 

※圖形的走訪應用

   ◎找出一個無向圖形的擴張樹

   ◎判斷無向圖形是否為一個相連圖形

   ◎找出一個無相圖的相連子圖

    歐歐 Lin 發表在 痞客邦 留言(0) 人氣()