第五章图论讲述.ppt

5.6 树-根树 定义5.6.4 设根树T有t片树叶v1,v2,…,vt，给每片树叶赋一个权值w1,w2,…,wt，则称为T的赋权二叉树，其中l(vi)为叶子结点vi的长度。 如果存在一种赋权方式，使得值?w(i)l(vi)达到最小，则称为棵树为最优二叉树，或称Huffman树。 Huffman树的构造算法： (1)对所有权值从低到高排队； (2)找出两个最小的权值，记为W1和W2。 (3)用W1+W2代替W1与W2，产生新的队列。 (4)若队列中的点数大于1，则回到(1)，否则转(5)。 (5)逆序将以上组合过程画出来便得到Huffman树。 5.6 树-根树 例题 汉字“一地在要工上是中国同和的有”出现频率依次为“2,3,5,7,11,13,17,19,23,29,31,37,41”，对汉字编译。 译出“1000101110100101111”对应的汉字 。 一 地 在 要 工 上 是 中 国 同 和 的 有 2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 34 42 53 31 37 41 65 42 53 37 41 65 42 53 78 65 95 78 95 143 238 5.6 树-根树 原则：左小右大、组合优先、左0右1、不足补0 一 地 在 要 工 上 是 中 国 同 和 的 有 1010111 1010110 101010 10100 0100 0101 1011 000 001 011 100 110 111 5.6 树-根树 原则：左小右大、组合优先、左0右1、不足补0 1000101110100101111” ，每次从根结点开始，100(和)0101(上) 110(的)100(和)1011(是)110(不足补0，凑成110，译为“的”) 此处右边5下方的2，3应画在左边，它违反了组合优先 5.7 最短路径 问题：二点之间数据路径最短，如图5.24中，求结点1到其他各点的最短距离，再求2到其他各点的距离…… Dijkstra算法如下： (1)初始化：D(1)=0，若1结点i有边直接相连则D(i)=边权W(1,i)，否则D(i)=?，S={1}； (2)若?S=?则结束，否则?S中寻找D值最小的点i，S=S+{i}，转(3)。 (3)在?S寻找i的后代j，若d(i)+w(i,j)d(j)，则置d(j)=d(i)+w(i,j)，回到(2)。 5.7 最短路径 (1)初始化。D(1)=0，D(2)=7，D(3)=1，S={1}，?S={2,3,4,5,6}。 (2)距离最小者i=3，S={1,3}，?S={2,4,5,6}。 (3)因d(3)+w(3,2)=6d(2)，故d(2)=6。 因d(3)+w(3,5)=3?，则d(5)=3。 因d(3)+w(3,6)=8?，则d(6)=8。 回到(2) (2)距离最小者i=5，S={1,3,5}，?S={2,4, 6}。 (3)因为d(5)+w(5,4)=8?，则d(4)=8，回到(2) (2)距离最小者i=2，S={1,3,5,2}，?S={4, 6}。 (3)因为d(2)+w(2,6)=78，则d(6)=7，回到(2) (2)距离最小者i=6，S={1,3,5,2,6}，?S={4}。 (3)由于结点4不是结点6后代，故迭代结束。 D(1)=0，D(3)=1，D(5)=3，D(2)=6，D(6)=7，D(4)=8 5.7 最短路径 动态规划算法，适用于分段明显、层次分明的点与点之间的距离，在上图中，结点2既是结点1的子结点，又是结点1的子结点3的子结点，层次紊乱，对于下图的网络，可用动态规划算法求解。 5.7 最短路径 动态规划法求解,细节见教材，结果见图5.26中的虚线所示，每个结点框内的数字为最短距离。 5.8 网络流 在图5.24、图5.25中，如果边的权值表示各边的容量 现在假设是油管，结点1只有流出，称为源结点，结点4只有流入，称为汇聚点，请问如何安排沿途各管道的流速，保证从源出流出尽可能多的油到汇聚点，此类问题称为网络流问题。 5.8 网络流 例 用Edmond-Karp方法求源头1到汇聚点的最大流量。 (1)在每条边标上图2.27所示的数字，如(7,0)它表示最大流速为7，当前流速为0 5.8 网络流 例 用Edmond-Karp方法求源头