《数据结构 第七章 图 7.1—7.22000版本(改)》由会员分享，可在线阅读，更多相关《数据结构 第七章 图 7.1—7.22000版本(改)（149页珍藏版）》请在金锄头文库上搜索。
1、 线性表中 数据元素之间仅有线性关系 每 个数据元素只有一个直接前驱和一个直接后 继 在树形结构中 数据元素之间有着层次关系 每一层上的数据元素可能和下一层中多个 元素相关 只能和上一层中一个元素相关 在图形结构中 结点之间的关系是任意的 图中任意两个数据元素之间都可能相关 7 1 图的定义和术语 7 2 图的存储结构 7 3 图的遍历 7 4 图的连通性问题 7 5 有向无环图及其应用 7 6 最短路径 图是由一个顶点集 V vertex 和一个 弧集 边集 R arc 构成的数据结构 Graph V R 其中数据关系R R VR VR v w V 且 P v w 表示从 v 到 w 的一条
2、 弧 谓词 P v w 定义了弧 的意义或信 息 图的定义 顶点 图中的数据元素 若 VR 则表示从v到w的 一条弧 v为弧尾 初始点 w为弧头 终端点 由于 弧 是有方向的 因此 称由顶点集和弧集构成的图为有向图 例如 G1 V1 VR1 其中 V1 A B C D E VR1 A B CD E 若 VR 必有 VR 即VR是对称的 则以无序对 v w 代替这两个有序对 表 示v 和 w 之间的一条边 B C A D F E 由顶点集和边 集构成的图称 作无向图 例如 G2 V2 VR2 V2 A B C D E F VR2 A B A E B E C D D F B F C F 名词和术语
3、 权 网 子图 完全图 有向完全图 稀疏图 稠密图 邻接点 依附 相关联 度 入度 出度 路径 回路 环 简单路径 简单回 路 简单环 连通 连通图 连通分量 强连通图 强连通分量 生成树 生成森林 假设图中有n 个顶点 e 条边 则 含有 e n n 1 2 条边的无向图称作 完全图 含有 e n n 1 条弧的有向图称作 有向完全图 图中最大边数是多少 图中最大弧数是多少 有很少条边或弧 e nlogn 的图称 为稀疏图 否则称作稠密图 权 与图的边或 弧相关的数 网 带权的图 A BE CF 15 9 7 21 11 3 2 B A E F B C 有两个图G V E 和 图 G V E
4、 且 V V E E 则称 G 为 G 的子图 A BE CF 例如 TD B TD A 边 v v 依附于顶点v 和v 边 v v 和顶点v 和v 相关联 顶点v的度是和顶点v相关联的 边的数目 A C D F E B 对于无向图G V E 如果边 v v E 则称v 和v 互为邻接点 即v和v 相邻接 3 2 顶点的出度 OutDegree 以顶点v为尾的弧的数目 A BE CF 顶点的入度 InDegree 以顶点v为头的弧的数目ID B 例如 OD B TD B 对于有向图G V A 如 果弧 A 则称顶点 v邻接到顶点v 顶点v 邻接 自顶点v 顶点的度 TD 出度 OD 入度 ID
5、 1 2 3 无向图G V E 中从顶点v 到顶点v 的路 径是一个顶点序列 v vi 0 vi 1 vi m v 其中 vi j 1 vi j E 1 j m 如果G是有向图 则路径也是有向的 顶点序列应满足 E 1 j m 路径长度是路径上边的数目 A BE CF 简单路径 序列中顶点不重 复出现的路径 简单回路 简单环 除了第 一个顶点和最后一个顶点 之外 其余顶点不重复出 现的回路 回路 环 第一个顶点 和最后一个顶点相同的路 径 ABCFA BCF AECFA 若图G中任意两个顶点 vi vj V vi和vj都是连通 的 则称此图为连通图 B A C D F E 在无向图G中 如果从
6、 顶点v到顶点v 有路径 则称v和v 是连通的 无向图中的极大连通子图是连通分量 B A C D K I ML E E B A C ML DE K I E 在有向图中 对于每一对vi vj V vi vj 从 vi到vj和从vj到vi都存在路径 则称此有向图 为强连通图 有向图中的极大强连通子图称作有向图的 强连通分量 A BC FA BC F 一个连通图的生成树是一个极小连通子图 它含有图中全部顶点 但只有足以构成 一棵树的n 1条边 B C F E 如果在一棵生成树中添加一条边 必 定构成一个环 一棵有n个顶点的生成树有且仅有n 1 个边 一个图有n个顶点和小于n 1条边 则 是非连通图
7、如果多于n 1条边 则一定有环 有n 1条边的图不一定是生成树 B C F E 一个有向图的生成森林由若干棵有 向树组成 含有图中全部顶点 但只有 足以构成若干棵不相交的有向树的弧 ABC EDF A BF E D C 有向图及其生成森林 结构的建立和销毁 插入或删除顶点 对邻接点的操作 对顶点的访问操作 遍历 插入和删除弧 基本操作 CreatGraph 若G存在 u和G中顶点有相同特征 若存在u 则返回该顶点在图中 位置 否则返回其它信息 GetVex G v 返回 v 的值 PutVex 对v赋值value 对邻接点的操作 FirstAdjVex G v 返回 v 的第一个邻接点 若该顶
8、点 在 G 中没有邻接点 则返回 空 NextAdjVex G v w 返回 v 的 相对于 w 的 下一个邻接 点 若 w 是 v 的最后一个邻接点 则 返回 空 插入或删除顶点 InsertVex 在图G中增添新顶点v DeleteVex 删除G中顶点v及其相关的弧 插入和删除弧 InsertArc 在G中增添弧 若G是无向的 则还增添对称弧 DeleteArc 在G中删除弧 若G是无向的 则还删除对称弧 遍历 DFSTraverse G Visit 深度优先遍历图G 并对每个顶点调用 函数Visit一次且仅一次 一旦visit 失 败 则操作失败 BFSTraverse G Visit
9、广度优先遍历图G 并对每个顶点调 用函数Visit一次且仅一次 一旦visit 失败 则操作失败 一 数组 邻接矩阵 表示法 二 邻接表 三 有向图的十字链表 四 无向图的邻接多重表 一 数组 邻接矩阵 表示法 无向图的邻接矩阵 用两个数组分别存储顶点的信息和 顶点之间关系 B A C D FE 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 为 对 称 矩 阵 A B C D E F A B C D E F 利用邻接矩阵容易 判定两个顶点间是否有 边相连 无向图中 顶 点vi的度是邻接矩阵第i 行
10、 或第j列 元素之 和 有向图的邻接矩阵 A BE CD 为 非 对 称 矩 阵 A B C D E A B C D E 对于有向图 第i行 元素之和为顶点vi的 出度 第j列元素之 和为顶点vj的入度 A BE CD 15 9 7 21 11 3 2 有向网的邻接矩阵 15 9 3 2 11 7 21 A i j wi j 若或 vi vj VR 反之 typedef struct ArcCell 弧的定义 VRType adj VRType是顶点关系类型 对无权图 用1或0表示相邻否 对带权图 则为权值类型 InfoType info 该弧相关信息的指针 ArcCell AdjMatrix
11、 MAX VERTEX NUM MAX VERTEX NUM define INFINITY INT MAX 最大值 define MAX VERTEX NUM 20 最大顶点个数 Typedef enum DG DN UDG UDN GraphKind 有向图 有向网 无向图 无向网 图的数组 邻接矩阵 存储表示 typedef struct 图的定义 VertexType vexs MAX VERTEX NUM 顶点向量 AdjMatrix arcs 邻接矩阵 int vexnum arcnum 图的当前顶点数和弧数 GraphKind kind 图的种类标志 MGraph Status
12、CreateUDN MGraph IncInfo为0则各弧不含其他信息 For i 0 i G vexnum i scanf i G vexnum i 初始化邻接矩阵 For j 0 j G vexnum j G arcs i j INFINITY NULL adj info For k 0 k G arcnum k 构造邻接矩阵 Scanf 输入一条边依附的顶点及权值 i LocateVex G v1 j LocateVex G v2 确定v1和v2在G中位置 G arcs i j adj w 弧的权值 If IncInfo Input G arcs i j info 若弧含有相关信息 则输
13、入 G arcs j i G arcs i j 置的对称弧 Return OK CreateUDN typedef struct ArcNode 弧的结点结构 int adjvex 该弧所指向的顶点的位置 struct ArcNode nextarc 指向下一条弧的指针 InfoType info 该弧相关信息的指针 ArcNode adjvex nextarc info表结点结构 define MAX VERTEX NUM 20 邻接点域 链域 数据域 二 图的邻接表 typedef struct VNode 顶点的结点结构 VertexType data 顶点信息 ArcNode firs
14、tarc 指向第一条依附该顶点的弧的指针 VNode AdjList MAX VERTEX NUM data firstarc 头结点结构 数据域 链域 typedef struct 图的结构 AdjList vertices int vexnum arcnum 图的当前顶点数和弧数 int kind 图的种类标志 ALGraph 图的结构 0 A 1 B 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3 B A C D FE 无向图的邻接表 邻接点域 链域 数据域 链域 14 0 4 5 顶点vi的度恰为 第i个链表中的 结点数 如何求某结点的度 1 4 2 3 0 1 2
15、 0 1 2 3 4 A B C D E 有向图的邻接表 A BE CD 可见 在有向图的邻接 表中不易找到指向该顶 点的弧 入弧 求入度需 遍历整个邻接表 邻接点域 链域 数据域 链域 如果求入度 A BE CD 有向图的逆邻接表 A B C D E 3 30 0 1 2 3 4 在有向图的逆邻接表 中 对每个顶点 链 接的是指向该顶点的 弧 入弧 邻接点域 链域 数据域 链域 1 2 0 4 三 有向图的十字链表 弧结点结构 弧尾顶点位置 弧头顶点位置 弧的相关信息 指向弧头相同的下 一条弧 typedef struct ArcBox 弧的结构表示 int tailvex headvex
16、该弧的尾和头结点的位置 struct ArcBox hlink tlink 分别为弧头相同和弧尾相同的弧的链域 InfoType info 该弧相关信息的指针 ArcBox define MAX VERTEX NUM 20 指向弧尾相同的下 一条弧 顶点的结点结构 顶点信息数据 指向以该顶点 为弧头的第一 个弧结点 指向以该顶点 为弧尾的第一 个弧结点 typedef struct VexNode 顶点的结构表示 VertexType data ArcBox firstin firstout 分别指向该顶点第一条入弧和出弧 VexNode typedef struct VexNode xlist MAX VERTEX NUM 表头向量 int vexnum arcnum 有向图的当前顶点数和弧数 OLGraph 有向图的结构表示 四 无向图的邻接多重表 typedef struct Ebox VisitIf mark 访问标记 int ivex jvex 该边依附的两个顶点的位置 struct EBox ilink jlink 分别指向依附这两个顶点的下一条边 InfoType inf
