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

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

学习思想
等等,先别急,正式学习之前先认识几个英语单词及缩写
类型(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…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...