图论核心概念 郝伟 2020/05/13
[TOC]
1. 1 简介 (Introduction)
在数据结构中，图论的相关知识点很多，为了方便学习，本文对相关内容进行了最简要的总结。
2. 2 术语定义 (Terms)
2.1. 2.1 图 (Graph)
由顶点和边组成的集合，通常表示为：$G=(V,E)$，其中，$G$表示一个图，$V$是图中顶点的集合，$E$是图$G$中边的集合。
2.2. 2.2 节点 (Vertex)
网络中的节点是网络中的个体，包括一定的数据。实际上，Vertex的本意是顶点，而网络中用的是Node表示结点，但是在使用的过程中，大家更喜欢使用节点，所以最终节点流行开来。
2.3. 2.3 边 (Edge)
两个节点的连接。边上可以有权值(Weight)，可以是有向的(Directed)，也可以是无向的(undirected)
2.4. 2.4 权值 (Weight)
边的属性，表示边的价值。常见的权值有距离，时间等。
2.5. 2.5 有向 (Directed)
边的属性，表示边是有方向的。如航班、车次是有方向的。
2.6. 2.6 无向 (Undirected)
边的属性，与有向相对，表示没有方向。如两点的距离，行程间的费用等。
2.7. 2.7 有/无向图 (Directed/undirected graph)
在图中的边是否有方向决定了整张图是有向图或是无向图。所有边是否有向的属性一般是一致的，即要么都是有向边要么都是无向边，极少有混合情况。
2.8. 2.8 连通 (Connected)
在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连，则称 i 和 j 是连通的。如果 G 是有向图，那么连接 i 和 j 的路径中所有的边都必须同向。
2.9. 2.9 连通图 (Connected Graph)
如果图中任意两点都是连通的，那么图被称作连通图。连通性是图的基本性质。
2.10. 2.10 强连通图 (Strongly Connected Graph)
双向都有路径的有向连通图。
3. 3 最小生成树 Minimum Spanning Trees
3.1. 3.1 定义 (Definition)
用最小数量的边连接所有的节点，同时这些边的权值之中最小。目前常见生成算法只有Kruskal和Prim两种算法。
3.2. 3.2 Prim 算法
核心思想：每次添加剩下的权值最小的边至最小生成树中，循环至所有节点都包括进来为止。
3.3. 3.3 Kruskal 算法
每次选择权值最小的能够连接两个不连通图边，循环直到无可添加的不连通图为止。
4. 4 单源最短路径 Single Source Shortest Path
4.1. 4.1 定义 (Definition)
4.2. 4.2 算法 (Algorithms)
4.2.1. 4.2.1 广度优先搜索 (Breadth First Search)
从一个节点出发为第0层，搜索它的所有子节点为第1层，如果第1层的子节点有子节点为第2层，将遇到的第2层放到队列中，等到所有的第1层子节点处理完，再处理第2层。以此类推，直到所有节点处理完。
4.2.2. 4.2.1 深度优先搜索 (Breadth First Search)
从一个节点出发为第0层，搜索它的所有子节点为第1层，如果第1层的子节点有子节点为第2层，将遇到的第2层则优先处理第2层的，如果有第3层则继续处理第3层，直到没有子节点，然后返回上一层。以此类推，直到所有节点处理完。
4.2.3. 4.2.3 Bellman-Ford 算法
贪心算法，每次在剩下的边中找到边长最短的，加入现有搜索图中，并更新权值，循环直到结束。
4.2.4. 4.2.4 Dijkstra 算法
每次添加能够更新当前节点值的最小候补节点，直到对所有候补节点完成搜索。
4.2.5. 4.2.5 A* 算法
搜索是同时计算与起点和终点的距离，尽可能向两个方向之和最小的方向搜索。