第2章非线性数据结构树和图

第2章非线性数据结构树和图内容摘要：

方 ）。 弧尾 （ Tail） 弧的起始点 （ Initial Node） 称为弧尾（ 方向后方 ）。 弧 〈 Vx， Vy〉 表示为 ， 弧尾 弧头 Vx Vy 下一页 上一页 停止放映 [第 41页 /91] 顶点、邻接点 顶点 （ Vertex） 图中的数据元素 （ 结点 ） 称为顶点。 如图 G G2中的Ｖ Ｖ 2， 1， 2。 邻接点 （ Adjacent） 无向图中 ,若边 （ Ｖ x,Ｖ y）  E，则Ｖ x和Ｖ y互为邻接点。 有向图中 ， 若弧 〈 Ｖ x,Ｖ y〉 E， 则Ｖ y是Ｖ x的邻接点 ， 反之 ， 不是。 Vx Vy Ｖ x、Ｖ y互为邻接点 Vx Vy Ｖ y是Ｖ x的邻接点 下一页 上一页 停止放映 [第 42页 /91] 顶点的度（ Degree） 无向图中 ， 顶点的 度 是以该顶点为一个端点的边的条数。 例如 ， G1中 V2的度为 3， V4的度为 1。 有向图中 ， 以某顶点为弧头的弧的数目称为该顶点的 入度 （ Indegree）。 例如 G2中顶点 1的入度为1。 以某顶点为弧尾的弧的数目称为该顶点的 出度（ Outdegree）。 例如 G2中顶点 1的出度为 2。 该顶点的度 =入度 +出度。 例如 ， G2中顶点 1的度 =2+1=3。 o o o o v1 v2 v3 v4 G1 1 3 2 4 G2 下一页 上一页 停止放映 [第 43页 /91] 路径、长度 路径 （ Path） 在图中 ， 从顶点 Vx到顶点 Vy的顶点序列 （ Vx， V1，V2， … ,Vn,Vy)称为从 Vx到 Vy的路径。 路径可能是不唯一的。 例如 ， G1中 ， V1到 V3的路径为： （ V1V2V3）或 （ V1V3） ；而 G2中 ， 1到 4的路径为 134。 长度 （ Length） 路径的长度是该路径上边或弧的数目。 例如 ， G1中V1到 V3的长度为 1或 2；而 G2中 1到 4的长度为 2。 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 下一页 上一页 停止放映 [第 44页 /91] 连通图、强连通图、连通分量 连通图（ Connected Graph） 在无向图中，若每一对顶点间都有路径，称此图是连通图。 如图 G3所示。 连通分量（ Connected Component） 无向图中的极大连通子图称为连通 分量。 强连通图 （ Strongly Connected Graph） 在有向图中 ， 若每对顶点 Vx到 Vy间都存在 Vx到 Vy， 及从 Vy到 Vx的路径 ， 则称此图是强连通图。 如图 G4所示。 1 2 3 4 5 G3 2 1 3 4 5 G4 下一页 上一页 停止放映 [第 45页 /91] 子图、生成树 子图 有两个图 G和 G1， 若 V1V， E1  E， 即 V1中的顶点都属于 V中的顶点 ， E1中的关系都属于 E中的关系 ，则称 G1是 G的子图。 G =（ V， E） ， G1=（ V1， E1） （图的部分顶点和部分边组成的图） 生成子图 、 生成树 设 G是一个连通图 ， G中任一包含 G的所有顶点的子图称为生成子图。 如果该子图是树 ， 则称为 G的生成树。 G的生成树不是唯一的。 一棵有 n个顶点的生成树 ， 有且仅有 n1条边 （ 弧 ）。 （子图包含所有顶点，但不一定包含所有边） 下一页 上一页 停止放映 [第 46页 /91] 网、权 权 （ Weight） 若图的边或弧带有与之相关的数 ， 称此数为该边或弧的权。 权通常用来表示从一个顶点到另一个顶点的距离或费用。 网 （ Network） 带权的图称为网。 如 G5为带权的网。 V1 V2 V3 V4 G5 2 3 5 7 下一页 上一页 停止放映 [第 47页 /91] 图的存储方式 1．邻接矩阵 利用数组实现的。 它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。 此二维数组又称 邻接矩阵。 邻接矩阵存储方式可用于无向图或有向图。 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。 下一页 上一页 停止放映 [第 48页 /91] 图的邻接矩阵存储可用下面结构体表示： define MAX_NUM 100 //最大顶点个数 typedef struct { VertexType vexs[MAX_NUM]。 //顶点信息数组 ArcType Matrix[MAX_NUM][MAX_NUM]。 //邻接矩阵 int vexnum,arum。 //图实际顶点数和弧 (边 )数 int kind。 //图种类标志 ,1—有向图 ,2—有向网 // 3—无向图 ,4—无向网 } MGraph。 其中 :ArcType是顶点关系的数据类型。 VertexType是顶点的数据类型。 MAX_NUM表示最多可存的顶点数。 下一页 上一页 停止放映 [第 49页 /91] 假设无向图 G=(V,E)是一个有 n个顶点的图，则图的邻接矩阵 A是 n阶方阵，其内容如下： 其中 W(i,j)是与边或弧相关的权。 其它或当]][[ E)v,(v Ev,vj)W ( i ,=ji A jiji对于含权的网络而言，其邻接矩阵可定义如下：  o t h e r w i s e0,) Ej)( i ,o r Eji,( if1,]j][iΑ[下一页 上一页 停止放映 [第 50页 /91] 0 1 3 2 5 2 8 1 3 0 1 2 3 4 1 0 2 3 4 (a)无向图 (b)有向图 (c)网络 0010100011100110110111110A0 1 3 2 4 0010010010000000010101000A 38 125A0 1 3 2 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 0 1 3 2 (a)无向图邻接矩阵 (b)有向图邻接矩阵 (c)网络邻接矩阵 邻接矩阵举例 下一页 上一页 停止放映 [第 51页 /91] 2．邻接表 邻接表存储形式是一种链表与数组结合的存储形式。 在邻接表中有两种结点，一种是头结点，另一种是表结点。 （ 1）头结点存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。 （ 2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。 （ 3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。 下一页 上一页 停止放映 [第 52页 /91] 邻接表的结点结构 (c)网络的表结点： info next adjvex next adjvex first Vexdata (a)头结点 (b)无权图的表结点： 顶点 Vi的邻接点 与边或弧有关的权值 存放 Vi信息 指向 Vi单链表的第一个结点 指向 Vi的下一个邻接点的指针 顶点 Vi的邻接点 指向 Vi的下一个 邻接点的指针 下一页 上一页 停止放映 [第 53页 /91] 邻接表的举例 无向图中 Vi的度是第 i个单链表的长度。 下一页 上一页 停止放映 [第 54页 /91] 逆邻接表 为求顶点 Vi的入度，对每个顶点 Vi，建立一个链接 以 Vi为弧头的邻接点链表，称该表为逆邻接表。 显然逆邻接表的单链表中结点的个数就是顶点 Vi的 入度。 邻接表中第 i个单链表的长度是顶点 Vi的出度。 逆邻接表中第 i个单链表的长度是顶点 Vi的入度 下一页 上一页 停止放映 [第 55页 /91] 图的邻接表描述 define MAX_NUM 100 //顶点最大允许数量 struct AdjNode { //表结点类型定义 int adjvex。 //该邻接点在数组中的位置 InfoType info。 //该弧相关信息 struct AdjNode *next。 //指向下一邻接点的指针 }。 typedef struct VNode { //头结点类型定义 VertexType data。 //顶点信息 AdjNode *first。 //指向邻接表第一个结点 } AdjList[MAX_NUM]。 下一页 上一页 停止放映 [第 56页 /91] typedef struct { AdjList headArray。 //头结点数组 int vexnum, arum。 //图的当前顶点数和弧数 int kind。 //图的种类标志 } ALGraph。 其中： AdjNode为表结点； InfoType为与边相关信息的数据类型 （ 包括权等 ） ； VNode为头结点； VertexType是顶点的数据类型； MAX_NUM表示最多可以存放的顶点个数。 下一页 上一页 停止放映 [第 57页 /91] 图的遍历 图的遍历 （ Traversing Graph） 从图中指定顶点出发访问图中每一个顶点 ，且使每个顶点只被访问一次 ， 该过程为图的遍历。 图的遍历要比树结构复杂的多。 出发点不同 ， 任一顶点的邻接点就不相同 ， 路径也就不同。 因为图中元素是 ‚ 多对多 ‛ 的关系 ， 为避免发生重复 ， 设立一个辅助数组 visited[]，。