《数据结构》 第七章上)
《 数据结构》 第七章(上)
数据结构 第七章图 71图的定义和术语 72图的存储结构 721数组表示法 7.2.2邻接表 73图的遍历 73.1深度优先搜索 7.3.2广度优先搜索 74图的连通性问题 74.3最小生成树 75有向无环图及其应用 7.5.1拓扑排序 7.6最短路径 761从某个源点到其余各顶点的最短路径 76.2每一对顶点之间的最短路径
数据结构 tjm 第七章 图 7.1 图的定义和术语 7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.3 最小生成树 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短路径
数据结构 71的定义和术语 图的定义:是一种多对多的结构关系,每个元素 可以有零个或多个直接前趋;零个或多个直接后 继。图是由顶点集合 vertex)及顶点间的关系集 合组成的一种数据结构: Graph=(V,R) 其中V={v|v∈某个数据对象} 是顶点的有穷非空集合; R=VR}={(vw)|vw∈V 图的类型定义参见P156
数据结构 tjm 图的类型定义参见P156 7.1 图的定义和术语 图的定义：是一种多对多的结构关系，每个元素 可以有零个或多个直接前趋；零个或多个直接后 继。图是由顶点集合(vertex)及顶点间的关系集 合组成的一种数据结构： Graph＝( V, R ) 其中 V = { v | v 某个数据对象} 是顶点的有穷非空集合； R ={VR}={(v, w) | v, w V }
数据结构 甚本术语: 有向图与无向图在有向图中,顶点对<v,W>是 有序的。在无向图中,顶点对(x,y)是无序的。 R2有向圖 有向边又可称为弧<ⅵvj> (6(5 中vi称为狐尾或初始点,v称 为狐头或终端点。 V={2,3,456,7 vR={13><12><3,7><3,6><25>,< 2,6>,<2,4><57><67>}
数据结构 tjm 基本术语： 有向图与无向图 在有向图中，顶点对<v, w>是 有序的。在无向图中，顶点对(x, y)是无序的。 5 3 6 7 2 1 4 有向图 V={1,2,3,4,5,6,7} VR={<1,3>,<1,2>,<3,7>,<3,6>,<2,5>,< 2,6>,<2,4>,<5,7>,<6,7>} 有向边又可称为弧, <vi,vj> 中vi称为狐尾或初始点，vj称 为狐头或终端点
数据结构 无向图 V={1,2,34,5,67 VR={(1,3),(34),(4,5)(12)(26),(27,(6,7, (56)(1,5),(17)
数据结构 tjm 无向图 5 3 6 7 2 1 4 V={1,2,3,4,5,6,7} VR={(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7), (5,6),(1,5),(1,7) }