图形表示法.ppt

重點一 圖形 圖形表示法 相鄰矩陣 adjacency matrix 相鄰串列 adjacency list 相鄰多元串列 adjacency multilists 相鄰矩陣 n個頂點 以n*n陣列 adj_mat表示圖形 adj_mat[i,j]=1表示 頂點i、j間有邊使之相連 對一無向圖，其相鄰矩陣是對稱的 可以只袸上三角或下三角矩陣，以省空間 相鄰串列 每一個串列的第一個節點(head nodes)表示頂點 n個點 = 有n個串列 且每一串列均加以循序編號，這樣可使我們快速地存取任一頂點的相鄰串列 串列中的節點表示與該頂點相鄰的頂點 對一個圖而言 n頂點與e邊 = 有n個heah nodes與2e個節點 基本的圖形運算 走訪所有節點 決定連通元件 生成樹 圖形的走訪 樹的走訪 前序、中序、後序 圖形的走訪 先深搜尋 Depth First Search (DFS) 以相連串列表示圖形時，DFS之複雜度: O(e) 以相連矩陣表示圖形時，DFS之複雜度: O(n2) 先廣搜尋 Breadth First Search (BFS) 以相連串列表示圖形時，BFS之複雜度: O(e) 以相連矩陣表示圖形時，BFS之複雜度: O(n2) DFS 以相鄰串列表示圖形時，DFS之複雜度: O(e)使用陣列visited[MAX_VERTICES]表示已走訪過的頂點 void dfs(int v) { node_pointer w; visited[v]= TRUE; printf(“%5d”, v); for (w=graph[v]; w==null; w=w-link) if (!visited[w-vertex]) dfs(w-vertex); } BFS 以相鄰串列表示圖形時，BFS之複雜度: O(e)使用陣列visited[MAX_VERTICES]表示已走訪過的頂點 void bfs(int v) { node_pointer w; queue_pointer front, rear; front = rear = NULL; printf(“%5d”, v); visited[v] = TRUE; addq(front, rear, v); while (front) { v= deleteq(front); for (w=graph[v]; w; w=w-link) if (!visited[w-vertex]) { printf(“%5d”, w-vertex); addq(front, rear, w-vertex); visited[w-vertex] = TRUE;} } } 問題 DFS演算法使用哪些資料結構完成DFS搜尋？ 圖形以哪一種資料結構儲存？ 相鄰矩陣或相鄰串列 DFS使用哪一種資料結構完成搜尋？ 堆疊 Why??? BFS演算法使用哪些資料結構完成BFS搜尋？ 圖形以哪一種資料結構儲存？ 相鄰矩陣或相鄰串列 BFS使用哪一種資料結構完成搜尋？ 佇列 Why??? 生成樹 spanning tree 生成樹 圖形G=(V,E)之生成樹 樹狀結構 包含G所有頂點 以及G的部分邊 DFS, BFS均可找出圖形之生成樹，稱為﹕ Depth first spanning tree Breadth first spanning tree 生成樹的特性 圖形G=(V, E)，其生成樹為G’=(V’,E’)，則﹕ 在G’中加入任何一邊v，v?G, v?G’ 會造成迴圈 生成樹是G的最小子圖，使得V’=V，且G’是連通的 G’有n個頂點，且G’有n-1邊 最小成本生成樹 Minimum cost spanning tree 最小成本生成樹 有加權的無向圖 最小成本生成樹具有下列特性 樹狀結構 不會有環路存在 有n-1邊（因為有n個頂點） 具有最小成本 使用三種不同演算法可找出最小成本生成樹 Kruskal’s algorithm Prim’s algorithm Sollin’s algorithm Kruskal’s algorithm 一次加一邊，必須符合下列條件﹕ 該邊的成本是尚未加入的邊中最小的 且不會造成cycle Kruskal’s Algorithm Kruskal’s Algorithm T= {}; while (T contains less than n-1 edges E is not empty) { choose