数据结构-图的应用算法

2023-10-27

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


一、最小生成树

最小生成树两种算法

1.1 Prim算法

算法步骤:
步骤一:树T初始状态为空;
步骤二:从图中任意选取一个点加入T;
步骤三:从图中找出能与T形成树的所有边,将代价最小的边加入T,形成新的树T;
步骤四:检查T中边的条数;
步骤五:如果条数小于n-1,返回步骤三,否则程序结束,T为最小代价生成树。

示例:
参考上述连接

1.2 Kruskal算法

算法步骤:
(1)将图G看做一个森林,每个顶点为一棵独立的树
(2)将所有的边加入集合S,即一开始S = E
(3)从S中拿出一条最短的边(u,v),如果(u,v)不在同一棵树内,则连接u,v合并这两棵树,同时将(u,v)加入生成树的边集E’
(4)重复(3)直到所有点属于同一棵树,边集E’就是一棵最小生成树

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

二、最短路径

2.1 Dijkstra算法

算法步骤:

示例:

2.2 Floyd算法

算法步骤:

示例:

三、有向无环图描述表达式

有向无环图描述表达式

算法步骤:
1)把各个操作数不重复地排成一排

2)标出各个运算符的生效顺序(先后顺序优点出入无所谓,比如先算左边括号或者先算右边括号,当然是同级的情况)

3)按顺序加入运算符,不同的运算级别层次不同,过程中如果已经存在某部分,则直接用

4)最后生成的图就是有向无环图

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

四、拓扑排序

参考
算法步骤:
① 输入AOV网络。令 n 为顶点个数。

② 在AOV网络中选一个入度为0的结点, 并输出之;(关键步)

③ 从图中删去该顶点, 同时删去所有它发出的有向 边;

④ 重复以上 ②、③步, 直到下面的情况之一出现: (1)全部顶点均已输出,拓扑有序序列形成,拓 扑排序完成; (2)图中还有未输出的顶点, 但已没有入度为0的 结点(说明网络中必存在有向环)。

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

五、关键路径

关键路径参考

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构-图的应用算法 的相关文章

