数据结构---图

描述

图是由[节点(Node)]通过[边(Edge)]相连组成的集合，用以表示实体之间的关系。图可以用 来建模社交网络、计算机网络、交通网络等。图包 含[顶点（节点）]和[边（节点之间的连接）]。图可以是[有向的]也可以是[无向的]，并且 可以[包含环]或者是[无环的]。图的遍历算法包括[广度优先搜索]和[深度优先搜索]。

图的术语

• 顶点: 顶点
• 边：顶点之间的连接线称为边。
• 路径：从一个顶点到另一个顶点之间经过的所有顶点的描述
• 路径长度：路劲上对单元路线的计量。
• 环：起点和终点为同一个顶点的路径。
• 负权环：在「加权图」中，如果一个环的所有边的权重加起来为负数，我们就称之为 「负权环」。
• 连通性：两个不同顶点之间存在至少一条路径，则称这两个顶点是连通的。
• 顶点的度：「度」适用于无向图，指的是和该顶点相连接的所有边数称为顶点的度。
• 顶点的入度：「入度」适用于有向图，一个顶点的入度为 𝑑 d，则表示有 𝑑 d 条与 顶点相连的边指向该顶点。
• 顶点的出度：「出度」适用于有向图，它与「入度」相反。一个顶点的出度为 𝑑 d， 则表示有 𝑑 d 条与顶点相连的边以该顶点为起点。

图的分类

• 无向图: 边的两个节点是没有顺序关系的, A-B 和 B-A 是一条边
• 有向图: 边的两个节点是有顺序关系的, A->B 和 B->A 是不同的
• 加权图: 图中的每条边带有一个权重的参数

图的相关算法

• 并查集（ Union Find ）数据结构
• 「图」的深度优先搜索算法
• 「图」的广度优先搜索算法
• 最小生成树相关定理和算法
  • 切分定理
  • Kruskal 算法
  • Prim 算法
• 单源最短路径相关算法
  • Dijkstra 算法
  • Bellman-Ford 算法
• 拓扑排序之 Kahn 算法