README.md

图

图论基础

• 构成

  节点（Vertex）

  边（Edge）

• 应用

  交通运输、社交网络、互联网、工作安排、程序状态执行

• 分类

  无向图、有向图

  无权图、有权图

• 连通性

• 简单图

  没有自环边和平行边

图的表示

• 邻接矩阵（Adjacency Matrix）

  适合稠密图（Dense Graph）

• 邻接表（Adjacency Lists）

  存储空间小，适合稀疏图（Sparse Graph）

  vector代替链表实现（链表便于删除）

相邻点迭代器

• 遍历邻边

  邻接表效率更高

  使用迭代器

图的算法框架

• 从文件中读取测试用例

深度优先遍历和联通分量

• 深度优先遍历

  和树的区别：需要记录是否遍历过

  计算连通分量

  判断节点是否连接

寻路

获得两点间的一条路径

• 深度优先遍历复杂度

  邻接表：O(V+E)

  邻接矩阵：O(V^2)

• 检测环

广度优先遍历和最短路径

队列实现（层序优先遍历）

• 广度优先遍历求出了无权图的最短路径

• 广度优先遍历复杂度

  邻接表：O(V+E)

  邻接矩阵：O(V^2)

参考

1. 算法与数据结构--综合提升篇（c++版）