算法:图的相关算法

图的相关算法

  • 1. 图的遍历算法
    • 1.1 深度优先搜索
    • 1.2 广度优先搜索
  • 2. 最小生成树求解算法
    • 普里姆(Prim)算法
    • 克鲁斯卡尔(Kruskal)算法
  • 3. 拓扑排序
  • 4. 最短路径算法

1. 图的遍历算法

图的遍历是指从某个顶点出发,沿着某条搜索路径对图中的所有顶点进行访问且只访问次的过程。
图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。
图的遍历要比树的遍历复杂得多。因为图的任一个结点都可能与其余顶点相邻接,所以在访问了某个顶点之后,可能沿着某路径又回到该结点上,为了避免对顶点进行重复访问,在图的遍历过程中必须记下每个已访问过的顶点。深度优先搜索和广度优先搜索是两种遍历图的基本方法。

1.1 深度优先搜索

类似树的先根遍历,在第一次经过一个顶点时就进行访问操作。遍历步骤如下:

  1. 设置搜索指针 p,使p指向顶点。
  2. 访问p所指顶点,并使p指向与其相邻接的且尚未被访问过的顶点。
  3. 若p所指顶点存在,则重复步骤(2),否则执行步骤(4)。
  4. 沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点,并使p指向这个未被访问的顶点,然后重复步骤(2),直到所有的顶点均被访问为止。
int visited[MaxN] = {0};  //调佣遍历算法前设置所有的顶点都被访问过
void Dfs(Graph G, int i)
{EdgeNode *t; int j;printf("%d",i);               //访问序号为i的顶点visited[i] = 1;               //序号为i的顶点已被访问过t = G.Vertices[i].firstarc;   //取顶点i的第一个邻接顶点while(t!=NULL){               //检查所有与顶点i相邻接的顶点j=t->adjvex;                 //顶点j为顶点i的一个邻接顶点if(visited[j]==0)           //若顶点j未被访问则从顶点j出发进行深度优先搜索Dfs(G,j);t=t->nextarc;              //取顶点i的下一个邻接顶点}
}

1.2 广度优先搜索

图:广度优先搜索

图的广度优先搜索方法为:从图中的某个顶点v出发,在访问了之后依次访问v的各个未被访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直到图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点,则另选图中的一个未被访问的顶点作为起点,重复上述过程,直到图中所有的顶点都被访问到为止。
广度优先遍历图的特点是尽可能先进行横向搜索,即最先访问的顶点的邻接点也先被访问。为此,引入队列来保存已访问过的顶点序列,即每当一个顶点被访问后,就将其放入队列中,当队头顶点出队时,就访问其未被访问的邻接点并令这些邻接顶点入队。

void Bfs(Graph G)
{EdgeNode *t; int i,j,k;int visited[MaxN]={0};          //调用遍历算法前设置所有的顶点都没有被访问过initQueue(Q);                  //创建一个空队列for(i=0;i<G.Vnum;i++){if(!visited[i]){               //顶点i未被访问过enQueue(Q,i);printf("%d",i);visited[i]=1;    //访问顶点i并设置已访问标志while(!isEmpty(Q)){            //若队列不空,则继续取顶点进行广度优先搜索deQueue(Q,k);t=G.Vertices[k].firstarc;for(;t;t=t->nextarc){      //检查所有与顶点K相邻接的顶点j=t->adjvex;           //顶点j是顶点k的一个邻接顶点if(visited[j]==0){     //若顶点j未被访问过,将j加入队列enQUeue(Q,j);printf("%d",j);    //访问序号为j的顶点并设置已访问标志visited[j]=1;}}}}}
}

2. 最小生成树求解算法

在这里插入图片描述
生成树:设图G=(V,E)是个连通图,如果其子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。
对于有n个顶点的连通图,至少有 n-1 条边,而生成树中恰好有 n-1条边,所以连通图的生成树是该图的极小连通子图。若在图的生成树中任意加一条边,则必然形成回路。
图的生成树不是唯一的。对于非连通图而言,每个联通分量中的顶点集和遍历时走过的边集一起构成若干棵生成树,把它们称为非连通图的生成树森林。

最小生成树:对于连通网来说,边是带权值的,生成树的各边也带权值,于是就把生成树各边的权值总和称为生成树的权,把权值最小的生成树称为最小生成树。求解最小生成树有许多实际的应用。普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两种常用的求解最小生成树算法。

普里姆(Prim)算法

在这里插入图片描述

克鲁斯卡尔(Kruskal)算法

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

3. 拓扑排序

