图论入门【数据结构基础】：什么是图？如何表示图？

图（Graph） 是一种非线性数据结构，用于表示对象之间的关系。图由 顶点（Vertex） 和 边（Edge） 组成，其中顶点表示对象，边表示对象之间的关系。图广泛应用于计算机科学、数学、物理、生物、社交网络等领域。

1. 图的基本概念

• 顶点（Vertex）：也称为节点（Node），表示图中的对象。例如，在社交网络中，顶点可以表示人。
• 边（Edge）：表示顶点之间的关系。例如，在社交网络中，边可以表示两个人是朋友。
• 有向图（Directed Graph）：边有方向，表示从一个顶点指向另一个顶点。例如，A → B 表示从 A 到 B 的关系。
• 无向图（Undirected Graph）：边没有方向，表示两个顶点之间的双向关系。例如，A — B 表示 A 和 B 是相互关联的。
• 权重（Weight）：边可以带有权重，表示关系的强度或成本。例如，在地图中，边的权重可以表示两个城市之间的距离。

2. 图的分类

按边是否有方向

• 有向图（Directed Graph）：
  • 边有方向，表示为 $(u,v)$，表示从顶点 $u$ 指向顶点 $v$。
  • 示例：网页链接（A 页面链接到 B 页面）。
• 无向图（Undirected Graph）：
  • 边没有方向，表示为 $u,v$，表示顶点 $u$ 和顶点 $v$ 之间的双向关系。
  • 示例：社交网络（A 和 B 是朋友）。

按边是否有权重

• 带权图（Weighted Graph）：
  • 边带有权重，表示关系的强度或成本。
  • 示例：地图（边的权重表示两个城市之间的距离）。
• 无权图（Unweighted Graph）：
  • 边没有权重，只表示顶点之间是否存在关系。
  • 示例：社交网络（只表示两个人是否是朋友）。

按图中是否有环

• 有环图（Cyclic Graph）：
  • 图中存在至少一个环（从一个顶点出发，经过若干边后回到自身）。
  • 示例：$A\to B\to C\to A$。
• 无环图（Acyclic Graph）：
  • 图中不存在任何环。
  • 示例：树（Tree） 是一种特殊的无环图。

按图的连通性

• 连通图（Connected Graph）：
  • 无向图中，任意两个顶点之间都存在路径。
  • 示例：完全连通的社交网络。
• 非连通图（Disconnected Graph）：
  • 无向图中，存在至少两个顶点之间没有路径。
  • 示例：孤立的社交网络群体。
• 强连通图（Strongly Connected Graph）：
  • 有向图中，任意两个顶点之间都存在双向路径。
  • 示例：完全连通的网页链接图。

3. 图的表示方法

图可以通过多种方式表示，常见的有：

• 邻接矩阵（Adjacency Matrix）：
  • 使用二维数组表示顶点之间的连接关系。
  • 适合稠密图。
• 邻接表（Adjacency List）：
  • 使用数组或链表存储每个顶点的邻接顶点。
  • 适合稀疏图。
• 边列表（Edge List）：
  • 直接存储所有边的列表。
  • 适合某些特定算法（如 Kruskal 算法）。

4. 图的算法

图论中有许多经典算法，例如：

• 遍历算法：
  • 深度优先搜索（DFS）：用于遍历或搜索图。
  • 广度优先搜索（BFS）：用于最短路径问题。
• 最短路径算法：
  • Dijkstra 算法：用于带权图的最短路径。
  • Floyd-Warshall 算法：用于所有顶点对之间的最短路径。
• 最小生成树算法：
  • Kruskal 算法：基于边列表的最小生成树。
  • Prim 算法：基于顶点的最小生成树。
• 拓扑排序：
  • 用于 有向无环图（DAG） 的排序。
• 强连通分量：
  • Kosaraju 算法：用于查找有向图的强连通分量。

我将在接下来几篇文章中和大家分享相关的题目。欢迎大家点赞收藏，持续关注！