青岛大学数据结构与算法——第6章

一 概述

• 图的概念和术语
• 案例引入
• 图的类型定义
• 图的存储结构
• 图的遍历
• 图的应用

二 图的概念和术语

2.1 概念

G=(V,E)：V-定点、E-边

2.2 术语

• 无向图/有向图
• 完全图
• 稀疏图/稠密图
• 网
• 邻接
• 关联/依附
• 定点的度
• 路径/路径长度
• 回路(环)
• 简单路径/简单回路(简单环)
• 连通图(强连通图)
• 权与网
• 子图
• 连通分量/强连通分量
• 极小连通子图
• 生成树/生成森林

三 案例引入

六度空间理论

四 图的类型定义

4.1 图的类型定义ADT Graph

4.2 操作

• 构造图CreateGraph
• 深度优先遍历DFSTraverse
• 广度优先遍历BFSTraverse

五 图的存储结构

5.1 数组邻近矩阵

• 表示：一个矩阵-顶点表、一个矩阵-邻接矩阵
• 操作：在图中查找顶点LocateVex

5.2 邻接表

六 图的遍历

• 深度优先搜索(DFS)
• 广度优先搜索(BFS)

七 图的应用

7.1 最小生成树

• 普里姆(Prim)算法
• 克鲁斯卡尔(Kruskal)算法

7.2 最短路径

• 用途：交通网络问题
• 解决办法：单源最短路径(狄杰斯特拉(Dijsstra)算法)、所有顶点最短路径(弗洛伊德(Floyd)算法)
• 拓扑排序：AOV网、AOE网
• 关键路径：办公司装修时间、家庭宴会准备时间

八 图示