《软件技术基础：第六章 图和广义表》由会员分享，可在线阅读，更多相关《软件技术基础：第六章 图和广义表（37页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构算法与数据结构第一章第一章 绪绪 论论第二章第二章 线线 性性 表表第三章第三章 栈和队列栈和队列第四章第四章 串和数组串和数组第五章第五章 二叉树和树二叉树和树第六章第六章 图和广义表图和广义表第七章第七章 排排 序序第八章第八章 查查 找找第九章第九章 文文 件件第六章第六章 图及广义表图及广义表6.1 图定义和术语图定义和术语6.2 图的存储结构图的存储结构6.3 图的遍历图的遍历:广度优先广度优先,深度优先深度优先6.4 生成树生成树6.5 最短路径最短路径6.6 拓扑排序拓扑排序6.7 广义表广义表 6.1 图的定义和术语图的定义和术语背景北京天津上海公路网 图图G G
2、是由两个集合是由两个集合V(G)V(G)和和E(G)E(G)组成组成, ,记作记作G=(V,E).G=(V,E).其中其中V(G)V(G)是图中顶点的非空有限集合是图中顶点的非空有限集合,E(G),E(G)是图边的是图边的有限集合有限集合. .如果图中的边是有方向的如果图中的边是有方向的, ,即边是顶点的有序对即边是顶点的有序对, ,则称则称这样的图为这样的图为有向图有向图. .此时此时, ,有向边也称为有向边也称为弧弧, ,弧的起点弧的起点为为弧尾弧尾, ,终点为终点为弧头弧头, ,表示为表示为V.若图中每条边都若图中每条边都是没有方向是没有方向, ,则为则为无向图无向图一一. . 图的定义
3、图的定义1231234JIHGFEACXB 在一个在一个n n个顶点的无向图中个顶点的无向图中, ,若每个顶点与其他若每个顶点与其他n-1n-1个个顶点之间都有边顶点之间都有边, ,这样的图称为这样的图称为无向完全图无向完全图. .在在n n个顶点的有向图中个顶点的有向图中, ,若每个顶点与其它的若每个顶点与其它的n-1n-1个顶个顶点之间都有弧存在点之间都有弧存在, ,则称该图为则称该图为有向完全图有向完全图在图中在图中, ,若若是一条边，则称顶点是一条边，则称顶点Vi和顶点和顶点Vj是是邻接邻接的的并且称该边依附于顶点并且称该边依附于顶点Vi和顶点和顶点Vj上上度：度：一个顶点的度是依附于
4、该点的边数一个顶点的度是依附于该点的边数一一. . 图的定义图的定义1231234JIHGFEACXB入度：入度：在有向图中，依附于顶点的弧头数目称为该点在有向图中，依附于顶点的弧头数目称为该点的入度的入度出度出度：以某顶点为尾，即依附于该顶点的弧尾数目称：以某顶点为尾，即依附于该顶点的弧尾数目称为该点的出度为该点的出度度：度：入度与出度之和称之为度入度与出度之和称之为度路径：路径：从从顶点顶点Vi到顶点到顶点Vj的顶点序列的顶点序列Vi, Vm, ,Vn, Vj,并且并且s, Vt属于图，则该序列称之为一条路径属于图，则该序列称之为一条路径路径长路径长：路径上边的数量：路径上边的数量一一.
5、. 图的定义图的定义1231234JIHGFEACXB邻接矩阵邻接矩阵6.2 6.2 图的存储图的存储C1C2C3C4C6C5C1C2C3C4C5C6邻接表邻接表6.2 6.2 图的存储图的存储C1C2C3C4C6C5C1C2C3C4C5C6234556566.3 6.3 图的运算图的运算: :遍历遍历Algorithm DFS(V) /纵向优先遍历的递归算法,从v点开始/ visiti的初值均为0,表示未访问,否则表示已访问Visitv = 1;Write(v);For 每一个点属于v的邻点x doIf (visitx = 0) DFS(x);123456786.3 6.3 图的运算图的运算
6、: :遍历遍历Algorithm DFS(V) /纵向优先遍历的非递归算法,从v点开始/ visiti的初值均为0,表示未访问,否则表示已访问入栈,标记表示已访问循环以下内容出栈访问邻点未标记的进栈,并标记123456786.3 6.3 图的运算图的运算: :遍历遍历Algorithm BFS(V) /横向优先遍历的非递归算法,从v点开始/ visiti的初值均为0,表示未访问,否则表示已访问入队,置标记While (队不空) 出队 访问未访问的邻接点入队,并置标记123456786.4 6.4 最小代价生成树最小代价生成树1 定义2 克鲁斯卡尔方法3 莱姆方法1234566513556462
7、6.4 6.4 最小代价生成树最小代价生成树1 定义(生成树):对于图进行遍历,所有走过的边以及结点构成一棵树,称之为生成树.123456123456广度优先搜索生成树6.4 6.4 最小代价生成树最小代价生成树1 定义(生成树):生成树中代价最小的树称为最小代价生成树.1234566513556462该图的代价为: 6+1+5+5+5+3+6+4+2+612345665134该图的代价为: 6+1+5+3+46.4 6.4 最小代价生成树最小代价生成树: :原理原理从最小的代价以最小成本进行扩充12345665135564626.4 6.4 最小代价生成树最小代价生成树: :克鲁斯卡尔方法克
8、鲁斯卡尔方法1将图中的边分为生成树边集E(T)和其他边集E(G),初始状态E(T)为空2在图中找非E(T)中、未访问过的，而且权重最小的一条边(u,v)3如果u, v以及边(u,v)加入到生成树T后,构成圈,则舍弃该边,否则,将该边以及点u,v加入T4 从原图中删除(u,v)边. 5 直到形成树为止12345665135564626.4 6.4 最小代价生成树最小代价生成树: :克鲁斯卡尔方法克鲁斯卡尔方法1234566513556462131123456653556462123456653556462462123456653556461316.4 6.4 最小代价生成树最小代价生成树: :克
9、鲁斯卡尔方法克鲁斯卡尔方法1314621234566535564612345665556462531314626.4 6.4 最小代价生成树最小代价生成树: :克鲁斯卡尔方法克鲁斯卡尔方法123456655564625313146212345665556462531314626.4 6.4 最小代价生成树最小代价生成树: :克鲁斯卡尔方法克鲁斯卡尔方法12345665556462531314621234566556642531314626.4 6.4 最小代价生成树最小代价生成树: :克鲁斯卡尔方法克鲁斯卡尔方法12356656642531314626.4 6.4 最小代价生成树最小代价生成树
10、: :克鲁斯卡尔方法克鲁斯卡尔方法不断地判断是否形成圈.6.4 6.4 最小代价生成树最小代价生成树: :普莱姆方法普莱姆方法12345665135564621将图中的点分为生成树点集V(T)和其他点集V(G),初始状态选定任意点置入V(T)2V(T)中所有点伸出去到达非E(T)中点的长权重最小的一条边(u,v)3u必然是E(T)中点, 将v加入到E(T)中4 直到形成树为止6.4 6.4 最小代价生成树最小代价生成树: :普莱姆方法普莱姆方法1234566513556462112345665135564621316.4 6.4 最小代价生成树最小代价生成树: :普莱姆方法普莱姆方法12345
11、6651355646213145123456651355646213145626.4 6.4 最小代价生成树最小代价生成树: :普莱姆方法普莱姆方法12345665135564621314562251234566513556462131456225536.4 6.4 最小代价生成树最小代价生成树: :普莱姆方法普莱姆方法12345665135564621314562251234566513556462131456225536.4 6.4 最小代价生成树最小代价生成树: :普莱姆方法普莱姆方法不在需要判断圈.算法实现:1 存贮关键元素2 实现算法6.5.1 单源最短路径-Dijkstra (迪捷
12、斯特拉)算法1342503510204565101533015206.5.1 单源最短路径-Dijkstra (迪捷斯特拉)算法1342503510204565101533015206.5.2 每对顶点之间的最短路径-Floyed (弗洛伊德)算法1342105411411A0=从节点i到节点j，中间不经过任何点的最短路径长i, j = 1, 2, , n1342105411411从节点i到节点j，中间经过结点1或直达的最短路径长，即最多经过1的最短路径长， i, j = 1, 2, , n其中：1342105411411从节点i到节点j，中间经过结点2(有可能曾经经过1)，或直达(有可能曾经经过1)的最短路径长， i, j = 1, 2, , n其中：1342105411411从节点i到节点j，中间经过结点n(有可能曾经经过1,2，n-1)，或直达(有可能曾经经过1,2，n-1)的最短路径长i, j = 1, 2, , n其中：6.5.2 每对顶点之间的最短路径-Floyed (弗洛伊德)算法1342105411411算法：算法：1 已经A02 产生A1,A2, ， AnAlgorithm Floyed(A) for( k = 1; k = n k+)/ 产生Ak第六章 图示例：1342105411411
