数据结构 第7 章 图的定义和术语

《数据结构 第7 章 图的定义和术语》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7.1图的定义和术语定义：图(Graph)是一种复杂的非线性数据结构，由顶点集合及顶点间的关系（也称弧或边）集合组成。可以表示为：G＝(V,{VR})其中V是顶点的有穷非空集合；VR是顶点之间关系的有穷集合，也叫做弧或边集合。弧是顶点的有序对，边是顶点的无序对。生成树：所有顶点均由边连接在一起，但不存在回路的图。一个图可以有许多棵不同的生成树。注所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同；生成树是图的极小连通子图；一个有n个顶点的连通图的生成树有n-1条边；生成树中任意两个顶点间的路径是唯一的；在生成树中再加一条边必然形成回路。含n

2、个顶点n-1条边的图不一定是生成树。7.2图的存储结构7.2.1数组表示法（邻接矩阵表示法）特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n-1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²，空间复杂度为O(n2)，用于稀疏图时空间浪费严重。无向图中顶点vi的度TD(vi)是邻接矩阵中第i行1的个数。有向图中顶点vi的出度是邻接矩阵中第i行1的个数。顶点vi的入度是邻接矩阵中第i列1的个数。7.2.2邻接表（类似于树的孩子链表表示法）v2v1v3v4v5G2v1v3v4v2v5012343^142^04

3、3^12^02^1特点：若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。无向图中顶点vi的度为第i个单链表中的结点数。v2v1v3v4G101232^13^^0v1v3v4v2^0123^30^^2v1v3v4v2^0邻接表逆邻接表顶点vi的出度为第i个单链表中的结点个数。特点：顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数。找出度易，找入度难。找入度易，找出度难。顶点vi的入度为第i个单链表中的结点个数。顶点vi的出度为整个单链表中邻接点域值是i-1的结点个数。弧结点abcd01237.2.3十字链表01

4、2002^30^31^32^23^^bdactailvexheadvexhlinktlinkdatafirstinfirstout顶点结点^^指向依附于ivex的下一条边7.2.3邻接多重表（无向图的另一种链式存储结构）邻接表优点：容易求得顶点和边的信息。缺点：某些操作不方便（如：删除一条边需找表示此边的两个结点）。邻接多重表：每条边用一个结点表示。其结点结构如下：指向依附于jvex的下一条边markivexilinkjvexjlinkinfo边结点datafirstedge顶点结点存与顶点有关的信息指向第一条依附于该顶点的边标志域标记此边是否被搜索过

5、该边依附的两个顶点在表头数组中位置0301234v2v1v3v4v5G2v1v2v3v4v50123212441^^^^^markivexilinkjvexjlinkinfo边结点datafirstedge顶点结点7.2.3邻接多重表（无向图的另一种链式存储结构）7.3图的遍历深度优先遍历（Depth_FirstSearch——DFS）广度优先遍历（Breadth_FristSearch——BFS）7.4.3最小生成树构造最小生成树方法：方法一：普里姆(Prim)算法。方法二：克鲁斯卡尔(Kruskal)算法。最小生成树可能不惟一V1V6V5V4V3V

6、26513566425拓扑排序的方法：在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止一个AOV网的拓扑序列不是唯一的7.5.2关键路径把工程计划表示为有向图，用顶点表示事件，弧表示活动，弧的权表示活动持续时间。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。称这种有向图为边表示活动的网络，简称为AOE（ActivityOnEdge）网。对于AOE网，我们关心两个问题：(1)完成整项工程至少需要多少时间？(2)哪些活动是影响工程进度的关键？求关键

7、路径步骤：求ve(i)、vl(j)求e(i)、l(i)计算l(i)-e(i)7.6最短路径7.6.1单源点最短路径（从某个源点到其余各顶点的最短路径）迪杰斯特拉（Dijkstra）算法：按路径长度递增次序产生各顶点的最短路径。7.6.2每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次。方法二：弗洛伊德(Floyd)算法算法思想：逐个顶点试探，从vi到vj的所有可能存在的路径中，选出一条长度最短的路径。