第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=(<x,y P(xy)∧(x,y∈V),谓词 P(x,y)定义了弧<x,y>上的意义或信息}
7.1 图的定义、术语 和基本运算 7.1.1 图的定义及术语 图结构的形式化定义： Graph=(V,R)，其中： V={x | xD,D是具有相同特性的数据元素的 集合}； R={Edge}， Edge={<x,y> | P(x,y)(x,yV), 谓 词 P(x,y)定义了弧<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是两个顶点之间的关系的集合: <x,y>∈Edge,则<x,y>为从x到y的 条弧; x为弧尾或始点;y为弧头或终点。 一此时的图称为有向图
相关术语 • 顶点（vertex） • Edge是两个顶点之间的关系的集合： <x,y>Edge，则<x,y>为从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)条弧的 有向图； •稀疏图 /稠密图