图论核心概念
郝伟 2020/05/13

1 简介 (Introduction)
2 术语定义 (Terms)
3 最小生成树 Minimum Spanning Trees
4 单源最短路径 Single Source Shortest Path
- 4.1 定义 (Definition)
- 4.2 算法 (Algorithms)
5 小结
6 参考资料

1 简介 (Introduction)

在数据结构中，图论的相关知识点很多，为了方便学习，本文对相关内容进行了最简要的总结。

2 术语定义 (Terms)

2.1 图 (Graph)

由顶点和边组成的集合，通常表示为： $G=(V,E)$ ，其中， $G$ 表示一个图， $V$ 是图中顶点的集合， $E$ 是图 $G$ 中边的集合。

2.2 节点 (Vertex)

网络中的节点是网络中的个体，包括一定的数据。实际上，Vertex的本意是顶点，而网络中用的是Node表示结点，但是在使用的过程中，大家更喜欢使用节点，所以最终节点流行开来。

2.3 边 (Edge)

两个节点的连接。边上可以有权值(Weight)，可以是有向的(Directed)，也可以是无向的(undirected)

2.4 权值 (Weight)

边的属性，表示边的价值。常见的权值有距离，时间等。

2.5 有向 (Directed)

边的属性，表示边是有方向的。如航班、车次是有方向的。

2.6 无向 (Undirected)

边的属性，与有向相对，表示没有方向。如两点的距离，行程间的费用等。

2.7 有/无向图 (Directed/undirected graph)

在图中的边是否有方向决定了整张图是有向图或是无向图。所有边是否有向的属性一般是一致的，即要么都是有向边要么都是无向边，极少有混合情况。

2.8 连通 (Connected)

在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连，则称 i 和 j 是连通的。如果 G 是有向图，那么连接 i 和 j 的路径中所有的边都必须同向。

2.9 连通图 (Connected Graph)

如果图中任意两点都是连通的，那么图被称作连通图。连通性是图的基本性质。

2.10 强连通图 (Strongly Connected Graph)

双向都有路径的有向连通图。

3 最小生成树 Minimum Spanning Trees

3.1 定义 (Definition)

用最小数量的边连接所有的节点，同时这些边的权值之中最小。目前常见生成算法只有Kruskal和Prim两种算法。

3.2 Prim 算法

核心思想：每次添加剩下的权值最小的边至最小生成树中，循环至所有节点都包括进来为止。

3.3 Kruskal 算法

每次选择权值最小的能够连接两个不连通图边，循环直到无可添加的不连通图为止。

4 单源最短路径 Single Source Shortest Path

4.1 定义 (Definition)

4.2 算法 (Algorithms)

4.2.1 广度优先搜索 (Breadth First Search)

从一个节点出发为第0层，搜索它的所有子节点为第1层，如果第1层的子节点有子节点为第2层，将遇到的第2层放到队列中，等到所有的第1层子节点处理完，再处理第2层。以此类推，直到所有节点处理完。

4.2.1 深度优先搜索 (Breadth First Search)

从一个节点出发为第0层，搜索它的所有子节点为第1层，如果第1层的子节点有子节点为第2层，将遇到的第2层则优先处理第2层的，如果有第3层则继续处理第3层，直到没有子节点，然后返回上一层。以此类推，直到所有节点处理完。

4.2.3 Bellman-Ford 算法

贪心算法，每次在剩下的边中找到边长最短的，加入现有搜索图中，并更新权值，循环直到结束。

4.2.4 Dijkstra 算法

每次添加能够更新当前节点值的最小候补节点，直到对所有候补节点完成搜索。

4.2.5 A* 算法

搜索是同时计算与起点和终点的距离，尽可能向两个方向之和最小的方向搜索。