【数据结构】邻接矩阵和邻接图的遍历

写在前面
本篇文章开始学习数据结构的图的相关知识,涉及的基本概念还是很多的。
本文的行文思路:
学习图的基本概念
学习图的存储结构——本文主要介绍邻接矩阵和邻接表
对每种结构进行深度优先遍历和广度优先遍历
先识概念
话不多说,狠活献上

学习思想
等等,先别急,正式学习之前先认识几个英语单词及缩写
类型(Type)
顶点(vertex)
边(Edge)
邻接(adjacency,简写adj)
邻接矩阵(adjacency Matrix)
邻接表(adjacency List)
深度优先遍历(Depth First Search,简称BFS)
广度优先遍历(Breadth First Search,简称DFS)
邻接矩阵的存储结构
typedef char VertexType; //顶点类型
typedef int EdgeType; //边类型
#define MAXVEX 100 //最大顶点数目
#define INFINITY 65535 //用65535表示无穷//邻接矩阵的存储结构typedef struct
{VertexType vexs[MAXVEX]; //顶点数组EdgeType arc[MAXVEX][MAXVEX]; //边数组int numVertexes, numEdges; //当前顶点的顶点数和边数
}MGraph;
邻接表的存储结构
#define MAXVEX 100
typedef char VertexType; //顶点类型
typedef int EdgeType; //边上的权值类型int visited[MAXVEX];typedef struct EdgeNode //边表结点
{int adjvex; //存储该顶点对应的下标EdgeType info; //存储权值,非网图则无需struct EdgeNode* next;
}EdgeNode;typedef struct VertexNode //顶点结点
{VertexType data; //存储顶点信息EdgeNode* firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];//邻接表存储结构typedef struct
{AdjList adjList;int numVertexes, numEdges; //当前顶点数目和边数
}GraphAdjList;
再学应用
邻接矩阵的深度遍历和广度遍历
深度遍历:实际上就是二叉树的前序遍历
广度遍历:实际上就是二叉树的层序遍历,要用到队列,我们自己还要写出队列的一些基本操作
#include<stdio.h>
#include<malloc.h>typedef char VertexType; //顶点类型
typedef int EdgeType; //边类型
#define MAXVEX 100 //最大顶点数目
#define INFINITY 65535 //用65535表示无穷//邻接矩阵的存储结构typedef struct
{VertexType vexs[MAXVEX]; //顶点数组EdgeType arc[MAXVEX][MAXVEX]; //边数组int numVertexes, numEdges; //当前顶点的顶点数和边数
}MGraph;//邻接矩阵的初始化void CreateMGraph(MGraph* G)
{int i, j, k;printf("请输入顶点的个数和边数:");scanf("%d%d", &G->numVertexes, &G->numEdges);for (i = 0; i < G->numVertexes; i++){printf("请输入%d个顶点: ", i + 1);scanf("%s", &G->vexs[i]);}//将矩阵的所有数据初始化为"无穷"for (i = 0; i < G->numVertexes; i++)for (j = 0; j < G->numVertexes; j++)G->arc[i][j] = INFINITY;//然后自定义矩阵中的数据for (k = 0; k < G->numEdges; k++){printf("请输入边(vi,vj)中的下标i和j: ");scanf("%d%d", &i, &j);G->arc[i][j] = 1;G->arc[j][i] = G->arc[i][j]; //无向图的邻接矩阵沿着右对角线对称}
}int visited[MAXVEX]; //访问标志的数组//深度优先递归算法void DFS(MGraph G, int i)
{int j;visited[i] = 1; //将第i个顶点标记为已访问printf("%c ", G.vexs[i]); //打印顶点,也可以是其他操作//循环遍历G中所有的顶点for (j = 0; j < G.numVertexes; j++){//判断当前正在遍历的顶点j和顶点i是否相邻且未被访问过,相连为1,不相连为0(前提是不带权的图)if (G.arc[i][j] == 1 && !visited[j]) DFS(G, j);}}//邻接矩阵的深度遍历操作void DFSTraverse(MGraph G)
{int i;//初始化所有顶点状态都是未访问过的 for (i = 0; i < G.numVertexes; i++){visited[i] = 0;}//对所有未访问过的顶点调用DFS,若为连通图则只执行一次for (i = 0; i < G.numVertexes; i++){if (!visited[i])DFS(G, i);}
}//队列的顺序存储结构
typedef struct
{char data[MAXVEX];int front;int rear;
}SqQueue;void InitQueue(SqQueue* Q)
{Q->front = 0;Q->rear = 0;
}void EnQueue(SqQueue* Q,int e)
{if ((Q->rear + 1) % MAXVEX == Q->front)return;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXVEX;
}void DeQueue(SqQueue* Q, int* e)
{if (Q->front == Q->rear)return;*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXVEX;}int QueueEmpty(SqQueue Q)
{return Q.front == Q.rear;
}//邻接矩阵的广度遍历void BFSTraverse(MGraph G)
{int i, j;SqQueue Q;for (i = 0; i < G.numVertexes; i++){visited[i] = 0; //将每一个顶点都设置未访问}InitQueue(&Q); //初始化一个辅助用的队列for (i = 0; i < G.numVertexes; i++){if (!visited[i]){visited[i] = 1; //设置当前顶点为已访问printf("%c ", G.vexs[i]);EnQueue(&Q, i); //将此顶点入队列while (!QueueEmpty(Q)){DeQueue(&Q, &i); //首元素出队,赋给ifor (j = 0; j < G.numVertexes; j++){if (G.arc[i][j] == 1 && !visited[j]) //边存在且未被访问过{visited[j] = 1; //设置当前顶点为已访问printf("%c ", G.vexs[j]); //打印顶点EnQueue(&Q, j); //将此顶点入队}}}}}
}int main()
{MGraph G;CreateMGraph(&G);printf("DFS遍历顺序:");DFSTraverse(G);printf("\n");printf("BFS遍历顺序:");BFSTraverse(G);printf("\n");return 0;
}
邻接表的深度遍历和广度遍历
#define _CRT_SECURE_NO_WARNINGS 1
//图的遍历主要有两种,深度优先遍历和广度优先遍历
//深度优先遍历实际上是二叉树的先序遍历,广度优先遍历实际上是二叉树的层序遍历#include<stdio.h>
#include<malloc.h>
#define MAXVEX 100
typedef char VertexType; //顶点类型
typedef int EdgeType; //边上的权值类型int visited[MAXVEX];typedef struct EdgeNode //边表结点
{int adjvex; //存储该顶点对应的下标EdgeType info; //存储权值,非网图则无需struct EdgeNode* next;
}EdgeNode;typedef struct VertexNode //顶点结点
{VertexType data; //存储顶点信息EdgeNode* firstedge; //边表头指针
}VertexNode, AdjList[MAXVEX];//邻接表存储结构typedef struct
{AdjList adjList;int numVertexes, numEdges; //当前顶点数目和边数
}GraphAdjList;//邻接表的初始化
void CreateALGraph(GraphAdjList* GL)
{int i, j, k;EdgeNode* e;printf("输入顶点数和边数:");scanf("%d%d", &GL->numVertexes, &GL->numEdges);//将数据存进顶点数组,把顶点指针域置空for (i = 0; i < GL->numVertexes; i++){getchar();printf("请输入第%d个顶点:", i + 1);scanf("%c", &GL->adjList[i].data);GL->adjList[i].firstedge = NULL;}for (k = 0; k < GL->numEdges; k++){printf("输入边(vi,vj)上的顶点序号:");scanf("%d%d", &i, &j);//结点i记录结点j的下标e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = j;e->next = GL->adjList[i].firstedge; //下面两步相当于链表的头插法GL->adjList[i].firstedge = e;//结点j记录结点i的下标e = (EdgeNode*)malloc(sizeof(EdgeNode));e->adjvex = i;e->next = GL->adjList[j].firstedge; //下面两步相当于链表的头插法GL->adjList[j].firstedge = e;}}//邻接表的深度优先递归算法void DFS(GraphAdjList GL, int i)
{EdgeNode* p;visited[i] = 1;printf("%c ", GL.adjList[i].data);p = GL.adjList[i].firstedge;while (p){if (!visited[p->adjvex])DFS(GL, p->adjvex);p = p->next;}
}//邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{int i;for (i = 0; i < GL.numVertexes; i++){visited[i] = 0;}for (i = 0; i < GL.numVertexes; i++){if (!visited[i])DFS(GL, i);}
}//队列的顺序存储结构
typedef struct
{char data[MAXVEX];int front;int rear;
}SqQueue;void InitQueue(SqQueue* Q)
{Q->front = 0;Q->rear = 0;
}void EnQueue(SqQueue* Q, int e)
{if ((Q->rear + 1) % MAXVEX == Q->front)return;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAXVEX;
}void DeQueue(SqQueue* Q, int* e)
{if (Q->front == Q->rear)return;*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAXVEX;}int QueueEmpty(SqQueue Q)
{return Q.front == Q.rear;
}//邻接表的广度优先遍历
void BFSTraverse(GraphAdjList GL)
{int i;EdgeNode* p;SqQueue Q;Q.front = Q.rear = 0;for (i = 0; i < GL.numVertexes; i++){visited[i] = 0;if (!visited[i]){visited[i] = 1;printf("%c ", GL.adjList[i].data);EnQueue(&Q, i);while (!QueueEmpty(Q)){DeQueue(&Q, &i);p = GL.adjList[i].firstedge;while (p){if (!visited[p->adjvex]){visited[p->adjvex] = 1;printf("%c ", GL.adjList[p->adjvex].data);EnQueue(&Q, p->adjvex);}p = p->next;}}}}
}int main()
{GraphAdjList GL;CreateALGraph(&GL);printf("DFS遍历顺序:");DFSTraverse(GL);printf("\n");printf("BFS遍历顺序:");BFSTraverse(GL);printf("\n");return 0;
}
一点补充
下面补充一个小知识点,就是typedef定义数组类型,先看下面的代码是什么意思呢?
typedef struct VertexNode AdjList[MAXVEX];
上面语句的意思是:定义一个元素类型是 struct VertexNode,含有MAXVEX个元素的数组类型
换个例子:
typedef int vector[10];
vector v1,v2;
语句定义了vector类型的两个对象v1和v2,每个对象都是vector类型的一个数组,每个数组由10个整型元素所组成。
写在最后
上面的代码难免会有疏漏,如果各位大佬发现错误,请一定要指正🙏
👍🏻 点赞,你的认可是我创作的动力!
⭐ 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富!
相关文章:

【数据结构】邻接矩阵和邻接图的遍历
写在前面 本篇文章开始学习数据结构的图的相关知识,涉及的基本概念还是很多的。本文的行文思路:学习图的基本概念学习图的存储结构——本文主要介绍邻接矩阵和邻接表对每种结构进行深度优先遍历和广度优先遍历先识概念话不多说,狠活献上学习思想等等&…...

设计跳表(动态设置节点高度)
最近学习redis的zset时候,又看到跳表的思想,突然对跳表的设置有了新的思考 这是19年设计的跳表,在leetcode的执行时间是200ms 现在我对跳表有了新的想法 1、跳表的设计,类似二分查找,但是不是二分查找,比较…...

基于神经辐射场(Neural Radiance Fileds, NeRF)的三维重建- 简介(1)
Nerf简介 Nerf(neural Radiance Fileds) 为2020年ICCV上提出的一个基于隐式表达的三维重建方法,使用2D的 Posed Imageds 来生成(表达)复杂的三维场景。现在越来越多的研究人员开始关注这个潜力巨大的领域,也…...

【AI面试】NMS 与 Soft NMS 的辨析
往期文章: AI/CV面试,直达目录汇总【AI面试】L1 loss、L2 loss和Smooth L1 Loss,L1正则化和L2正则化 一、NMS 非极大值抑制(Non-Maximum Suppression,NMS),并不是深度学习时期,目标…...

一文让你彻底理解Linux内核多线程(互斥锁、条件变量、读写锁、自旋锁、信号量)
一、互斥锁(同步) 在多任务操作系统中,同时运行的多个任务可能都需要使用同一种资源。这个过程有点类似于,公司部门里,我在使用着打印机打印东西的同时(还没有打印完),别人刚好也在…...

利用python写一个gui小公举--环境搭建
文章目录背景搭建环境安装必要库添加工具快捷方式检验背景 在实习过程中遇到一个问题,某项目是通过python代码实现的,而且需要一直修改参数实现功能,过程有些繁琐。虽然师兄用PHP study搭了一个网站用于查看结果,但是还是过于繁琐…...
英飞凌Tricore实战系列02_ENDINIT属性看门狗原理及应用
目录 1.概述2.ENDINIT功能及使用2.1 ENDINIT属性2.2 改写受ENDINIT保护寄存器的步骤3. Tricore 看门狗介绍及使用3.1 看门狗系统介绍3.1.1 安全看门狗介绍3.1.2 CPU看门狗介绍3.2 看门狗模式介绍3.2.1 Time-out模式3.2.2 正常模式(Normal Mode)3.2.3 禁用模式(Disabled Mode…...
Java Number类
Java Number 类是一个抽象类,它是所有数字类的基类。Java 中的数字类包括 Byte、Short、Integer、Long、Float 和 Double,它们都继承自 Number 类。Java Number 类提供了一些常用的方法,可以用于将数字类型转换为不同的格式,以及进…...

C++构造和析构
欢迎来观看温柔了岁月.c的博客 目前 设有C学习专栏 C语言项目专栏 数据结构与算法专栏 目前主要更新C学习专栏,C语言项目专栏不定时更新 待C专栏完毕,会陆续更新C项目专栏和数据结构与算法专栏 一周主要三更,星期三,星期五&#x…...

docker安装即docker连接mysql(window)
一 安装docker 1.什么是docker Docker容器与虚拟机类似,但二者在原理上不同。容器是将操作系统层虚拟化,虚拟机则是虚拟化硬件,因此容器更具有便携性、高效地利用服务器。 2.WSL2 WSL,即Windows Subsystem on Linux,中…...

HMM-维特比算法
HMM-维特比算法(viterbi)HMM回顾隐马科夫链解法:维特比算法(Viterbi)HMM回顾 最终的公式可以解释主要分为两个部分: P(xi|yi),发射概率,字面意思是从一个词性中发射/生成出某一个单…...

【C++初阶】2. 类和对象_1
1. 面向过程和面向对象的初步认识 2. 类的引入 C语言结构体中只能定义变量,在C中,结构体内不仅可以定义变量,也可以定义函数。比如: 之前在数据结构初阶中,用C语言方式实现的栈,结构体中只能定义变量&#…...
kotlin把函数作为参数转递给另一个函数
kotlin把函数作为参数转递给另一个函数 fun say(s: String, foo: (String) -> Unit) {print("hello")foo(s) }fun hi(str: String) {println(str) }fun main(args: Array<String>) {say("hello", ::hi) } 输出: hellohello...

海思嵌入式开发-005-OpenHarmony源码编译问题
海思嵌入式开发-005-OpenHarmony源码编译问题一、问题描述二、解决方案2.1解决原理2.2获取OpenHarmony 3.1.1 Release源码2.3最后解决问题,编译成功。一、问题描述 按照链接拉取master源码,出现如下问题,打开build.log文件 提示相应位置的文…...

指针的进阶续(笔试题强化练习)
写在前面:在上次我们学习了指针的相关类型的知识,对指针家族的成员基本有了了解,这次让我们跟着一些题目来练习和补充一些知识,这有助于我们强化理解这些知识。 话不多说,我们马上开始: 1.指针和数组的笔…...

一个供参考的计算机的学习路线
本文是介绍如何成为一个Geek,一个真正的计算机高手。 适合有成为IT领域技术大牛的人参考。 写给大一新生和所有向深耕IT领域的人,避免走一些弯路。 仅代表个人想法,供批判性参考。 第一门入门的必备功课-语法与算法 什么是计算机?…...

React(五):受控组件、高阶组件、Portals、Fragment、CSS的编写方式
React(五)一、受控组件1.什么是受控组件(v-model)2.收集表单数据:input和单选框3.收集表单数据:下拉框二、非受控组件三、高阶组件1.什么是高阶组件2.高阶组件的应用13.高阶组件的应用2-注入Context4.高阶组件的应用3-登录鉴权5.高…...

MATLAB——系统环境
MATLAB概述MATLAB的发展MATLAB:MATrix LABoratory1980年前后,Cleve Moler教授编写的Linpack 和Eispack的接口程序。1984年,MATLAB第1版(DOS版)1992年,MATLAB4.0版1994年,MATLAB 4.2版1997年,MATLAB 5.0版1999年&#x…...

2 GateWay工作流程+GateWay搭建
GateWay工作流程GateWay搭建 核心流程图如下: 核心概念: 客户端向 Spring Cloud Gateway 发出请求。如果Gateway Handler Mapping确定请求与路由匹配,则将其发送到Gateway Web Handler 处理程序。此处理程序通过特定于请求的Fliter链运行请求…...
【微信小程序】富文本rich-text的图片预览效果的几种方法
前言 使用原生小程序开发,实现在富文本rich-text中的图片预览效果的几种方法对比。 1.正则wx.previewImage(有明显不足) 一个不需要用额外组件或插件的方法: 思路:使用正则把图片的url进行剖离出来,push…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...