DSA之图(4):图的应用

这篇具有很好参考价值的文章主要介绍了DSA之图(4):图的应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

0 图的应用

DSA之图(4):图的应用,DSA,深度优先,图论,算法

1 生成树

生成树:所有顶点均由边连接在一起,但不存在回路的图。
也就是两个条件,顶点条件和边数条件,顶点都要保持连通,边数达到最少,没有回路。
DSA之图(4):图的应用,DSA,深度优先,图论,算法
如右边的图,随便再加一条边就有回路了。DSA之图(4):图的应用,DSA,深度优先,图论,算法
所有生成树都具有以下的共同特点:

  • 生成树的顶点个数与图的顶点个数相同;
  • 生成树是图的极小连通子图,去掉一条边则非连通;
  • 一个有 n n n个顶点的连通图的生成树有 n − 1 n-1 n1条边;
  • 生成树中任意两个顶点间的路径是唯一的;
  • 含有 n n n个顶点 n − 1 n-1 n1条边的图不一定是生成树,如下图所示
    DSA之图(4):图的应用,DSA,深度优先,图论,算法
    因为生成树是连通的,每个顶点都要用边相连,上图是不连通的,有两个连通分量。

1.1 无向图的生成树

生成树要包含所有顶点,那么对图进行遍历,把走过的边全部加入到图当中。
遍历则采用DFS与BFS都可以。DSA之图(4):图的应用,DSA,深度优先,图论,算法

用DFS生成的生成树就是DFS生成树。
DSA之图(4):图的应用,DSA,深度优先,图论,算法
用BFS生成的生成树就是BFS生成树。
DSA之图(4):图的应用,DSA,深度优先,图论,算法

综上
DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.2 最小生成树

DSA之图(4):图的应用,DSA,深度优先,图论,算法
最小生成树:给定一无向网络在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树。
最小生成树可能是不唯一的。

DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.2.1 构造最小生成树

构造最小生成树的算法很多,其中多数算法都利用了MST(Minimum Spanning Tree)的性质。

MST性质
其实就是贪心算法,不断去找权值最小的边。
N = ( V , E ) N=(V, E) N=(V,E)以目是一个连通网, U U U是顶点集 V V V的一个非空子集。若边 ( u , v ) (u, v) (u,v)是一条具有最小权值的边,其中 u ∈ U , v ∈ V − U u∈U,v∈V-U uU,vVU则必存在一棵包含边 ( u , v ) (u,v) (u,v)的最小生成树。

举例

DSA之图(4):图的应用,DSA,深度优先,图论,算法
现在 U = { v 1 } U=\{v_1\} U={v1},所以 V − U = { v 2 , v 3 , v 4 , v 5 , v 6 } V-U=\{v_2,v_3,v_4,v_5,v_6\} VU={v2,v3,v4,v5,v6},所以 u ∈ U , v ∈ V − U u∈U,v∈V-U uU,vVU当中,其中从 v 1 v_1 v1 v 3 v_3 v3是最小的,权值为1,存在这个权值最小的边,这条边一定会包含在某个最下生成树当中。
DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.2.2 Prim算法构造最小生成树

算法思想:
DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.2.3 Kruskal算法构造最小生成树

相比Prim算法更加贪心,直截了当贪心,前提不成环。这次开始就把所有顶点都加入到最小生成树上面去。不过并不包括边,这时边的集合都是空集,没包含边,彼此之间不连通。
DSA之图(4):图的应用,DSA,深度优先,图论,算法
然后直接在边集合当中选权值最小的边,直接加入。DSA之图(4):图的应用,DSA,深度优先,图论,算法
以此类推,选到所有顶点都连通为止(前提不能形成回路)(n个点,n-1条边)。DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.2.4 两种算法的比较

DSA之图(4):图的应用,DSA,深度优先,图论,算法
Prim是选择点加入的,而Kruskal是选择边的。选择边的时候和顶点数是没关系的。

1.3 最短路径

1.3.1 两点间最短路径

从起点走向终点,并非要n个节点都包括,也并非要n-1条边。DSA之图(4):图的应用,DSA,深度优先,图论,算法
直到找到路径长度最短的一条路径。
这种最短路径也称为单源的最短路径,采用Dijkstra算法。

1.3.2 某源点到其他各点最短路径

DSA之图(4):图的应用,DSA,深度优先,图论,算法
所有顶点的最短路径,统一使用Floyd弗洛伊德算法。

1.3.3 Dijkstra

其时间复杂度为 O ( n 3 ) O(n^3) O(n3)
DSA之图(4):图的应用,DSA,深度优先,图论,算法
按照路径长度递增次序产生最短路径,启发式贪心算法。
DSA之图(4):图的应用,DSA,深度优先,图论,算法
DSA之图(4):图的应用,DSA,深度优先,图论,算法
启发式算法,先找最短的,后面再及时更新,具体过程可以看王老师的视频。

1.3.4 Floyd

其时间复杂度为 O ( n 3 ) O(n^3) O(n3)

算法思想:

  • 逐个顶点试探
  • 从少,到的所有可能存在的路径中
  • 选出一条长度最短的路径

DSA之图(4):图的应用,DSA,深度优先,图论,算法
求最短路径的步骤:
初始时设置一个 n n n阶方阵,令其对角线元素(到自身的路径)为0,若存在弧 < v i , v j > <v_i, v_j> <vi,vj>,则对应元素为权值;否则为 ∞ ∞
逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短,则修改之;否则,维持原值。所有顶点试探完毕,算法结束。

DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.4 拓扑排序

1.4.1 有向无环图DAG

