每日学习一个数据结构-图

图基础

一、图的定义

在数学中，图是描述于一组对象的结构，其中某些对象对在某种意义上是“相关的”。这些对象对应于称为顶点的数学抽象（也称为节点或点），并且每个相关的顶点对都称为边（也称为链接或线）。通常，图形以图解形式描绘为顶点的一组点或环，并通过边的线或曲线连接。图（Graph）是由顶点的有穷非空集合和顶点之间的连线（边）的集合组成，通常表示为G=(V, E)，其中G表示一个图，V(G)代表图G中的顶点集合，E(G)代表图G中的边集合。

二、图的相关概念

1. 阶：图G中点集V的大小称作图G的阶。

2. 子图：当图G’=(V’,E’)，其中V’包含于V，E’包含于E，则G’称作图G=(V,E)的子图。每个图都是本身的子图。

3. 生成子图：指满足条件V(G’)=V(G)的G的子图G’。

4. 导出子图：

   • 以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。
   • 以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。

5. 度：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。

6. 入度和出度：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。

7. 自环：若一条边的两个顶点为同一顶点，则此边称作自环。

8. 路径：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,…ek,vk，其中ei的顶点为vi及vi-1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。

9. 简单路径：如果路径中除起始与终止顶点可以重合外，所有顶点两两不等，则称为简单路径。

10. 行迹：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。

11. 轨道：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。

12. 回路和圈：闭的行迹称作回路（Circuit），闭的轨称作圈（Cycle）。

13. 桥：若去掉一条边，便会使得整个图不连通，该边称为桥。

三、图的分类

1. 无向图和有向图：

   • 无向图：边没有方向的图。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和< vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧。
   • 有向图：给图的每条边规定一个方向得到的图。在有向图中，边称作弧，含箭头的一端称为弧头，另一端称为弧尾。在有向图中，路径也是有向的。

2. 简单图、多重图、完全图：

   • 简单图：图中若不存在顶点到其自身的边，并且同一条边不会重复出现，这种图称为简单图。简单图分为简单无向图和简单有向图。
   • 多重图：图中某两个顶点之间的边数多于一条，或者顶点通过一条边和自己关联，这种图称为多重图。多重图分为多重无向图和多重有向图。数据结构中所讨论的图一般都是简单图。
   • 完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条边。

3. 稀疏图和稠密图：有很少条边或者弧的图称为稀疏图，反之称为稠密图。稀疏和稠密都是相对而言的，并不是一个精确的数值。

四、图的使用场景

图是一种非常重要的数据结构，在多个领域都有广泛的应用：

1. 计算机科学：图论被广泛应用于算法设计中，如最短路径算法、网络流算法等。此外，图还是许多数据结构的基础，如邻接表、邻接矩阵等。
2. 工程领域：在电路设计中，图可以用来表示电路元件之间的连接关系；在机械设计中，图可以用来表示零件之间的装配关系。
3. 社会学：在社会网络分析中，图可以用来表示人与人之间的社会关系，如朋友关系、合作关系等。
4. 生物学：在生物信息学中，图可以用来表示基因之间的相互作用关系、蛋白质之间的相互作用关系等。
5. 经济学和金融学：图可以用来表示不同经济实体之间的交易关系、投资关系等。
6. 地理信息系统：在GIS中，图可以用来表示地理实体之间的空间关系，如城市之间的交通网络、河流的流向等。

总的来说，图作为一种强大的工具，在各个领域都发挥着重要的作用。通过构建和分析图，人们可以更好地理解和解决复杂的问题。

和图相关的算法

图是一种重要的数据结构，由顶点（或节点）和边组成，用于表示对象及其相互之间的关系。以下是与图相关的一些经典算法：

一、图的遍历算法

1. 广度优先搜索（BFS）
   

   • 从起始节点开始，先访问所有相邻的节点，再依次访问这些相邻节点的未访问过的相邻节点，直到所有节点都被访问过。
   • 适用于寻找最短路径（未考虑边权）等问题。
   • 实现时通常使用队列数据结构。

2. 深度优先搜索（DFS）
   

   • 从起始节点开始，沿着一个分支尽可能深地搜索，直到该分支的末端，然后回溯到上一个节点，继续搜索其他未访问的分支。
   • 适用于解决连通性问题、路径查找、图的遍历等问题。
   • 可以通过递归或显式栈来实现。

3. A*算法

   • 启发式搜索算法，使用启发式函数来评估从源节点到目标节点的路径成本。
   • 通过优先队列来选择下一个要访问的节点，以找到最短路径。
   • 估值函数f(n)=g(n)+h(n)，其中g(n)是从起始搜索点到当前点的代价，h(n)是当前结点到目标结点的估值。

二、最短路径算法

1. Dijkstra算法

   • 解决单源最短路径问题，即求出给定顶点到其他任一顶点的最短路径。
   • 适用于加权图，且图中不包含负权边。
   • 算法依据最短路径的最优子结构性质，从起点开始，每一步都走最短的路径，并不断更新每个点到起点的最短距离。

2. Bellman-Ford算法

   • 解决含负权图的单源最短路径问题。
   • 通过连续进行松弛操作来更新最短路径估计值。
   • 如果在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果。

3. Floyd-Warshall算法

   • 解决任意两点间的最短路径问题。
   • 适用于所有类型的图，包括有向图和带负权边的图。
   • 算法通过考虑最佳子路径来得到最佳路径，使用邻接矩阵来储存边。

三、最小生成树算法

1. Prim算法

   • 在加权连通图中搜索最小生成树。
   • 从任意一个顶点开始，逐步扩展生成树，每次选择权值最小的连接新顶点和生成树中顶点的边。

2. Kruskal算法

   • 另一种求加权连通图的最小生成树的算法。
   • 基于贪心策略，首先将所有边按权值从小到大排序，然后依次选择边，如果选择的边不会形成环，则将其加入生成树中。

四、图匹配算法

• 匈牙利算法

  • 在多项式时间内求解任务分配问题的组合优化算法。
  • 用于求解指派问题（assignment problem），算法时间复杂度为O(n^3)。
  • 适用于二分图的最大匹配问题。

五、网络流算法

• Ford-Fulkerson算法

  • 用于计算流网络中的最大流量。
  • 流网络是一个有向图，其中每条边都有一个非负容量。
  • 算法通过寻找增广路径来不断更新流量，直到无法再找到增广路径为止。

这些算法在图论和网络分析中有着广泛的应用，包括网络路由、社交媒体分析、推荐系统等领域。根据具体问题的需求和图的结构特性，可以选择合适的算法来解决问题。