图论基础知识

embedded/2024/11/26 5:34:42/

图论基础知识

什么是图论

图论(Graph Theory)是研究图(Graph)的数学分支,主要研究点和边之间的关系。在计算机科学、网络设计、生物信息学等领域中,图论有广泛的应用。

图的基本定义

  1. 图 (Graph)
    一个图 ( G = (V, E) ) 由以下两部分组成:

    • ( V ):顶点集合(Vertices),表示对象。
    • ( E ):边集合(Edges),表示顶点之间的关系。
  2. 边的类型

    • 无向边:顶点之间的关系是对称的。
    • 有向边:顶点之间的关系有方向性(例如箭头 ( u \rightarrow v ))。
    • 加权边:每条边附带一个权值,表示强度或成本。
  3. 图的分类

    • 无向图:所有边都是无方向的。
    • 有向图:所有边都有方向。
    • 简单图:没有平行边和自环的图。
    • 完全图:任意两个顶点之间都有一条边。
    • 稀疏图:边的数量远小于顶点对的数量。
    • 稠密图:边的数量接近顶点对的数量。

图的基本术语

  1. 度 (Degree)

    • 顶点的度是与其相连的边的数目。
    • 无向图中,顶点的度为其连接的边数。
    • 有向图中:
      • 入度(In-degree):指向该顶点的边数。
      • 出度(Out-degree):从该顶点出发的边数。
  2. 路径 (Path)

    • 一系列顶点的序列,其中每一对相邻顶点之间都有边。
    • 简单路径:路径中没有重复的顶点。
  3. 回路 (Cycle)

    • 从一个顶点出发,通过若干边返回该顶点的路径。
    • 无重复顶点(除起点和终点)。
  4. 连通性 (Connectivity)

    • 无向图:如果任意两个顶点之间都有路径,则为连通图。
    • 有向图:如果任意两个顶点之间都有双向路径,则为强连通图。
  5. 子图 (Subgraph)

    • 从图中选取一部分顶点和边构成的图。

图的表示方式

  1. 邻接矩阵 (Adjacency Matrix)
    用一个 ( n * n ) 的矩阵表示图,其中 ( A[i][j] ) 表示顶点 ( i ) 和 ( j ) 之间是否有边。
    优点:快速查询边的存在性。
    缺点:空间复杂度高,特别是对稀疏图。

    示例:

    0 1 0
    1 0 1
    0 1 0
    
  2. 邻接表 (Adjacency List)
    用一个列表表示每个顶点的邻接顶点。
    优点:空间高效,适合稀疏图。
    缺点:查询特定边的存在性较慢。

    示例:

    0: [1]
    1: [0, 2]
    2: [1]
    

常见算法

  1. 图遍历

    • 深度优先搜索(DFS):递归地访问每个未访问的相邻顶点。
    • 广度优先搜索(BFS):按层次逐层访问顶点。
  2. 最短路径算法

    • Dijkstra算法:适用于加权图,不能处理负权边。
    • Bellman-Ford算法:适用于处理负权边。
    • Floyd-Warshall算法:计算所有点对之间的最短路径。
  3. 最小生成树

    • Prim算法:从一个顶点开始,逐步构建生成树。
    • Kruskal算法:按权值排序边,然后逐步添加到生成树中。
  4. 拓扑排序

    • 对有向无环图(DAG)进行排序,使得每条边的起点在终点之前。
  5. 连通性检测

    • Tarjan算法:用于检测强连通分量。
    • 并查集(Union-Find):检测无向图的连通性。

应用场景

  1. 网络结构:如社交网络分析、通信网络建模。
  2. 路径规划:如导航系统中的最短路径计算。
  3. 资源分配:如任务调度、流水线作业优化。
  4. 数据结构设计:如依赖关系分析、图数据库。

http://www.ppmy.cn/embedded/140552.html

相关文章

dify部署和应用 | docker基础使用

使用Docker运行 cd dify cd docker cp .env.example .env docker compose up -d这里docker一定要更新,旧版的没有docker compose这个命令,会失败。如果在ubuntu上面docker拉镜像一直失败,可以使用win系统的docker下载导出,然后再…

【Zookeeper】二、主从应用(master-worker架构)

以一张具有代表性的架构风格展开本篇论述 一般在这种架构中,主节点所负责的工作主要有 跟踪从节点状态分配任务到从节点,并跟踪任务的有效性(任务是否正常执行完成) 此时,我们需要关注三个问题 主节点崩溃 如果主节…

Firewall防火墙配置

文章目录 一、firewalld简介二、firewalld特性三、firewalld相关文件及目录四、firewalld配置五、firewalld配置实例一、firewalld简介 firewalld 提供了支持网络/防火墙区域(zone)定义网络链接以及接口安全等级的动态防火墙管理工具。它支持 ipv4, ipv6 防火墙设置以及以太网…

CircuitBreaker机制详解:Elasticsearch中的资源管理

CircuitBreaker机制详解:Elasticsearch中的资源管理 在现代软件架构中,熔断器(CircuitBreaker)是一种重要的模式,用于防止系统过载并保护系统稳定性。在Elasticsearch中,熔断器机制尤其关键,因为它们帮助管理资源使用,防止节点因资源耗尽而崩溃。本文将深入探讨Elasti…

废品买卖回收管理系统|Java|SSM|Vue| 前后端分离

【重要①】前后端源码万字文档部署文档 【重要②】正版源码有问题包售后 【包含内容】 【一】项目提供非常完整的源码注释 【二】相关技术栈文档 【三】源码讲解视频 【其它服务】 【一】可以提供远程部署安装,包扩环境 【二】提供软件相关的安装包 【三】如…

输入三个整数x,y,z,请把这三个数由小到大输出。-多语言实现

目录 C 语言实现 Python 实现 Java 实现 Js 实现 题目:输入三个整数x,y,z,请把这三个数由小到大输出。 程序分析:我们想办法把最小的数放到x上,先将x与y进行比较,如果x>y则将x与y的值进行交换,然后…

go语言range的高级用法-使用range来接收通道里面的数据

在 Go 语言中,可以使用 for ... range 循环来遍历通道(channel)。for ... range 循环会一直从通道中接收值,直到通道关闭并且所有值都被接收完毕。 使用 for ... range 遍历通道 示例代码 下面是一个使用 for ... range 遍历通…

如何调试 chrome 崩溃日志(MAC)

引言 在使用 Chrome 浏览器的过程中,偶尔会遇到浏览器崩溃的情况。为了找出崩溃的原因并修复问题,我们需要对崩溃后的 .dmp 文件进行详细分析。本文将详细介绍如何从用户的系统中获取崩溃日志文件,使用 minidump_stackwalk 查看浏览器版本信…