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

数据结构与算法--图的应用

文章目录

      • 回顾
      • 提要
      • 连通图
      • 生成树
      • 最小生成树
      • 构造最小生成树的算法
        • 普里姆(Prim)算法
        • 克鲁斯卡尔(Kruskal)算法
      • 最短路径
      • 狄杰斯特拉 (Dijkstra) 算法
      • 当前最短路径的更新
      • 拓扑排序
      • 拓扑排序方法
      • 拓扑排序示例
      • 总结

回顾

图的遍历方法:

  • 深度优先遍历 (DFS):从任意顶点开始,访问其未访问过的邻接点,直至全部访问完毕。
  • 广度优先遍历 (BFS):从任意顶点开始,访问其所有未访问过的邻接点,然后是下一层的邻接点,直至所有顶点被访问。

提要

  • 最小生成树的概念。
  • 最小生成树的构造算法:
    • 普里姆 (Prim) 算法
    • 克鲁斯卡尔 (Kruskal) 算法
  • 单源点最短路径。
  • 拓扑排序。

连通图

连通图:图中任意两个顶点都是连通的。在连通图中,从任意顶点出发进行深度优先遍历或广度优先遍历,都可以访问图中所有其他顶点。在这里插入图片描述
在这里插入图片描述

生成树

生成树:包含连通图全部顶点的极小连通子图,即以最少的边连接连通图中所有的顶点。
在这里插入图片描述
在这里插入图片描述

最小生成树

最小生成树:带权连通图的所有生成树中权值之和最小的生成树。在实际问题中,如管道铺设问题,可以应用最小生成树来最小化成本。
最小生成树:带权连通图的所有生成树中权值之和最小的生成树。
在实际问题中的应用:管道的铺设问题。
n 个小区只需铺设 n-1 条管线就能连通,各条管线的投资成本不同,如何使得总的投资成本最低?最小生成树。
在这里插入图片描述

构造最小生成树的算法

  • 普里姆 (Prim) 算法:从任一顶点开始,逐步扩展最小生成树,每次添加权值最小的边。
  • 克鲁斯卡尔 (Kruskal) 算法:按边权值从小到大的顺序选择边,形成最小生成树,不形成环。
普里姆(Prim)算法

在这里插入图片描述
示例:在这里插入图片描述
求解过程:

  • 初始化U={v}。v到其他顶点的所有边为候选边;
  • 重复以下步骤n-1次,使得其他n-1个顶点被加入到U中:
    • 从候选边中挑选权值最小的边输出,设该边在V-U中的顶点是k,将k加入U中;
    • 考察当前V-U中的所有顶点j,修改候选边:若 (k, j) 的权值小于原来和顶点 j 关联的候选边,则用 (k, j) 取代后者作为候选边。
克鲁斯卡尔(Kruskal)算法

假设N=(V,E)是连通网(带权的图),令最小生成树的初始状态为包含全部n个顶点,但没有边的非连通图T=(V,{ }),图中每个顶点自成一个连通分量
在E中选择权值最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条权值最小的边。依此类推,直至所有顶点都在同一连通分量上为止。

示例:在这里插入图片描述

求解过程:

  • T的初始状态:包含n个顶点、不包含边的森林:T=(V,Ø );
  • 按权值递增的顺序选择E中的n-1条安全边(u,v),并加入T;
  • 安全边指两个顶点分别是森林T里两棵树中的顶点的边。安全边的加入,不会形成环。加入安全边,可将森林中的两棵树连接成一棵更大的树。

最短路径

最短路径:带权图中从源点到终点的所有路径中,所经过边的权值之和最小的路径。
图的最短路径:
单源点最短路径:从一个顶点到其余各顶点的最短路径;
每对顶点间的最短路径。

狄杰斯特拉 (Dijkstra) 算法

求解单源点最短路径的算法,通过不断更新顶点间的最短路径来实现。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

当前最短路径的更新

在这里插入图片描述
在这里插入图片描述

拓扑排序

拓扑排序:在一个有向图中找一个满足所有有向边的方向的顶点序列的过程。
在这里插入图片描述

拓扑排序方法

  1. 从有向图中选择一个没有前驱(入度为0)的顶点并输出。
  2. 从图中删去该顶点及发出的全部有向边。
  3. 重复以上步骤,直到所有顶点都被输出。

拓扑排序示例

计算机专业课程学习顺序的拓扑排序,展示了如何根据先修课程的要求进行排序。
在这里插入图片描述
课程之间的先后关系可用有向图表示:在这里插入图片描述
拓扑序列:C2-C7-C1-C3-C4-C5-C6 或:C1-C2-C3-C4-C5-C7-C6 等
注意:拓扑序列不一定唯一。

总结

  • 普里姆 (Prim) 算法和克鲁斯卡尔 (Kruskal) 算法构造最小生成树的方法。
  • 狄杰斯特拉 (Dijkstra) 算法求解单源点最短路径。
  • 拓扑排序的应用。
http://www.lryc.cn/news/424789.html

相关文章:

  • 【leetcode图文详解】特殊数组II : 空间换时间的“记忆化”,越多越好吗?
  • 离线安装prometheus与Grafana实现可视化监控
  • 【Python学习-UI界面】PyQt5 小部件7-QSpinBox 计数器
  • [二次元]个人主页搭建
  • Spring Data JPA 自动创建时间的相关注解和用法
  • Java基础之隐式类型转换
  • 【数据结构与算法 | 图篇】Dijkstra算法(单源最短路径算法)
  • windows c转linux c要做的事情。
  • 【高等代数笔记】002.高等代数研究对象(二)
  • ubuntu服务器部署的mysql本地连不上的问题
  • python redis安装
  • YJ0043定制版抖音电商卷抢购系统带回收商城抖音电商优惠卷投资理财系统
  • 如何选择图片和视频
  • html+css网页制作 电商华为商城首页 ui还原度100%
  • EDAS(企业级应用服务)
  • 简单工厂,工厂方法 和 抽象工厂
  • python 压力测试脚本
  • 【Linux】多线程7——线程池
  • Linux Shell实例
  • Linux~MySQL数据库具体操作
  • Unity WebGL平台Hybrid Generate All报错undefined symbol sendfile
  • Java高级Day28-多线程
  • 0003 保险的会计要素及其计量属性
  • Swift版本控制的艺术:掌握代码演化的魔杖
  • 学习实战:生活垃圾自动识别与分类系统的实现
  • Swift模块化构建:解锁代码重用的金钥匙
  • 【计算机网络】CIDR无分类编址知识学习
  • JavaScript 详解
  • 运维实践01-安装OpenJDK
  • Windows下,C# 通过FastDDS高效通信