图的应用实例 生成树]设G(V,B是一个无向图,当且 仅当G中每一对顶点之间有一条路径时,可 认为G是连通的( connected) 个n节点的连通图必须至少有m1条边。 因此当通信网络的每条链路具有相同的建 造费用时,在任意一棵生成树上建设所有 的链路可以将网络建设费用减至最小,并 且能保证每两个城市之间存在一条通信路 径。如果链路具有不同的耗费,那么需要 在一棵最小耗费生成树上建立链路。 下一页 第16页
下一页 上一页 停止放映 第 16 页 图的应用实例 ⚫ [生成树] 设G= (V,E)是一个无向图，当且 仅当G中每一对顶点之间有一条路径时，可 认为G是连通的（ c o n n e c t e d） ⚫ 一个n节点的连通图必须至少有n- 1条边。 因此当通信网络的每条链路具有相同的建 造费用时，在任意一棵生成树上建设所有 的链路可以将网络建设费用减至最小，并 且能保证每两个城市之间存在一条通信路 径。如果链路具有不同的耗费，那么需要 在一棵最小耗费生成树上建立链路
图的应用实例 28 2 10 14/\16 14/16 14/16 25\24 2524 18/12 8 22 停止放映 图12-4连通图和它的两棵生成树 下一页 a)图b)耗费为100的生成树c耗费为129的生成树 第17页
下一页 上一页 停止放映 第 17 页 图的应用实例
二、图的存储结构 邻接矩阵表示法 根据图的定义可知,图的逻辑结构分为两部分:V(顶 点)和E(边或弧)的集合。因此, 用 维数组存放图中所有顶点数据 用一个二维数组存放顶点间关系(边或弧)的数据, 称这个二维数组为接矩阵。 邻接矩阵又分为有向图接矩和无向图接矩阵 1234 停止放映 1010 下一页 410 第18页
下一页 上一页 停止放映 第 18 页 二、图的存储结构 ⚫ 1、邻接矩阵表示法 ⚫ 根据图的定义可知，图的逻辑结构分为两部分：V（顶 点）和E（边或弧）的集合。因此， –用一个一维数组存放图中所有顶点数据； –用一个二维数组存放顶点间关系（边或弧）的数据， 称这个二维数组为邻接矩阵。 –邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。 1 2 3 4 1 0 1 0 1 2 1 0 1 0 3 0 1 0 1 4 1 0 1 0
有向图的邻接矩阵 定义 设图G=(V,E)是有n(n≥1)个顶点的图,则G的邻 接矩阵是具有下述性质的nxn的方阵,元素为: 1当〈Ⅵi,Vj∈E时(存在弧) A[ i, j] 0当〈Ⅵi,VjE时(不存在弧) 例如,G2的邻接矩阵为: 3 0110 G nodes=/2 0000 3 A= GArc= 000 4 10004x4 停止放映 ★意:不一定对称,对角线全为0 第19页
下一页 上一页 停止放映 第 19 页 有向图的邻接矩阵 ⚫ 定义 设图G=（V，E）是有n（n 1）个顶点的图，则G的邻 接矩阵是具有下述性质的nxn的方阵，元素为： 1 当〈Vi，Vj> E 时 （存在弧） A[ i，j] = 0 当〈Vi，Vj> E 时 （不存在弧） 例如，G2的邻接矩阵为： G.nodes= 1 2 3 4 A= G.Arc= 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 4x4 1 3 2 4 G2 注意：不一定对称，对角线全为0
无向的图邻接矩阵 定义 v1√2接矩阵是具有下述性质的对称阵,元素为:0 设图G=(,E)是有n(n≥1)个顶点的图 的邻 1当(Vi,Vj)∈E时(有边) AL i, j]=Alj,i]= 0 0当i,Vj)gE时(无边) 3v4 无向图的邻接矩阵是一个对称矩阵 例如,G1的邻接矩阵为: 0110 2 1011 G nodes 3 A=G edge 1100 停止放映 4 01004x4 ★意:一定对称,对角线全为0 第20页
下一页 上一页 停止放映 第 20 页 无向的图邻接矩阵 ⚫ 定义 设图G=（V，E）是有n（n 1）个顶点的图，则G的邻 接矩阵是具有下述性质的对称阵，元素为： 1 当(Vi，Vj） E 时(有边) A[ i，j] =A[j,i] = 0 当(Vi，Vj） E 时（无边） 无向图的邻接矩阵是一个对称矩阵 例如，G1的邻接矩阵为： G.nodes = 1 2 3 4 A=G.edge = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4 o o o o v1 v2 v3 v4 G1 注意：一定对称，对角线全为0