李春葆《数据结构》——图相关代码
邻接矩阵结构体:
#define MAX<最大结点个数>
#define INF 32765 //定义无穷
typedef struct{int no;//顶点的编号;InfoType info;//顶点的其他信息
}vertexType;//顶点的类型
typedef struct{int edges[MAX][Max];//邻接矩阵数组 int vertexType vexs[MAX];//存放顶点的信息int n,e;//顶点数,边数
}MatGraph;
邻接表结构体:
typedef struct ANode{int adjvex;//该编的邻接点编号struct ANode *nextarc;//指向下一条边的指针int weight;//权值
}ArcNode;//边结点类型 typedef struct Vnode{InfoType info;//顶点的其他信息 ArcNode *firstarc;//指向第一个边结点
}VNode; typedef struct {VNode adjlist[MAX];//邻接表的头节点数组int n,e; //顶点数,边数
}AdjGraph;
一:带权图。邻接矩阵转换为邻接表。
思想:找不为0和无穷的元素,能够找到,则存在边。头插法插到单链表中。
代码:
void MatToList(MatGraph g,AdjGraph *&G){int i,j;ArcNode *p;G=(AdjGraph *)malloc(sizeof(AdjGraph));for(i=0;i<g.n;i++){G->adjlist[i].firstarc=NULL;//所有头结点指针域置空 }for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=0&&g.edges[i][i]!=INF){p=(ArcNode*)malloc(sizeof(ArcNode));//创建边结点p->adjvex=j;p->weight=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;//用头插法插入 G->adjlist[i].firstarc=p;}}}
}
二:带权图。邻接表转换为邻接矩阵。
思想:遍历邻接表中的所有单链表,通过第i个单链表查找顶点i的相邻结点p,将邻接矩阵g中的元素g.edges[i][p->adjvex]=p->weight。
代码:
void ListToMat(AdjGraph *G,MatGraph,&g){int i;ArcNode *p;for(i=0;i<G->n;i++){p=G.adjlist[i].firstarc;//p指向第i个单链表的头结点 while(p!=NULL){g.edges[i][p->adjvex]=p->weight;p=p->nextarc;}}g.n=G->n,g.e=G->e;
}
图的深度优先遍历代码:
int visited[Max]={0};//全局数组
void DFS(AdjGraph *G,int v){ArcNode *p;visited[v]=1;printf("%d",v);p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){DFS(G,p->adjvex);}p=p->nextarc;}
}
图的深度优先遍历的应用
(1)图采用邻接表存储。设计一个算法判断从顶点u到顶点v是否存在简单路径。
简单路径:路径上不存在重复结点。
代码:
bool ExistPath(AdjGraph *G,int u,int v){int w;ArcNode *p;visited[u]=1;if(u==v) return true;p=G->adjlist[u].firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){if(ExistPath(G,w,v)) return true;}p=p->nextarc;}return false;
}
(2)图采用邻接表存储。输出从顶点u到顶点v的一条简单路径。(假设至少存在一条)
代码:
void FindPath(AdjGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度,假设初始为-1。 int w,i;ArcNode *p; visited[u]=1;d++;path[d]=u;if(u==v){for(i=0;i<=d;i++){printf("%d",path[i]);}printf("\n");return;}p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){FindPath(G,w,v,path,d);}p=p->nextarc;}
}
(3)图采用邻接表存储。输出从顶点u到顶点v的所有简单路径。
代码:
void FindAllPath(AdjGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度,假设初始为-1。 int w,i;ArcNode *p; visited[u]=1;d++;path[d]=u;if(u==v){for(i=0;i<=d;i++){printf("%d",path[i]);}printf("\n");visited[u]=0;//恢复环境 return;}p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){FindAllPath(G,w,v,path,d);}p=p->nextarc;}visited[u]=0;//恢复环境,使该顶点可以重复访问
}
(4)图采用邻接表存储。输出从顶点u到顶点v长度为a的所有简单路径。
代码:
void PathlenAll(AdjGraph *G,int u,int v,int path[],int d){//d表示path中的路径长度,假设初始为-1。 int w,i;ArcNode *p; visited[u]=1;d++;path[d]=u;if(u==v&&d==a){//限制要输出的路径长度为a for(i=0;i<=d;i++){printf("%d",path[i]);}printf("\n");visited[u]=0;//恢复环境 return;}p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(visited[w]==0){PathlenAll(G,w,v,path,d);}p=p->nextarc;}visited[u]=0;//恢复环境,使该顶点可以重复访问
}
(5)图采用邻接表存储。求图中通过顶点k的所有简单回路。
代码:
int visited[Max];//全局变量
void DFSPath(AdjGraph *G,int u,int v,int path[],int d){int w,i;ArcNode *p;visited[u]=1;d++;path[d]=u;p=G->adjlist.firstarc;while(p!=NULL){w=p->adjvex;if(w==v&&d>1){//找到回路输出 printf(" ");for(i=0;i<=d;i++){printf("%d",path[i]);}printf("%d\n",v);}if(visited[w]==0){DFSPath(G,w,v,path,d);}p=p->nextarc;}visited[u]=0;//恢复环境,使该顶点可以重复访问
}
void FindCyclePath(AdjGraph *G,int k){int path[MAX];DFSPath(G,k,k,path,-1);
}
图的广度优先遍历代码:
void BFS(AdjGraph *G,int v){int i,w;ArcNode *p;SqQueue *q;InitQueue(q);int visited[Max];for(i=0;i<G->n;i++){visited[i]=0;//标记数组初始化 } printf("%d",v);visited[v]=1;enQueue(q,v);while(!QueueEmpth(q)){deQueue(q,w);p=G->adjlist.firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("%d",p->adjvex);visited[p->adjvex]=1;enQueu(q,p->adjvex);}p=p->nextarc;}} printf("\n");
}
图的广度优先遍历的应用
(1)图采用邻接表存储。设计一个算法求不带权连通图G从顶点u到顶点v的最短路径
代码:
// 定义邻接表中边节点结构体
typedef struct ArcNode {int adjvex; // 该边的终点编号struct ArcNode *nextarc; // 指向下一条边的指针int weight; // 该边的权值等信息
} ArcNode;// 定义邻接表中顶点节点结构体
typedef struct VNode {char data; // 顶点信息ArcNode *firstarc; // 指向第一条边
} VNode;// 定义邻接表图结构体
typedef struct {VNode adjlist[MAX]; // 假设最大顶点数为100,可根据实际情况修改int n, e; // 图中顶点数n和边数e
} ALGraph;// 定义队列元素结构体
typedef struct {int data; // 顶点编号int parent; // 前一个顶点的位置
} QUERE;// 输出从顶点u到顶点v的最短逆路径
void ShortPath(ALGraph *G, int u, int v) {ArcNode *p;int w, i;Queue qu[MAX]; // 假设最大顶点数为100,定义非循环队列,可根据实际情况修改int front = -1, rear = -1; // 队列的头、尾指针int visited[MAX];// 初始化访问数组for (i = 0; i < G->n; i++) {visited[i] = 0;}// 将起始顶点u入队rear++;qu[rear].data = u;qu[rear].parent = -1;visited[u] = 1;// 队列不为空时进行循环while (front!= rear) {front++;w = qu[front].data;// 找到目标顶点v,输出最短逆路径if (w == v) {i = front;while (qu[i].parent!= -1) {printf("%d ", qu[i].data);i = qu[i].parent;}printf("%d ", qu[i].data);printf("\n");break;}// 取出当前顶点w的第一条边p = G->adjlist[w].firstarc;while (p!= NULL) {if (visited[p->adjvex] == 0) {visited[p->adjvex] = 1;// 将未访问过的邻接点入队rear++;qu[rear].data = p->adjvex;qu[rear].parent = front;}// 查找当前顶点w的下一条边p = p->nextarc;}}
}
(2)图采用邻接表存储。设计一个算法求不带权连通图G从顶点u到顶点v的最短路径长度(指路径上的边数)。
代码:
// 定义邻接表中边节点结构体
typedef struct ArcNode {int adjvex; // 该边的终点编号struct ArcNode *nextarc; // 指向下一条边的指针int weigth; // 该边的权值等信息
} ArcNode;// 定义邻接表中顶点节点结构体
typedef struct VNode {char data; // 顶点信息ArcNode *firstarc; // 指向第一条边
} VNode;// 定义邻接表图结构体
typedef struct {VNode adjlist[MAX]; // 假设最大顶点数为100,可根据实际情况修改int n, e; // 图中顶点数n和边数e
} ALGraph;// 定义队列元素结构体
typedef struct {int data; // 顶点编号int parent; // 前一个顶点的位置
} QUERE;// 输出从顶点u到顶点v的最短逆路径,并返回最短路径长度
int ShortPath(ALGraph *G, int u, int v) {ArcNode *p;int w, i;Queue qu[MAX]; int front = -1, rear = -1; // 队列的头、尾指针int visited[MAX];int distance[MAX]; // 新增数组用于记录每个顶点到起始顶点u的距离// 初始化访问数组和距离数组for (i = 0; i < G->n; i++) {visited[i] = 0;distance[i] = -1; // 初始化为 -1,表示未到达过}// 将起始顶点u入队,设置距离为0rear++;qu[rear].data = u;qu[rear].parent = -1;visited[u] = 1;distance[u] = 0;// 队列不为空时进行循环while (front!= rear) {front++;w = qu[front].data;// 找到目标顶点v,输出最短逆路径并返回最短路径长度if (w == v) {i = front;while (qu[i].parent!= -1) {printf("%d ", qu[i].data);i = qu[i].parent;}printf("%d ", qu[i].data);printf("\n");return distance[v];}// 取出当前顶点w的第一条边p = G->adjlist[w].firstarc;while (p!= NULL) {if (visited[p->adjvex] == 0) {visited[p->adjvex] = 1;// 将未访问过的邻接点入队rear++;qu[rear].data = p->adjvex;qu[rear].parent = front;// 更新距离数组,距离为当前顶点w的距离加1distance[p->adjvex] = distance[w] + 1;}// 查找当前顶点w的下一条边p = p->nextarc;}}return -1; // 如果未找到路径,返回 -1
}
相关文章:
李春葆《数据结构》——图相关代码
邻接矩阵结构体: #define MAX<最大结点个数> #define INF 32765 //定义无穷 typedef struct{int no;//顶点的编号;InfoType info;//顶点的其他信息 }vertexType;//顶点的类型 typedef struct{int edges[MAX][Max];//邻接矩阵数组 int vertexTy…...

Linux驱动开发第2步_“物理内存”和“虚拟内存”的映射
“新字符设备的GPIO驱动”和“设备树下的GPIO驱动”都要用到寄存器地址,使用“物理内存”和“虚拟内存”映射时,非常不方便,而pinctrl和gpio子系统的GPIO驱动,非常简化。因此,要重点学习pinctrl和gpio子系统下的GPIO驱…...

告别多品牌乱战,吉利开始觉醒
科技新知 原创作者丨思原 编辑丨蕨影 2007年,是国内自主品牌汽车萌芽的一年,当时行业普遍奉行“多生孩子好打架”战略,吉利也是在这样的背景下发布了《宁波宣言》,奠定了之后十多年的发展主导思想。 然而,新能源的快…...
Target-absent Human Attention
Abstract 预测人类注视行为对于构建能够预测用户注意力的人机交互系统非常重要。已经开发出计算机视觉模型来预测人们在搜索目标物体时的注视点。但当目标不存在于图像中时,又该如何处理呢?同样重要的是要了解当人们找不到目标时,他们如何进行搜索,以及何时停止搜索。在本文…...

<QNAP 453D QTS-5.x> 日志记录:在 Docker 中运行的 Flask 应用安装 自签名 SSL 证书 解决 Chrome 等浏览器证书安全
原因:Chrome 不信任 ssc 证书 使启用了 HTTPS,即使有使用 自签名证书 (self-signed certificate 非由可信的证书颁发机构 【CA,Certificate Authority】签发的)。浏览器 Chrome 默认不信任自签名证书,也会报 NET::ERR_…...

通过huggingface-cli下载Hugging Face上的公开数据集或模型至本地
1. 获取 Access Tokens 在使用huggingface-cli命令下载之前需要先去官网获取 Access Tokens: 获取tokens的官网链接:https://huggingface.co/settings/tokens点击新增 token: 然后选择 write 权限: 最后,这个 Access…...

论文阅读——Intrusion detection systems using longshort‑term memory (LSTM)
一.基本信息 论文名称:Intrusion detection systems using longshort‑term memory (LSTM) 中文翻译:基于长短期记忆(LSTM)的入侵检测系统 DOI:10.1186/s40537-021-00448-4 作者:FatimaEzzahra Laghrissi1* , Samira Douzi2*, Kha…...
SparkSQL的执行过程:从源码角度解析逻辑计划、优化计划和物理计划
SparkSQL的执行过程可以分为以下几个阶段:从用户的SQL语句到最终生成的RDD执行,涵盖逻辑计划、优化计划和物理计划。以下是详细的源码角度解析: 1. 解析阶段(Parsing) SQL语句解析:Spark 使用 Catalyst 引…...

Leetcode打卡:新增道路查询后的最短距离II
执行结果:通过 题目:3244 新增道路查询后的最短距离II 给你一个整数 n 和一个二维整数数组 queries。 有 n 个城市,编号从 0 到 n - 1。初始时,每个城市 i 都有一条单向道路通往城市 i 1( 0 < i < n - 1&…...

Spring Web入门练习
加法计算器 约定前后端交互接⼝ 约定 "前后端交互接⼝" 是进⾏ Web 开发中的关键环节. 接⼝⼜叫 API(Application Programming Interface), 我们⼀般讲到接⼝或者 API,指的都是同⼀个东西. 是指应⽤程序对外提供的服务的描述, ⽤于交换信息…...

计算机毕业设计 | SpringBoot+vue汽车资讯网站 汽车购买咨询管理系统(附源码+论文)
1,绪论 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理汽车资讯网站的相关信息成为必然…...

stm32下的ADC转换(江科协 HAL版)
十二. ADC采样 文章目录 十二. ADC采样12.1 ADC的采样原理12.2 STM32的采样基本过程1.引脚与GPIO端口的对应关系2.ADC规则组的四种转换模式(**)2.2 关于转换模式与配置之间的关系 12.3 ADC的时钟12.4 代码实现(ADC单通道 & ADC多通道)1. 单通道采样2. 多通道采样 19.ADC模数…...

解决IntelliJ IDEA的Plugins无法访问Marketplace去下载插件
勾选Auto-detect proxy setting并填入 https://plugins.jetbrains.com 代理URL,可以先做检查连接:...

react 如何修改弹出的modal的标题
原来标题的样子: 修改为: 实现方式: <Modal title<span>股价趋势/{this.state.pccode}</span> visible{this.state.isPriceModalOpen} style{{ top: 20 }} width{1320} height{400} footer{null} onCancel{()>this.hideMo…...

C#中的二维数组的应用:探索物理含义与数据结构的奇妙融合
在C#编程中,二维数组(或矩阵)是一种重要的数据结构,它不仅能够高效地存储和组织数据,还能通过其行、列和交叉点(备注:此处相交处通常称为“元素”或“单元格”,代表二维数组中的一个…...

HTML5拖拽API学习 托拽排序和可托拽课程表
文章目录 前言拖拽API核心概念拖拽式使用流程例子注意事项综合例子🌰 可拖拽课程表拖拽排序 前言 前端拖拽功能让网页元素可以通过鼠标或触摸操作移动。HTML5 提供了标准的拖拽API,简化了拖放操作的实现。以下是拖拽API的基本使用指南: 拖拽…...
内容补充页(相关公式解释)
from 学习日记_20241117_聚类方法(高斯混合模型) 学习日记_20241117_聚类方法(高斯混合模型) 公式 P ( Z k ) π k P(Zk) \pi_k P(Zk)πk 在高斯混合模型 (GMM) 中,公式 P ( Z k ) π k P(Zk) \pi_k P(Zk…...

vue中动态渲染静态图片资源
不报错且f12查看元素的时候,显示的src说明已经渲染到html的src上,但是就是不显示在页面上 原因 在vue上,动态渲染静态图片资源(比如从assets文件夹加载的图片)需要注意打包工具对静态资源的解析方式 由于vue2的脚手…...

管伊佳ERP,原名华夏ERP,一个简约易上手的国产ERP系统
JSH_ERP(管伊佳ERP)是一款开源、模块化的企业资源计划系统,旨在为中小企业提供高效的管理工具。它基于SpringBoot框架和SaaS模式,支持进销存、财务、生产等业务模块,包括零售、采购、销售、仓库和报表管理。 核心特点…...

学习虚幻C++开发日志——委托(持续更新中)
委托 官方文档:Delegates and Lamba Functions in Unreal Engine | 虚幻引擎 5.5 文档 | Epic Developer Community | Epic Developer Community 简单地说,委托就像是一个“函数指针”,但它更加安全和灵活。它允许程序在运行时动态地调用不…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
Django RBAC项目后端实战 - 03 DRF权限控制实现
项目背景 在上一篇文章中,我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统,为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...