当前位置: 首页 > article >正文

【数据结构】非线性数据结构——图

1. 图的定义

图(Graph) 是一种由一组 顶点(Vertex) 和一组 边(Edge) 构成的数据结构。图通常用来表示 实体(顶点) 之间的关系(边)。例如,社交网络中的用户和朋友关系、道路网络中的城市和道路、计算机网络中的设备和连接等,都是可以通过图来建模的。

2. 图的基本概念

在这里插入图片描述

3. 图的表示方式

图可以通过以下几种方式来表示:

1)邻接矩阵(Adjacency Matrix):

邻接矩阵是一个二维数组 A[i][j],用于表示顶点 𝑖 和顶点 𝑗 之间是否存在边。

优点:查找是否存在边的时间复杂度为 O(1)。

缺点:对于稀疏图(边远少于顶点数的图),会浪费大量空间。

2)邻接表(Adjacency List):

邻接表是为每个顶点维护一个链表或列表,列表中保存与该顶点相连的所有顶点。每个顶点都有一个链表,链表中的元素是与该顶点直接相连的其他顶点。

优点:节省空间,特别适用于稀疏图。对于每个顶点的所有邻居,可以快速访问。

缺点:查找是否存在一条特定边的时间复杂度是 O(k),其中 k 是该顶点的邻居数量。

3)边列表(Edge List):

边列表是一种简单的图表示方法,其中包含所有的边,每条边由一对顶点组成。通常用于表示无向图或有向图的边集合。

优点:简单易懂,适用于边的操作。

缺点:不适合高效地进行邻接查询。

3. 图的基本术语

在这里插入图片描述

4. 图的遍历

图的遍历是图论中的基本操作,主要有两种方式:

1)深度优先搜索(DFS, Depth-First Search):

DFS 是一种从起始顶点开始,沿着一个分支一路向下走,直到没有新的顶点可以访问,然后回溯到上一个分支,继续访问其他未访问的顶点,直到所有顶点都被访问过。递归 或 栈 可用于实现 DFS。

2) 广度优先搜索(BFS, Breadth-First Search):

BFS 是一种从起始顶点开始,首先访问所有相邻的顶点,然后再访问这些顶点的邻居,依此类推,直到所有顶点都被访问过。队列 是 BFS 的常用实现工具。

5. 图的应用场景

图在许多领域都有广泛的应用,包括但不限于:

  • 社交网络:在社交网络中,用户是图中的顶点,用户之间的好友关系是图中的边。图可以帮助发现群体、推荐朋友、分析社交影响等。

  • 计算机网络:计算机网络中的设备(如路由器、交换机)可以视为图中的顶点,设备之间的连接为图中的边。路由算法、网络拓扑分析等问题都可以通过图来建模。

  • 任务调度:任务调度中,任务可以视为顶点,任务之间的依赖关系可以表示为边。通过图的遍历和排序算法(如拓扑排序),可以有效地安排任务的执行顺序。

  • 网页链接分析:网页之间的链接关系是有向图。搜索引擎通过分析网页的链接结构来评估网页的排名(如 PageRank 算法)。


http://www.kler.cn/a/459997.html

相关文章:

  • OkHttp接口自动化测试
  • df.replace({‘b‘: r‘\s*(\.)\s*‘}, {‘b‘: r‘\1ty‘}, regex=True)
  • 设计模式の状态策略责任链模式
  • 【网络安全 | 漏洞挖掘】硬编码凭据泄露实现支付系统账户接管
  • 玉米中的元基因调控网络突出了功能上相关的调控相互作用。/biosample_parser.py
  • kafka怎么保证顺序消费?
  • Oracle复合索引规则指南
  • 大模型Weekly 03|OpenAI o3发布;DeepSeek-V3上线即开源!
  • 【Linux知识】exec命令行详解
  • 关于 覆铜与导线之间间距较小需要增加间距 的解决方法
  • MATLAB语言的计算机基础
  • 自学记录HarmonyOS Next Image API 13:图像处理与传输的开发实践
  • 大数据研究方向有哪些创新点
  • Go中的逃逸分析
  • JS async await fetch 捕获后端500错误详细信息
  • Visual Studio 中增加的AI功能
  • 【文献精读笔记】Explainability for Large Language Models: A Survey (大语言模型的可解释性综述)(一)
  • JS中Symbol (符号)数据类型详解和应用场景
  • Gemma2 2B 模型的model.safetensors.index.json文件解析
  • win版ffmpeg的安装和操作
  • 基于问卷调查数据的多元统计数据分析与预测(因子分析、对应分析与逻辑回归)
  • Docker搭建RocketMQ
  • 基于源码剖析:深度解读JVM底层运行机制
  • CPT203 Software Engineering 软件工程 Pt.2 敏捷方法和需求工程(中英双语)
  • Unity3D仿星露谷物语开发11之添加Scenary Fader
  • 离线语音识别+青云客语音机器人(幼儿园级别教程)