算法笔记（七）—— 图的相关知识及算法

图的存储方式

1. 邻接表（记录关于某点的直接相邻点）

2. 邻接矩阵（一定是正方形的矩阵，对点进行编号，点到点的权值由距震中的值表示，无直接相连记为正无穷）

图的模板

unordered_map<int,Node>

unordered_set<Edge>

Node类：值、入度、出度、点发散出去的边连接的邻居、属于该点的边

Edge类：权值（距离）、起始点（from）、终止点（to）

图的宽度优先遍历

使用unordered_set来进行去重，放置重复点进队列

 

图的深度优先遍历

 

拓扑排序

有向无环图，先处理入度为0的点，然后将该点及其影响擦掉，继续寻找入度为0的点，周而复始。

无向图生成最小生成树（K算法 P算法）

保证连通性且整体边权值最小

K算法（从边的角度出发）

1. 对所有边排序，从最小开始考虑

2. 如果加上该边没有形成环则加上，若形成环则考虑下一条边

怎么考虑会不会形成环：假设所有点一开始自己是个集合（都不连通），判断是否有环，看一条边的from和to在不在一个集合，若不在将两个点所在集合合并。

P算法

1. 所有边都被锁定

2. 从某点出发，将该点直接相连的所有边解锁，选权值最小的边（且左右两侧不在一个模型内），将邻点加入，周而复始。

Dijkstra算法（要求没有累加权值为负数的环）

规定出发点 ，该点到所有点的最短距离

1. 初始化，到自己0，到别的点正无穷

2. 从当前最小值对应的点出发，看其所有的边，发现了更短的距离则改写

3. 周而复始即可，直到所有点都作为出发点被遍历到