DSA之图(4):图的应用,DSA,深度优先,图论,算法
DSA之图(4):图的应用,DSA,深度优先,图论,算法
AOV网以顶点表示活动;AOE网用弧表示活动(子工程)。
AOV网用来解决拓扑排序,AOE网用来解决关键路径问题。

拓扑排序的一个小例子:
DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.4.2 AOV网

DSA之图(4):图的应用,DSA,深度优先,图论,算法
问题:如何判断AOV网中是否存在回路?

DSA之图(4):图的应用,DSA,深度优先,图论,算法
所有顶点都能加入拓扑排序的话,就一定没有网。

拓扑排序。
将网变成一个线性序列的过程就是拓扑排序。
DSA之图(4):图的应用,DSA,深度优先,图论,算法
拓扑排序的步骤:

  1. 首先构建好AOV网

DSA之图(4):图的应用,DSA,深度优先,图论,算法

  1. 在有向图中选一个没有前驱的顶点且输出(例如C1和C9)
  2. 假设选了C1,在有向图当中删除该顶点和所有以它为尾的弧(C1发出的弧)(即C1与C2,C4,C12的弧)
  3. 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止DSA之图(4):图的应用,DSA,深度优先,图论,算法

1.5 关键路径

制定计划,查找关键路径。
关键路径就是从源点到汇点路径长度(权值之和)最长(大)的路径。

DSA之图(4):图的应用,DSA,深度优先,图论,算法
按照任务需求,构建有权图。
DSA之图(4):图的应用,DSA,深度优先,图论,算法
举例:
DSA之图(4):图的应用,DSA,深度优先,图论,算法

对于上方AOE网,我们关心两个问题:

  1. 完成整项女程至少需要多少时间?
  2. 哪些活动是影响工程进度的关键?

以上答为关键路径与路径长度。

1.5.1 求解关键路径

四个有用的量:
DSA之图(4):图的应用,DSA,深度优先,图论,算法
DSA之图(4):图的应用,DSA,深度优先,图论,算法
DSA之图(4):图的应用,DSA,深度优先,图论,算法
求关键路径的步骤:
DSA之图(4):图的应用,DSA,深度优先,图论,算法
DSA之图(4):图的应用,DSA,深度优先,图论,算法
DSA之图(4):图的应用,DSA,深度优先,图论,算法文章来源地址https://www.toymoban.com/news/detail-611500.html

到了这里,关于DSA之图(4):图的应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图论算法】深度优先搜索的应用

    深度优先搜索 (depth-first search)是对先序遍历(preorder traversal)的推广。我们从某个顶点 v 开始处理 v,然后递归地遍历所有邻接到 v 的顶点。 对一棵树的所有顶点的访问需 O(|E|) 时间。对任意图进行该过程时则需要考虑避免圈的出现。为此,当访问一个顶点 v 的时候,由于当时已

    2024年02月08日
    浏览(60)
  • 【图论】图的存储--链式前向星存图法以及深度优先遍历图

    无向图 - 就是一种特殊的有向图 - 只用考虑有向图的存储即可 邻接矩阵 邻接表 邻接表 存储结构: (为每一个点开了一个单链表,存储这个点可以到达哪个点) 1 : 3-4-null 2 : 1-4-null 3 : 4-null 4 : null 插入一条新的边 比如要插一条边: 2-3 先找到 2 对应的 单链表 然后将 3 插入到单链表

    2024年04月14日
    浏览(46)
  • acwing算法提高之图论--最小生成树的扩展应用

    本专题用来记录使用最小生成树算法(prim或kruskal)解决的扩展题目。 题目1 :1146新的开始 C++代码如下, 题目2 :1145北极通讯网络 C++代码如下, 题目3 :346走廊泼水节 C++代码如下, 题目4 :1148秘密的牛奶运输 C++代码如下,

    2024年04月16日
    浏览(38)
  • acwing算法提高之图论--最小生成树的典型应用

    本专题用来记录使用prim算法或kruskal算法求解的题目。 题目1 :1140最短网络 C++代码如下, 题目2 :1141局域网 C++代码如下, 题目3 :1142繁忙的都市 C++代码如下, 题目4 :1143联络员 C++代码如下, 题目5 :1144连接格点 C++代码如下,

    2024年04月27日
    浏览(41)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(49)
  • 【数据结构与算法】图的深度优先和广度优先遍历

    😊😊作者简介😊😊 : 大家好,我是南瓜籽,一个在校大二学生,我将会持续分享Java相关知识。 🎉🎉个人主页🎉🎉 : 南瓜籽的主页 ✨✨座右铭✨✨ : 坚持到底,决不放弃,是成功的保证,只要你不放弃,你就有机会,只要放弃的人,他肯定是不会成功的人。 图是一

    2024年02月02日
    浏览(58)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(63)
  • 数据结构学习笔记——图的遍历算法(深度优先搜索和广度优先搜索)

    图的遍历指从图中某一顶点出发(任意一个顶点都可以作为访问的起始顶点),按照某种遍历方法,对图中所有的顶点访问一次且只访问一次。图与树不一样,其中一个顶点可能与多个顶点相连,所以需记录已访问过的顶点,当访问一个顶点后,考虑如何选取下一个要访问的

    2024年02月05日
    浏览(53)
  • 彻底搞懂图的深度优先算法(Debug+图解+JavaDOC)

    深度优先算法 从 算法的思想 , 算法步骤 , 代码实现与分析 , 最后\\\"debug+图解\\\"展示 展开 会有一定的 图示 ,以便于更好的理解( 博主的自我思考,如有错误,欢迎指正 ) 需要源码与相关图解请评论区留言 博客空间 https://blog.csdn.net/JOElib?spm=1011.2266.3001.5343 文件压缩与解压 https://blog

    2023年04月08日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包