第7章图 阿,图的义。术语和基本运算 阿72图的存储结构 阿3图的遍历与拓扑排 7.4最小性成树 75最短路径 7.6本章小结
第7章 图 7.1 图的定义、术语和基本运算 7.2 图的存储结构 7.3 图的遍历与拓扑排序 7.4 最小生成树 7.5 最短路径 7.6 本章小结
71图的定义、术语 和基本运算 7.1.1图的定义及术 图结构的形式化定义: Graph=(V,R),其中: V={x|x∈D,D是具有相同特性的数据元素的 集合} R=Edge), Edge=(上的意义或信息}
7.1 图的定义、术语 和基本运算 7.1.1 图的定义及术语 图结构的形式化定义： Graph=(V,R)，其中： V={x | xD,D是具有相同特性的数据元素的 集合}； R={Edge}， Edge={ | P(x,y)(x,yV), 谓 词 P(x,y)定义了弧上的意义或信息}
在图结构中,一个元素可以有多个 直接后继,也可以有多个直接前趋。 圆圈之间的连线代 圆圈代表数据元素 表数据元素之间的 关系 3(4 (a)有向图G1 (b)无向图G2 图7.1图的示例
1 2 3 4 5 1 2 3 4 5 (a)有向图 G1 (b)无向图 G2 图7.1 图的示例 圆圈代表数据元素 圆圈之间的连线代 表数据元素之间的 关系 在图结构中，一个元素可以有多个 直接后继，也可以有多个直接前趋
相关术语 顶点( vertex) Edge是两个顶点之间的关系的集合: ∈Edge,则为从x到y的 条弧; x为弧尾或始点;y为弧头或终点。 一此时的图称为有向图
相关术语 • 顶点（vertex） • Edge是两个顶点之间的关系的集合： Edge，则为从x到y的 一条弧； x为弧尾或始点 ；y为弧头或终点。 －－－－此时的图称为有向图
若Edge是对称的 用无序对(x,y)表示x和y之间的一条 边 一此时的图称为无向图 不考虑顶点到自身的边: 完全图:N个顶点,有N(N-1)/2条边的无 向图 有向完全图:N个顶点,有N(N-1)条弧的 有向图; 稀疏图/稠密图
•若Edge是对称的 用无序对(x,y) 表示x和y之间的一条 边。－－－－此时的图称为无向图。 •不考虑顶点到自身的边： 完全图：N个顶点，有N(N-1)/2条边的无 向图； 有向完全图：N个顶点，有N(N-1)条弧的 有向图； •稀疏图 /稠密图
网( Network):带边权的图 子图: 1(2 (a)有向图G,的一些子图 (b)无向图G的一些子图 图7.2图7.1中G1和G的子图示例 无向图中 两顶点互为邻接点 边和顶点相关联;顶点的度
•网（Network）：带边权的图 •子图： 1 2 3 4 5 1 2 3 4 5 (a)有向图 G1 的一些子图 (b)无向图 G2 的一些子图 图7.2 图7.1中G1 和G2 的子图示例 1 3 4 5 •无向图中 两顶点互为邻接点； 边和顶点相关联；顶点的度
有向图中 邻接到/邻接自 顶点的入度/出度 图中的顶点与边/弧之间有以下关系 e=∑TD(v c路径 路径的长度
•有向图中 邻接到/邻接自 顶点的入度/出度 •图中的顶点与边/弧之间有以下关系 ( ) = = n i 1 2 i 1 e TD v •路径 •路径的长度
回路/环 简单路径 ·简单回路/简单环 连通 连通图 连通分量 强连通图(有向图) ·强连通分量
•回路/环 •简单路径 •简单回路/简单环 •连通 •连通图 •连通分量 •强连通图 (有向图) •强连通分量
4(4 (a)图7.1(a)中G1的3个强联通分量(b)图7.1(a)中G,的生成森林示例 图7.3有向图的强联通分量与生成森林 连通图的生成树 有向图的生成森林
1 2 3 4 5 (a) 图7.1(a)中G1 的3个强联通分量 1 2 3 4 5 (b) 图7.1(a)中G1 的生成森林示例 图7.3 有向图的强联通分量与生成森林 •连通图的生成树 •有向图的生成森林
7.1.2图的基本运算及其ADT °图的基本运算 查找,插入和删除 顶点在图中的位置: 人为随意排列
7.1.2 图的基本运算及其ADT • 图的基本运算 查找，插入和删除 顶点在图中的位置： 人为随意排列