图

这是一篇关于图的思维导图，包含了生成树包含所有顶点，尽可能少的边=砍去一条边，非连通图，增加一条边，形成回路等。

图

定义

顶点集V和边集E

子主题

注：空表，空树，没有空图(边可以没有，顶点必须有)

有向图

<V1,E1>

无向图

(V,E)

简单图

不存在重复边，不存在顶点到自身的边

多重图

相对于简单图

完全图(简单完全图)

任意两个顶点之间都存在边

子图

连通，连通图

无向图

任意两个顶点连通

连通分量

极大连通分量

包含所有的边

极小连通分量

边数最小且含有所有顶点

强连通图，强联通分量

有向图

生成树，生成森林

入度，出度

稀疏，稠密图

简单路径

不存在重复顶点

简单回路

除顶点和最后一个顶点外，不存在重复顶点

距离：最短路径

有向树：一个顶点入度为0，其余顶点入读均为1

存储

邻接矩阵

适合稠密图

n*n的矩阵

无向图

是对称矩阵且唯一

第i行/列是第i个顶点的度

有向图

第i行列是第i个顶点的出/入度

邻接表

适合稀疏图

不唯一

顺序存储，链式存储

无向图存储空间

O(|V|+2|E|)

有向图存储空间

O(|V|+|E|)

邻接多重表，十字链表

难!理!解!

遍历

广度优先搜索BFS

空间复杂度(最坏)

辅助队列 O(|V|)

时间复杂度

邻接表

O(|V|+|E|)

邻接矩阵

O(|V|^2)

广度优先生成树

深度优先搜索DFS

空间复杂度

递归工作栈 O(|V|)

时间复杂度

邻接表

O(|V|+|E|)

邻接矩阵

O(|V|^2)

深度优先生成树和生成森林

图的遍历和图的连通性

应用

最小生成树

生成树包含所有顶点，尽可能少的边=砍去一条边，非连通图，增加一条边，形成回路

最小生成树不唯一，但各权值互不相等时，唯一

最小生成树的边数=顶点数-1

算法

Prim

Kruskal

有向无环图描述表达式

最短路径

Dijkstra

Floyd

拓扑排序

AOV网

关键路径

AOE网