在工程领域,一个大的工程项目通常被划分为许多较小的子工程(称为活动),当这些子工程都完成时,整个工程也就完成了。若以顶点表示活动,用有向边表示活动之间的优先关系,则称这样的有向图为以顶点表示活动的网(Activity On Vertex network,AOV 网)。在有向网中若从顶点 v i v_i vi到顶点 v j v_j vj有一条有向路径,则顶点 v i v_i vi v j v_j vj的前驱,顶点 v j v_j vj v i v_i vi的后继。若 < v i , v j > <v_i,v_j> <vi,vj>是网中的一条弧,则顶点 v i v_i vi v j v_j vj的直接前驱,顶点 v j v_j vj v i v_i vi的直接后继。AOV 网中的弧表示了活动之间的优先关系,也可以说是一种活动进行时的制约关系。

在 AOV 网中不应出现有向环、回路若存在的话,则意味着某项活动必须以自身任务的完成为先决条件,显然这是荒谬的。因此,若要检测一个工程划分后是否可行,首先就应检查对应的AOV 网是否存在回路。检测的方法是对其 AOV 网进行拓扑排序。
在这里插入图片描述
对一个有向图进行拓扑排序的结果会有两种情况:

  1. 一种是所有顶点已输出,此时整个拓扑排序完成,说明网中不存在回路;
  2. 另一种是尚有未输出的顶点,剩余的顶点均有前驱顶点,表明网中存在回路,拓扑排序无法进行下去。

4. 最短路径算法

狄克斯特拉算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/464814.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PowerCat反弹Shell

PowerCat介绍 PowerCat是一个powershell写的tcp/ip瑞士军刀&#xff0c;可以看成ncat的powershell的实现&#xff0c;然后里面也 加入了众多好用的功能&#xff0c;如文件上传&#xff0c;smb协议支持&#xff0c;中继模式&#xff0c;生成payload&#xff0c;端口扫描等等。 …

A014-基于Spring Boot的家电销售展示平台设计与实现

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

蓬勃发展:移动开发——关于软件开发你需要知道些什么

一、前言 移动开发一直都是软件开发领域中最有趣的领域之一&#xff0c;这是因为&#xff1a; 1、移动开发为“只有一个人”的开发团队提供了一个非常独特的机会&#xff0c;让他可以在相对较短的时间内建立一个实际的、可用的、有意义的应用程序&#xff1b; 2、移动开发也代…

RK3568平台开发系列讲解(字符设备驱动篇)注册字符设备

🚀返回专栏总目录 文章目录 一、字符设备初始化二、字符设备的注册和注销沉淀、分享、成长,让自己和他人都能有所收获!😄 📢注册字符设备可以分为两个步骤: 字符设备初始化字符设备的添加一、字符设备初始化 字符设备初始化所用到的函数为 cdev_init(…),在对该函数讲…

软件测试面试题个人总结

前面看到了一些面试题&#xff0c;总感觉会用得到&#xff0c;但是看一遍又记不住&#xff0c;所以我把面试题都整合在一起&#xff0c;都是来自各路大佬的分享&#xff0c;为了方便以后自己需要的时候刷一刷&#xff0c;不用再到处找题&#xff0c;今天把自己整理的这些面试题…

【Java语言】继承和多态(一)

继承 继承就是实现代码的复用&#xff1b;简而言之就是重复的代码作为父类&#xff08;基类或超类&#xff09;&#xff0c;而不同的可以作为子类&#xff08;派生类&#xff09;。如果子类想要继承父类的成员就一定需要extends进行修饰&#xff08;如&#xff1a;&#xff08;…

关于我的编程语言——C/C++——第四篇(深入1)

&#xff08;叠甲&#xff1a;如有侵权请联系&#xff0c;内容都是自己学习的总结&#xff0c;一定不全面&#xff0c;仅当互相交流&#xff08;轻点骂&#xff09;我也只是站在巨人肩膀上的一个小卡拉米&#xff0c;已老实&#xff0c;求放过&#xff09; 字符类型介绍 char…

Golang | Leetcode Golang题解之第535题TinyURL的加密与解密

题目&#xff1a; 题解&#xff1a; import "math/rand"type Codec map[int]stringfunc Constructor() Codec {return Codec{} }func (c Codec) encode(longUrl string) string {for {key : rand.Int()if c[key] "" {c[key] longUrlreturn "http:/…

群控系统服务端开发模式-应用开发-业务架构逻辑开发第一轮测试

整个系统的第一个层次已经开发完毕&#xff0c;已经有简单的中控&#xff0c;登录、退出、延迟登录时长、黑名单、数据层封装、验证层封装、RSA加解密、Redis等功能&#xff0c;还缺获取个人、角色按钮权限、角色菜单权限功能。角色按钮权限以及角色菜单权限等明后天开发&#…

