大学教程(零起点)数据结构-1图

第七章 7.1 7.2 7.3

图

图的基本概念 图的存储结构 图的遍历

7.47.5

最小生成树最短路径

7.6

拓扑排序

问题： 电子地图中从起点到终点的最短路径求取 任务分解 子任务1,电子地图在计算机中的存储方式 子任务2,计算机起点到终点的最短路径的方法

问题： 电子地图中从起点到终点的最短路径求取 子任务1分解：电子地图在计算机中的存储方式 进一步分解子任务： 1.1 抽象出电子地图的表示形式 1.2 根据表示形式抽象出电子地图的逻辑形式 1.3 根据逻辑形式设计存储结构 1.4 根据设计的存储结构定义数据结构

问题： 电子地图中从起点到终点的最短路径求取 子任务1分解：电子地图在计算机中的存储方式 进一步分解子任务： 1.1 抽象出电子地图的表示形式

蓬莱 招远 莱州 平度 潍坊 胶州 胶南 即墨 青岛 黄岛 抽象出电子地图的表示形式7

烟台 栖霞 莱阳 莱西 潍坊 乳山

威海

文登

120 招远莱州 100

蓬莱 150 栖霞80

烟台 85

威海55

50 110 文登 莱阳 200 20 平度 70 乳山 莱西 150 110 90 130 潍坊 潍坊 190 胶州70 即墨 220 70 60 青岛 60 胶南 50 黄岛 抽象出电子地图的表示形式8

120 招远莱州 100

蓬莱 150 栖霞80

烟台 85

威海55

50 110 文登 莱阳 200 20 平度 70 乳山 莱西 150 110 90 130 潍坊 潍坊 190 胶州70 即墨 220 70 60 青岛 60 胶南 50 黄岛 抽象出电子地图的表示形式9

O L C 100 200 150 A 190 220

120M 50 I 20 J

150 80

P

R 85 110 55 Q

B

70 N

K 90 110 130 D 70 H10

70 60 G 60 E 50 F 抽象出电子地图的表示形式

问题： 电子地图中从起点到终点的最短路径求取 子任务1分解：电子地图在计算机中的存储方式 进一步分解子任务： 1.1 抽象出电子地图的表示形式 用点和线表示地图，线上的数值表示距离 1.2 根据表示形式抽象出电子地图的逻辑形式 图的定义： 权的定义： 扩展：有向图定义、其他图的术语的定义11

7.1

图的基本概念

图G由两个集合构成，记作G=<V,E> 其中: V(vertex)是顶点的非空有限集合 E(edge)是边的有限集合v1v3

v2v4 v512

如果每条边都没有方向，则为无向图 (vi,vj)和(vj,vi)表示同一条边 如果每条边都有方向，则称有向图 有向图中用箭头表示弧的方向，箭头从弧尾指向弧头 例如右图中的弧：<v2,v4>,v2是弧尾，v4是弧头v1

v3v2 v4 v5

v2

v3

v4

v113

v1 v3 v2 v4 v5

v2

v3

v4

v1

G1={V,E} V={v1,v2,v3,v4,v5 } E={(v1,v2),(v2,v3),(v2,v4),(v3,v5),(v2,v5) } G2={V,E} V={ v1,v2,v3,v4,v5 }, E={<v1,v2>,<v1,v3>,<v2,v3>, <v2,v4>,<v4,v1>}14

完全图： 无向完全图：任意两顶点间都有边的图。

在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

有向完全图:任意两顶点之间都

有方向互为相反的两 条弧相连接的有向图。

在一个含有n个顶点的有向完全图中，有n(n-1)条弧。

v1

v1

v2

v3

v2

v3

邻接点、相关边 无向图中存在边(vi,vj),则称vi和vj互为邻接点 同时称边(vi,vj)依附于顶点vi,vj (vi,vj)是与vi和vj相关联的边 在有向图中，若存在弧<vi,vj>,也称相邻接， 但要区分弧的头和尾v1 v3 v2 v4 v5

v2

v3

v4

v1