欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 建筑 > 图论入门【数据结构基础】:什么是图?如何表示图?

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

2025/3/16 14:09:56 来源:https://blog.csdn.net/Vitalia/article/details/146254353  浏览:    关键词:图论入门【数据结构基础】:什么是图?如何表示图?

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

文章目录

  • 1. 图的基本概念
  • 2. 图的分类
    • 按边是否有方向
    • 按边是否有权重
    • 按图中是否有环
    • 按图的连通性
  • 3. 图的表示方法
  • 4. 图的算法

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 ABCA
  • 无环图(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 算法:用于查找有向图的强连通分量。

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词