「C/C++」C/C++的区别

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…

PySpark 本地开发环境搭建与实践

目录 一、PySpark 本地开发环境搭建 &#xff08;一&#xff09;Windows 本地 JDK 和 Hadoop 的安装 &#xff08;二&#xff09;Windows 安装 Anaconda &#xff08;三&#xff09;Anaconda 中安装 PySpark &#xff08;四&#xff09;Pycharm 中创建工程 二、编写代码 …

筋膜枪哪个牌子好?深入探索国产筋膜枪品牌的口碑之选

​双11购物狂欢节即将来临&#xff0c;面对市面上琳琅满目的筋膜枪品牌&#xff0c;是否感到无从选择&#xff1f;别担心&#xff0c;我们为你带来了倍益康X Max、有品H1、飞利浦mini小金刚、SKG F7和Artsmith AS300这五款迷你筋膜枪的全方位测评&#xff0c;帮你找到性价比最高…

java.io.FileNotFoundException: Could not locate Hadoop executable: (详细解决方案)

1&#xff0c;当你在pycharm 上运行spark代码时候出现下面这个报错。 解决方案 我们要先去hadoop的bin目录下去看看里面是否有 winutils.exe 这个错误 就是缺少winutils.exe 所以报这个错误&#xff0c;把它放到你的hadoop的bin目录下问题就解决了

Linux第三讲:环境基础开发工具使用

Linux第三讲&#xff1a;环境基础开发工具使用 1.Linux软件包管理器yum1.1什么是软件包管理器1.2操作系统生态问题1.3什么是yum源 2.vim详解2.1什么是vim2.2vim的多模式讲解2.2.1命令模式的诸多指令2.2.1.1gg和nshiftg2.2.1.2shift$和shift^2.2.1.3上、下、左、右2.2.1.4w和b2.…

数据库管理-第256期 Oracle DB 23.6新特性一览(20241031)

数据库管理256期 2024-10-31 数据库管理-第256期 Oracle DB 23.6新特性一览&#xff08;20241031&#xff09;1 AI向量搜索&#xff1a;新的向量距离度量2 混合向量索引3 分区&#xff1a;本地邻近分区向量索引4 持久邻近图向量索引5 稀疏向量6 邻居图向量索引的事务支持7 特征…

智能诊断系统:AI可以辅助临床诊断,提高疾病诊断的准确性和效率

​ 大家好&#xff0c;我是Shelly&#xff0c;一个专注于输出AI工具和科技前沿内容的AI应用教练&#xff0c;体验过300款以上的AI应用工具。关注科技及大模型领域对社会的影响10年。关注我一起驾驭AI工具&#xff0c;拥抱AI时代的到来。 AI工具集1&#xff1a;大厂AI工具【共2…

GCC编译器的`-Wall`、`-Wextra`和`-pedantic`选项解读

gcc是广泛使用的开源编译器&#xff0c;-Wall、-Wextra和-pedantic是gcc中用于控制警告信息的选项&#xff0c;以下是详细介绍&#xff1a; -Wall&#xff08;启用大部分警告&#xff09; 功能&#xff1a;-Wall 选项用于启用一系列常用的警告信息&#xff0c;这些警告能帮助…

[RocketMQ 5.3.1] Win11 + Docker Desktop 本地部署全流程 + 踩坑记录

时间比较仓促&#xff0c;部署Linux的过程我就简写啦。 0. 我的系统版本&#xff08;供参考&#xff09; Windows 11 专业版 24H2, Build 26100.2161 Experience: Windows Feature Experience Pack 1000.26100.32.0 JDK: OpenJDK Amazon Corretto 21.0.4.7.1 1. 在WSL2上安…

基于SpringBoot的植物园管理小程序【附源码】

基于SpringBoot的植物园管理小程序 效果如下&#xff1a; 系统登录页面 管理员主页面 商品订单管理页面 植物园信息管理页面 小程序主页面 小程序登录页面 植物信息查询推荐页面 研究背景 随着互联网技术的快速发展和移动设备的普及&#xff0c;线上管理已经成为各行各业提高…

qt QDragEnterEvent详解

1、概述 QDragEnterEvent是Qt框架中用于处理拖放进入事件的一个类。当用户将一个拖拽对象&#xff08;如文件、文本或其他数据&#xff09;拖动到支持拖放操作的窗口部件&#xff08;widget&#xff09;上时&#xff0c;系统会触发QDragEnterEvent事件。这个类允许开发者在拖拽…