二元树表示法--阵列表示法.PPT

* 堆積排序法結論 堆積排序法為不穩定排序法 平均時間複雜度為O(n log n)及最差時間複雜度為O(n log n) 若使用堆積排序法排序n筆資料，共需n次處理(pass)，而每次處理所須的處理時間約為log2n，因此共需O(n log n)的時間。所以堆積排序法的平均時間複雜度與最差時間複雜度皆為O(n log n) * 各種排序法的比較 * 圖形 圖形(graph)是由「端點」 (vertex)及「端點對所構成的邊」(edge)二個非空集合所構成，一般利用以下的符號來代表對應之元件： V代表端點 E代表邊 G(V,E) 代表圖形 圖形中端點集合表示為V(G)，邊集合表示為E(G) * 無向圖與有向圖 圖形依邊的型態可分成下列兩類 無向圖(Undirected Graph)：E中的邊無方向性，(x, y) = (y, x)，其中x及y為端點 有向圖(Directed Graph; Digraph)：E中的邊有方向性，x, y ? y, x，其中x及y為端點。在x, y中，x是head，y是tail * 無向圖範例 V(G) = {1, 2, 3, 4, 5}。 E(G) = {(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5) } * 有向圖範例 V(G) = {1, 2, 3, 4, 5}。 E(G) = {1, 2, 1, 4, 2, 3, 2, 4, 3, 4, 4, 5, 5, 3 } * 無向圖重要名詞 (1/10) 子圖(subgraph) 若G為G的子圖，若且唯若(if and only if)： V(G) V(G) 且 E(G) E(G) 上圖中G1、G2及G3均為G的子圖 * 無向圖重要名詞 (2/10) 相鄰(adjacent) 圖形中一邊的二端點稱為相鄰。若邊(x, y)是E(G)中的一邊，則端點x與y是相鄰的 連接(incident) 若邊(x, y)是E(G)中的一邊，則邊(x, y)連接端點x與端點y * 無向圖重要名詞 (3/10) 路徑(path) 在圖形中，路徑是指一組由一連串端點所形成的連續序列 1，2，4，5，3便是一組路徑 * 無向圖重要名詞 (4/10) 路徑長度(path length) 路徑中包含的邊總數 上圖1，2，4，5，3路徑長度為4 簡單路徑(simple path) 除起點和終點外，其餘節點均不可重覆的路徑 相連(connected) 兩個端點為相連，若且唯若，在這對端點間存在一條路徑 * 無向圖重要名詞 (5/10) 相連圖(connected graph) 若一個圖形相連圖，若且唯若，圖形中之任二端點均有路徑相連。如二元樹(binary tree) 相連圖 非相連圖 * 無向圖重要名詞 (6/10) 完全圖(complete graph) 一個具n個端點的無向圖中任何二端點間均恰有一邊直接相連，則恰具有 個邊。完全圖圖必定是連通圖 * 無向圖重要名詞 (7/10) 多重圖(multi-graph) 圖形中若有兩個端點間的邊數大於或等於2，則此圖形即為多重圖 簡單圖(simple graph) 圖形中，任二端點間最大的邊數為1 * 無向圖重要名詞 (8/10) 分支度(degree) 一端點的分支度是指與該端點相鄰(adjacent)的端點個數 * 無向圖重要名詞 (9/10) 尤拉路徑(Eulerian path) 在一無向圖中，若存在一條路徑可由起點出發，恰經過所有邊一次，最後到達終點(終點與起點不同)，則可稱此路徑為尤拉路徑。尤拉路徑的充分必要條件為除了二個端點的分支度為奇數外，其餘必需均為偶數。尤拉路徑又稱為尤拉鏈結(Eulerian chain) * 無向圖重要名詞 (10/10) 尤拉循環(Eulerian cycle) 在一無向圖中，若存在一條路徑可由起點出發，恰經過所有邊一次，最後再回到起點(終點與起點相同)，則可稱此路徑為尤拉循環。尤拉循環的充分必要條件所有端點的分支度均為偶數 * 尤拉循環(Eulerian cycle) * 有向圖重要名詞 (1/3) 完全圖(complete graph) 一個具n個端點的有向圖中任何二端點間均恰有一邊直接相連，則恰具有n(n-1)個邊 路徑(path) 在有向圖形中，路徑是指一組由一連串端點所形成的連續序列，連接端點的邊皆為有向邊 相鄰(adjacent) 端點x adjacent to 端點y，端點y adjacent from 端點x * 有向圖重要名詞(2/3) 強連結(strongly connect