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

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

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

二 图的概念和术语

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网
  • 关键路径：办公司装修时间、家庭宴会准备时间

八 图示