随机推荐

  • vue + springboot poi 实现excel模板导出 完整代码

    有导入导出功能的时候 避免用户导入数据有误 提供了excel模板下载 用户直接在系统导出的excel模板中填写数据 再导入该excel 例如下图excel 提供前后台所有导出代码 3 代码 3 1 前台 1 按钮
  • Python 循环所有文件夹(含子文件夹),读取指定格式文件,另存为其他格式文件...

    循环所有文件夹 含子文件夹 读取指定格式文件 另存为其他格式文件 与原有文件在同一级目录 并删除原有文件 usr bin python coding utf 8 遍历所有文件夹 将指定格式文件 批量另存为其他文件 或其他格式 import
  • 【OpenCV学习笔记】【函数学习】十四(cvSeq的用法说明(功能很多,按照需求使用))

    OpenCV CvSeq 结构 一直困惑于CvSeq到底是个什么样的东西 因为曾经拿到别人写的一个函数库 其返回值是一个CvSeq指针 我的任务是遍历所有的Sequence 然后删除其中不符合要求的Sequence 由于没有文档 我当时并不
  • 优雅的获取文件及文件夹

    string filepath D WEB var rel Directory GetFiles filepath SearchOption AllDirectories ToList foreach var file in rel Con
  • Java垃圾回收机制

    Java垃圾回收机制 Java垃圾回收机制是指一种自动化的内存管理方式 Java程序员无需手动管理内存 而是由JVM Java虚拟机 自动进行垃圾回收 下面是简要的Java垃圾回收机制 垃圾收集器 JVM中垃圾回收器 Garbage Col
  • 外包征途-甲方、乙方、外包

    甲方 乙方 外包 在IT这行 我们经常都会听到这几个词 那这几个词到底是什么意思 我们先看看官方的解释 甲方 一般是指提出目标的一方 在合同拟定过程中主要是提出要实现什么目标 是合同的主导方 甲方是合同中双方平等主体的代称 也是为了方便在下
  • Meta算力争夺演变成团队动荡!LLaMA、LLaMA2、OPT团队成员多位离职

    据TheInformation报道 原参与Llama项目的团队成员有多位已经辞职 原因是Meta内部的OPT研究团队与Llama团队之间发生了一场关于计算资源的内部斗争 看来不管是谷歌 微软 OpenAI还是Meta 人才流失都是一个避不开
  • 【满分】【华为OD机试真题2023 JS】组装新的数组

    华为OD机试真题 2023年度机试题库全覆盖 刷题指南点这里 组装新的数组 知识点回溯数组 时间限制 1s 空间限制 256MB 限定语言 不限 题目描述 给你一个整数M和数组N N中的元素为连续整数 要求根据N中的元素组装成新的数组R 组
  • iOS 299美元企业账号申请流程及注意事项

    iOS开发者众多 但并不是所有的开发者都对账号申请 证书配置这些问题都清楚 毕竟不是所有开发者都能够经历这个环节 多数情况下是进公司之前这些东西都已经有了 作为一个合格的iOS开发者 我们必须要了解苹果的三种开发者账号 下图对三者进行了比较
  • C# 中的委托和事件(详解)

    C 中的委托和事件 委托和事件在 NET Framework 中的应用非常广泛 然而 较好地理解委托和事件对很多接触 C 时间不长的人来说并不容易 它们就像是一道槛儿 过了这个槛的人 觉得真是太容易了 而没有过去的人每次见到委托和事件就觉得
  • opencv图像处理及视频处理基本操作

    计算机眼中的图像由一个个像素组成 每个像素点的值在0 255之间 代表像素点的亮度 0为最暗 255为最亮 通常彩色图为三通道 灰度图 黑白图 为单通道 彩色图像包括三个颜色通道 B G R 分别表示蓝 绿 红 目录 1 图像的表示 2 图
  • html超链接打开共享文件夹,访问共享文件夹的方法

    在局域网 我们经常会用到共享文件 这样在多人传输文件跟共享资料上就会又方便又快捷啦 在这里教大家怎样建立跟访问共享文件夹 打开控制面板 找到防火墙 点击打开防火墙 弹出防火墙设置面板 我们选择关闭防火墙 虽然写不推荐 但我们可以无视它 然后
  • 抖音自动生成文字_文字动画怎么制作?这里教你一键制作抖音爆款文字视频

    现在很多人都会在闲暇时间打开抖音刷刷视频 经常会看到很多文字视频特别有趣 配上动感的节奏 文字立刻鲜活起来 如何才能制作出这样的文字视频呢 今天给大家介绍一种全网最简单的抖音文字视频制作方法 不需要会使用AE 甚至也不需要你打字 直接语音识
  • 关于python基础,90%的人不知道这些。但你一定得清楚。

    经过前几次的学习我们已经安装好Python解释器 搭建好顺手的IDE环境 那么接下来 我们就正式的开始一些列Python知识的学习 代码敲起来 一 字面量 字面量是以变量或常量给出的原始数据 在Python中 有多种类型的字面量 如数字字面
  • linux中断实验

    文章目录 一 linux中断简介 1 linux中断API函数 1 中断号 2 request irq函数 3 free irq 4 中断处理函数 5 中断使能与禁止函数 2 上半部与下半部 1 软中断 2 tasklet 3 工作队列 3
  • jboss源码中片段分析

    package com test import java security AccessController import java security PrivilegedAction import java util ArrayList
  • QRegExp

    d 非负整数 正整数 0 0 9 1 9 0 9 正整数 d 0 非正整数 负整数 0 0 9 1 9 0 9 负整数 d 整数 d d 非负浮点数 正浮点数 0 0 9 0 9 1 9 0 9 0 9 1 9 0 9 0 9 0 9 1
  • post使用方法以及有道API

    import requests import json headers User Agent Mozilla 5 0 Windows NT 10 0 Win64 x64 AppleWebKit 537 36 KHTML like Gecko
  • Unity人物前进的方向和相机朝向一致

    鼠标点击滑动移动相机 代码 using UnityEngine using System Collections This is an improved orbit script based on the MouseOrbitImprove
  • 数据结构-图的应用算法

    提示 文章写完后 目录可以自动生成 如何生成可参考右边的帮助文档 文章目录 一 最小生成树 1 1 Prim算法 1 2 Kruskal算法 二 最短路径 2 1 Dijkstra算法 2 2 Floyd算法 三 有向无环图描述表达式 四