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

图（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)

    (

    u

    ,

    v

    ) ，表示从顶点

    u u

    u 指向顶点

    v v

    v 。

  • 示例：网页链接（A 页面链接到 B 页面）。

• 无向图（Undirected Graph） ：

  • 边没有方向，表示为

    u , v {u,v}

    u

    ,

    v ，表示顶点

    u u

    u 和顶点

    v v

    v 之间的双向关系。

  • 示例：社交网络（A 和 B 是朋友）。

按边是否有权重

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

按图中是否有环

• 有环图（Cyclic Graph） ：

  • 图中存在至少一个环（从一个顶点出发，经过若干边后回到自身）。

  • 示例：

    A → B → C → A A → B → C → A

    A

    →

    B

    →

    C

    →

    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 算法 ：用于查找有向图的强连通分量。

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