4生成树。所谓连通图G的生成树,是G的包含其全 部n个顶点的一个极小连通子图。它必定包含且仅包含 G的n-1条边。下图示出了图G1的一棵生成树 3 无向图G1 G1的一棵生成树 5生成森林。在非连通图中,由每个连通分量都可得 到一个极小连通子图,即一棵生成树。这些连通分量的 生成树就组成了一个非连通图的生成森林。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 11 ⒁生成树。所谓连通图G的生成树，是G的包含其全 部n 个顶点的一个极小连通子图。它必定包含且仅包含 G的n-1条边。下图示出了图G1 的一棵生成树。 ⒂生成森林。在非连通图中，由每个连通分量都可得 到一个极小连通子图，即一棵生成树。这些连通分量的 生成树就组成了一个非连通图的生成森林
8.1.2图的基本操作 (1) CreatGraph(G)输入图G的顶点和边,建立图G的存储 2 Destroy Graph(G)释放图G占用的存储空间。 (3) GetVe(G,V)在图G中找到顶点V,并返回顶点v的相 关信息。 (4)Puve(G,v,vaue)在图G中找到顶点v,并将vaue 值赋给顶点V。 (5 InsertVex(G,)在图G中增添新顶点v。 (6) Deletevex(G,v)在图G中,删除顶点v以及所有和顶 点v相关联的边或弧。 (⑦ inserter(G,V,W)在图G中增添一条从顶点v到顶点 W的边或弧。 8 DeleteArc(G,V,W)在图G中删除一条从顶点v到顶 W的边或弧。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 12 8.1.2 图的基本操作 ⑴CreatGraph（G）输入图G的顶点和边，建立图G的存储。 ⑵DestroyGraph（G）释放图G占用的存储空间。 ⑶GetVex（G，v）在图G中找到顶点v，并返回顶点v的相 关信息。 ⑷PutVex（G，v，value）在图G中找到顶点v，并将value 值赋给顶点v。 ⑸InsertVex（G，v）在图G中增添新顶点v。 ⑹DeleteVex（G，v）在图G中，删除顶点v以及所有和顶 点v相关联的边或弧。 ⑺InsertArc（G，v，w）在图G中增添一条从顶点v到顶点 w的边或弧。 ⑻DeleteArc（G，v，w）在图G中删除一条从顶点v到顶点 w的边或弧
( ODFSTraverse(G,v)在图G中,从顶点v出发深度优先遍历 图G BFSTtaverse(G,v)在图G中,从顶点v出发广度优先遍历 图G。 在图中,顶点是没有先后次序的,但当采用某一种确定的 存储方式存储后,存储结构中顶点的存储次序构成了顶点之 间的相对次序:同样的道理,对一个顶点的所有邻接点,采 用该顶点的第个邻接点表示与该顶点相邻接的某个顶点的 存储顺序,在这种意义下,图的基本操作还有: (LOcate Vex(G,u)在图G中找到顶点u,返回该顶点在图中 位置。 FirstAdj vex(G,v)在图G中,返回v的第一个邻接点。若 顶点在G中没有邻接顶点,则返回“空 3 NextAdjVex(G,v,w)在图G中,返回v的(相对于w的)下 个邻接顶点。若w是v的最后一个邻接点,则返回“空 2021年1月21日 数据结构讲义 13
2021年1月21日 数据结构讲义 13 ⑼DFSTraverse（G，v）在图G中，从顶点v出发深度优先遍历 图G。 ⑽BFSTtaverse（G，v）在图G中，从顶点v出发广度优先遍历 图G。 在图中，顶点是没有先后次序的，但当采用某一种确定的 存储方式存储后，存储结构中顶点的存储次序构成了顶点之 间的相对次序；同样的道理，对一个顶点的所有邻接点，采 用该顶点的第i个邻接点表示与该顶点相邻接的某个顶点的 存储顺序，在这种意义下，图的基本操作还有： ⑾LocateVex（G，u）在图G中找到顶点u，返回该顶点在图中 位置。 ⑿FirstAdjVex（G，v）在图G中，返回v的第一个邻接点。若 顶点在G中没有邻接顶点，则返回“空”。 ⒀NextAdjVex（G，v，w）在图G中，返回v的(相对于w的) 下 一个邻接顶点。若w是v的最后一个邻接点，则返回“空”
8.2图的存储表示 ◆邻接矩阵 ◆邻接表 ◆十字链表 ◆邻接多重表 @ 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 14 8.2 图的存储表示 邻接矩阵 邻接表 十字链表 邻接多重表
82.1邻接矩阵 所谓邻接矩阵( Adjacency Matrⅸx)的存储结构,就是 用一维数组存储图中顶点的信息,用矩阵表示图中各顶 点之间的邻接关系。假设图G=(V,E)有n个确定的顶 点,即V={o1…,Mn13,则表示G中各顶点相邻关系为 个n×n的矩阵,矩阵的元素为: Ar;1ri_d1若(vy)或<vy>是E(G中的边 0若(vy)减或<vy>不是E(G)中的边 若G是网图,则邻接矩阵可定义为: Ar:r:1-(W若(vv)或<y>是E(G)中的边 0或∞若(vv)或<vv>不是E(G)中的边 其中,W表示边(vy)或<y>上的权值;表示一个 计算机允许的、大于所有边上权值的数。 2021年1月21日 数据结构讲义 15
2021年1月21日 数据结构讲义 15 8.2.1 邻接矩阵 所谓邻接矩阵（Adjacency Matrix）的存储结构，就是 用一维数组存储图中顶点的信息，用矩阵表示图中各顶 点之间的邻接关系。假设图G＝（V，E）有n个确定的顶 点，即V＝{v0 ,v1 ,…,vn-1},则表示G中各顶点相邻关系为一 个n×n的矩阵，矩阵的元素为： A[i][j]= 若G是网图，则邻接矩阵可定义为： A[i][j]= 其中，wij表示边(vi ,vj )或<vi ,vj>上的权值；∞表示一个 计算机允许的、大于所有边上权值的数。 { 1 若(vi ,vj )或<vi ,vj>是E(G)中的边 0 若(vi ,vj )或<vi ,vj>不是E(G)中的边 { wij 若(vi ,vj )或<vi ,vj>是E(G)中的边 0或∞ 若(vi ,vj )或<vi ,vj>不是E(G)中的边