图的定义

• 有向图、无向图
• 简单图、多重图，区别：平行边和自环
• 有向完全图、无向完全图，相同点：该有的边或弧都有，区别：边和弧、n(n-1)/2、n(n-1)
• 极大连通子图、极小连通子图，相同点：无向图，连通图，区别：边
• 极大强连通子图、极小强连通子图，相同点：有向图、连通图，区别：边
• 连通分量、强连通分量，区别：有向图、无向图
• 生成树、生成森林
• 度、入度、出度
• 边的权和网，带权图即网
• 稠密图、稀疏图，稠密适用于邻接矩阵法，稀疏适用邻接表
• 路径、路径长度、回路
• 距离，最短路径或无穷大
• 有向树，顶点入度0，其余入度1

存储结构

1. 邻接矩阵法
   稠密图
   顺序结构
   顶点集、边集
   斜对称
   

2. 邻接表法
   稀疏图
   查出度简单，入度难
   顶点表顺序、边表链式
   

3. 十字链表
   有向图
   链式
   出入度简单
   

4. 邻接多重表
   无向图
   链式
   解决删除一条边需要删除两个边表结点
   

图的遍历

广度优先搜索

BFS
类似于树的层次遍历
队列+辅助数组

深度优先搜索

类似于树的先序遍历
DFS

图的应用

最小生成树

用最短的路连通各点
生成树：包含全部顶点的极小连通子图


当所有边的权不同时最小生成树唯一

只有n-1条边时最小生成树唯一

性质

Prim

按点
先将一个起点加入最小生成树，之后不断寻找与最小生成树相连的边权最小的边能通向的点，并将其加入最小生成树，直至所有顶点都在最小生成树中。

克鲁斯卡尔算法

按边

最短路径

迪杰斯特拉算法

求单源最短路径

Floyd算法

求各顶点之间最短路径问题

拓扑排序

有向无环图用于工程

AOV和AOE区别在于用顶点还是边表示活动

拓扑排序方法去除入度为0的顶点
拓扑排序可以检测AOV网是否有环

关键路径

小总结

存储结构：

• 邻接矩阵法：稠密图
• 邻接表法：稀疏图
• 十字链表：有向图，解决邻接表查找入度
• 邻接多重表：无向图，解决每次删除两结点

遍历
BFS:队列和辅助数组
DFS:工作栈

应用

• 最小生成树

1. Prim按点
2. 克鲁斯卡尔算法按边

• 最短路径

1. 迪杰斯特拉算法求单源最短路径
2. Floyd求各顶点之间最短路径问题

• 拓扑排序
  AOV点为活动
  AOE边为活动
  拓扑排序方法去除入度为0的顶点
  拓扑排序可以检测AOV网是否有环
• 关键路径
  由关键活动组成的路径