图的遍历（深度优先遍历DFS，广度优先遍历BFS）以及Ｃ语言的实现

article/2025/9/20 8:09:06

遍历的定义：

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算．

一:深度优先遍历（ＤＦＳ）

１，在访问图中某一起始顶点Ｖ后，由Ｖ出发，访问它的任一邻接顶点Ｗ１

２，再从Ｗ１出发，访问与Ｗ１邻接但还未被访问过的顶点Ｗ２；

３，然后再从Ｗ２出发，进行类似的访问．．．．．．

４，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点Ｕ为止．

５，接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问过的邻接点

６，如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；

７，如果没有，就再退回一步进行搜索．重复上述过程，直到连通图中所有顶点都被访问过为止．

１，使用邻接矩阵表示的无向图深度优先遍历的实现

 

 以上图为例，以邻结矩阵创建无向图，并且深度优先遍历

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //最大顶点数
#define MAX_INT 32767//设置最大值
typedef struct{char vexs[MAXSIZE];//这里的数据类型根据实际情况而定int arcs[MAXSIZE][MAXSIZE];//这里的数据类型根据实际情况而定int vexnum, arcnum;//图的当前顶点数和边数
}Graph;
int get_index(char* arr,char m)
{int i = 0;for(i = 0; i < MAXSIZE; i++){if(arr[i] == m)return i;}return -1;
}void CreatGraph(Graph* G)
{int i,j = 0;printf("请输入顶点和边的数量:>");scanf("%d%d",&G->vexnum,&G->arcnum);//把输入的值保存到图结构体中for(i = 0; i < G->vexnum; i++)//初始化邻接矩阵{for(j = 0; j < G->vexnum; j++){G->arcs[i][j] = 0;}}for(i = 0; i < G->vexnum; i++){printf("请输入每个顶点的值:>");getchar();//清除键盘缓存区的回车键scanf("%c", &G->vexs[i]);//把输入的值保存到顶点数组当中}for(i = 0; i < G->arcnum; i++)//有几条边，循环几次{char m,n;//用来接收两个顶点int j,k;//接收顶点的下标printf("请依次输入每一条边，格式为:ab >");getchar();scanf("%c%c",&m,&n);j = get_index(G->vexs,m);//得到输入的m的值，在顶点数组中的下标k = get_index(G->vexs,n);//得到输入的n的值，在顶点数组中的下标G->arcs[j][k] = 1;//给邻接矩阵对应的位置赋权值G->arcs[k][j] = 1;//因为是无向网，所以是对称的，给对称点赋相同值}}
//深度遍历创建的无向图
void DepthSearch(Graph G, int v, int*visited)//参数为创建的图，输入的值在数组中的下标，判断是否被访问过的数组
{int i = 0;visited[v] = 1;printf("%c", G.vexs[v]);for(i = 0; i < G.vexnum; i++)//遍历二维数组v行的每一列{if((G.arcs[v][i] == 1)&&(visited[i]!=1))//如果有边相连，而且该顶点还没有被访问过DepthSearch(G, i,visited);//递归搜索该顶点}
}
int main()
{Graph G;CreatGraph(&G);char input;int visited[MAXSIZE] = {0};//创建数组，用来判断某一个顶点是否被访问过printf("请输入搜索的起始点:>");getchar();scanf("%c",&input);DepthSearch(G, get_index(G.vexs, input),visited);return 0;}

 ２，使用邻接表表示的无向图深度优先遍历的实现

 同样以这个无向图为例：创建一个visited[]数组，用来判断某个顶点是否已经被访问过

代码与上面邻接矩阵也差不多，只是在条件判断时有所不同，这里不需要判断表结点是不是顶点的边，只需要判断表结点是不是空．具体代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 //最大顶点数
#define MAX_INT 32767//设置最大值
typedef struct TableNode{//表结点int index;//结点在数组中的下标struct TableNode* nextarc;int info;//权值}TNode;typedef struct{//头结点char data;TNode* firstarc;
}HNode;typedef struct{//整个无向网的结构体HNode* head;int vexnum,arcnum;
}Gragh;
int get_index(HNode* arr,char m)
{int i = 0;for(i = 0; i < MAXSIZE; i++){if(arr[i].data == m)return i;}return -1;
}void CreatGraph(Gragh* G)
{int i = 0;printf("请输入顶点和边的数量:>");scanf("%d%d",&G->vexnum,&G->arcnum);//把输入的值保存到图结构体中for(i = 0; i < G->vexnum; i++){printf("请输入每个顶点的值:>");getchar();//清除键盘缓存区的回车键scanf("%c", &G->head[i].data);//把输入的值保存到顶点数组当中G->head[i].firstarc = NULL;}for(i = 0; i < G->arcnum; i++)//有几条边，循环几次{char m,n;//用来接收两个顶点int j,k;//接收顶点的下标printf("请依次输入每一条边，格式为:ab >");getchar();scanf("%c%c",&m,&n);j = get_index(G->head,m);//得到输入的m的值，在顶点数组中的下标k = get_index(G->head,n);//得到输入的n的值，在顶点数组中的下标TNode* P1 = malloc(sizeof(TNode));P1->index = k;P1->nextarc = G->head[j].firstarc;G->head[j].firstarc = P1;//因为是无向图，所以还要建立一条反向的边TNode* P2 = malloc(sizeof(TNode));P2->index = j;P2->nextarc = G->head[k].firstarc;G->head[k].firstarc = P2;}}
//深度遍历创建的无向图
void DepthSearch(Gragh G, int v, int*visited)//参数为创建的图，输入的值在数组中的下标，判断是否被访问过的数组
{visited[v] = 1;printf("%c", G.head[v].data);TNode* P = G.head[v].firstarc;while(P){if(!visited[P->index])DepthSearch(G, P->index, visited);//如果表结点不为空且判断数组值不为１，则递归搜索该结点P = P->nextarc;//指针指向该结点的下一个结点}}
int main()
{Gragh G;CreatGraph(&G);char input;int visited[MAXSIZE] = {0};//创建数组，用来判断某一个顶点是否被访问过printf("请输入搜索的起始点:>");getchar();scanf("%c",&input);DepthSearch(G, get_index(G.head, input),visited);return 0;}

二:广度优先遍历（ＢＦＳ） 

方法：从图的某一结点出发，首先依次访问该结点的所有邻接点，再按这些顶点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止．

根据广度优先的特点，和以前树的层次遍历比较相似，这里我们也采用队列的方式，把要访问的顶点先入队，访问完后，再出队，这样不停的循环，直到队列为空，就表示遍历完成了．

１，使用邻接矩阵表示的无向图广度优先遍历的实现

这里为了代码的简洁和可读性，我把常用的一些代码，创建无向图和队列，都放到头文件中去了

如果有需要，可以私信．创建无向图和队列的代码在前面的文章里都有．这里只是重点讲广度优先遍历的算法

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10 //最大顶点数
#include "gragh.h"
//广度优先遍历创建的无向图
void BreadthSearch(Gragh G, int v, int*visited, SQ* Q)//参数为创建的图，输入的值在数组中的下标，判断是否被访问过的数组，以及队列
{visited[v] = 1;//把传入的起点，设置为１push_sq(Q, G.head[v]);//把传入的顶点入队while(Q->back != Q->front)//如果队不为空，则循环{printf("%c", Q->arr[Q->front].data);//访问队列最前面的数据TNode* P = Q->arr[Q->front].firstarc;//把指针指向顶点对应的第一个表结点while(P)//只要表结点不为空就循环{if(!visited[P->index])push_sq(Q, G.head[P->index]);//把没有访问过的顶点入队列visited[P->index] = 1;//把入了队列的顶点，在visited数组中设置为１P = P->nextarc;//指针指向下一条边}pop_sq(Q);}
}
int main()
{SQ Q;//队列类型变量Gragh G;//图类型变量CreatGraph(&G);//创建一个无向图InitSQ(&Q);//创建并初始化一个顺序队列char input;int visited[MAXSIZE] = {0};//创建数组，用来判断某一个顶点是否被访问过printf("请输入搜索的起始点:>");getchar();scanf("%c",&input);BreadthSearch(G, get_index(G.head, input),visited,&Q);//广度优先遍历无向图return 0;}

邻接表不唯一，根据你创建算法，头插法，尾插法不同，而不同

邻接矩阵是唯一的，所以用邻接矩阵创建的图，遍历出来的结果都一样． 

邻接矩阵的广度遍历，和邻接表的差不多，这里就不详细说了！

_____________________________________

最近老是有人问我上面代码里.h和.c文件的内容，我现在发出来

gragh.h:

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10 //最大顶点数
typedef struct TableNode{//表结点int index;//结点在数组中的下标struct TableNode* nextarc;int info;//权值
}TNode;typedef struct{//头结点char data;TNode* firstarc;
}HNode;typedef struct{//整个无向网的结构体HNode* head;int vexnum,arcnum;
}Gragh;
typedef struct SequenceQueue//定义一个队列类型结构体
{HNode* arr;//定义一个数组，类型自己决定int front;//队列头指针（下标）int back;//队列尾指针（下标）
}SQ;
int get_index(HNode* arr,char m);
void CreatGraph(Gragh* G);
void InitSQ(SQ* Q);//创建并初始化一个队列
void push_sq(SQ* Q, HNode e);//插入规则，从队尾插入
void pop_sq(SQ* Q);//删除规则，从队头删除
int length_sq(SQ* Q);

gragh.c:

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10 //最大顶点数
#define MAX_INT 32767//设置最大值
#include "gragh.h"
int get_index(HNode* arr,char m)
{int i = 0;for(i = 0; i < MAXSIZE; i++){if(arr[i].data == m)return i;}return -1;
}void CreatGraph(Gragh* G)
{int i = 0;printf("请输入顶点和边的数量:>");scanf("%d%d",&G->vexnum,&G->arcnum);//把输入的值保存到图结构体中for(i = 0; i < G->vexnum; i++){printf("请输入每个顶点的值:>");getchar();//清除键盘缓存区的回车键scanf("%c", &G->head[i].data);//把输入的值保存到顶点数组当中G->head[i].firstarc = NULL;}for(i = 0; i < G->arcnum; i++)//有几条边，循环几次{char m,n;//用来接收两个顶点int j,k;//接收顶点的下标printf("请依次输入每一条边，格式为:ab >");getchar();scanf("%c%c",&m,&n);j = get_index(G->head,m);//得到输入的m的值，在顶点数组中的下标k = get_index(G->head,n);//得到输入的n的值，在顶点数组中的下标TNode* P1 = malloc(sizeof(TNode));P1->index = k;P1->nextarc = G->head[j].firstarc;G->head[j].firstarc = P1;//因为是无向图，所以还要建立一条反向的边TNode* P2 = malloc(sizeof(TNode));P2->index = j;P2->nextarc = G->head[k].firstarc;G->head[k].firstarc = P2;}
}void InitSQ(SQ* Q)//创建并初始化一个队列
{Q->arr = (TNode*)malloc(sizeof(TNode)*MAXSIZE);//定义一个10个整型大小空间的数组Q->front = Q->back = 0;//队列置空}
void push_sq(SQ* Q, HNode e)//插入规则，从队尾插入
{if((Q->back+1)%MAXSIZE == Q->front)//判断队列是否满{printf("error!,队列已经满了！");}else{Q->arr[Q->back] = e;Q->back = (Q->back + 1)%MAXSIZE;}
}
void pop_sq(SQ* Q)//删除规则，从队头删除
{if(Q->front == Q->back)//判断队列是否空{printf("error!,队列已经空了！");}else{HNode tmp = Q->arr[Q->front];Q->front = (Q->front + 1)%MAXSIZE;return;}
}
int length_sq(SQ* Q)
{return (Q->back - Q->front + MAXSIZE)%MAXSIZE;
}


http://chatgpt.dhexx.cn/article/GVJR2iJJ.shtml

相关文章

使用SSM框架上传图片

使用SSM框架上传图片

使用SSM框架上传图片 为了大家方便对照,我上传源码到网盘,有兴趣的自取. ps:其中有一个存储数据的网页,我没删除,可以忽略 链接&#xff1a;https://pan.baidu.com/s/1u24E8mUs4K-raoQgx-ae2A 提取码&#xff1a;java 建数据表 CREATE DATABASE my_resource;USE my_resource…
阅读更多...
SSM框架简单介绍

SSM框架简单介绍

一. SSM框架简介及特征 1.SpringMVC Spring MVC属于SpringFrameWork的后续产品&#xff0c;已经融合在Spring Web Flow 里面。Spring 框架提供了构建 Web 应用程序的全功能 MVC 模块。使用 Spring 可插入的 MVC 架构&#xff0c;从而在使用Spring进行WEB开发时&#xff0c;可…
阅读更多...
SSM框架整合详细教程

SSM框架整合详细教程

目录 1. 什么是SSM&#xff1f; 2. SSM整合的时候容器之间如何访问 3. SSM下面的开发步骤 4. SSM整合时候时容易混乱的知识点 1. 什么是SSM&#xff1f; SSM是对三个框架名字的简写&#xff0c;其中第一个S指的是SpringMVC,第二个S指的是Spring&#xff0c;第三个M指的是M…
阅读更多...
SSM框架理解

SSM框架理解

一、作用&#xff1a; 1、 SSM是spingspringMVCmybatis集成的框架。是标准的MVC模式&#xff0c;将整个系统划分为表现层&#xff0c;controller层&#xff0c;service层&#xff0c;DAO层四层。 2、使用spring MVC负责请求的转发和视图管理&#xff0c;spring实现业务对象管理…
阅读更多...
SSM框架初探

SSM框架初探

SSM 框架初探 SSM框架简介对框架的理解为什么使用 SSM 框架 SpringSpringMVCMybatis SSM框架简介 SSM框架一种以java语言作为后端搭建基本语言的应用系统搭建框架。是继SSH(strutsspringhibernate)之后&#xff0c;目前较为主流的Java EE企业级框架&#xff0c;适用于搭建各种大…
阅读更多...
SSM框架整合

SSM框架整合

今天来整合一下SSM三大框架~~ 1、创建一个maven项目 比较简单就不赘述了&#xff0c;创建的时候选择webapp骨架。 用骨架创建的项目&#xff0c;在创建完之后要更新一下web.xml 模板目录&#xff1a;“你的Tomcat安装目录\webapps\ROOT\WEB-INF\web.xml” 2、项目整体结构 按…
阅读更多...
SSM框架原理

SSM框架原理

SSM框架是spring MVC &#xff0c;spring和mybatis框架的整合&#xff0c;是标准的MVC模式&#xff0c;将整个系统划分为表现层&#xff0c;controller层&#xff0c;service层&#xff0c;DAO层四层 使用spring MVC负责请求的转发和视图管理 spring实现业务对象管理&#xff…
阅读更多...
SSM框架总结

SSM框架总结

一&#xff1a;什么是SSM框架&#xff1f; SSM框架是Spring、SpringMVC和MyBatis框架的总结&#xff0c;是比较标准的MVC模式。 标注的SSM框架有四层&#xff1a;dao&#xff08;mapper&#xff09;层、service层、controller层、domain(entity)层。 使用Spring实现业务对象…
阅读更多...
SSM框架详解

SSM框架详解

SSM框架详解 写在前面&#xff1a;当初整理SSM原理时&#xff0c;参考了网上一些前辈的文章&#xff0c;时间久远已经忘记来源&#xff0c;所以文中原理部分如有侵权请联系我删除。 基于SSM框架的仿天猫商城网站电商后台管理系统 本文视频讲解 文章目录 SSM框架详解 一、项…
阅读更多...
java ssm框架论文,ssm框架理解

java ssm框架论文,ssm框架理解

文章简介： SSM框架集简介 spring框架IOC的理解 mybatis框架sqlSessionFactory理解 Tomcat的理解 图解SSM SSM框架常用注解 1.SSM框架集简介 SSM(Spring+SpringMVC+MyBatis)框架集由Spring、MyBatis两个开源框架整合而成(SpringMVC是Spring中的部分内容)。常作为数据源较简单的…
阅读更多...
SSM框架详细讲解

SSM框架详细讲解

SSM框架 文章目录 SSM框架&#xff08;白痴都看完都会&#xff09;介绍SSM框架<原理>一、什么是SSM框架&#xff1f; 1.Spring2.Spring MVC3.Mybatis &#xff08;核心是SqlSession&#xff09;二、代码实战 1.创建配置工程2.代码实战&#xff08;查询记录数&#xff0…
阅读更多...
SSM三大框架超详细总结(适合你重新回顾)

SSM三大框架超详细总结(适合你重新回顾)

目录 1.1 概念 1.2 Mybatis优点 1.3 Mybatis架构 1.4 底层原理 1.5 Mybatis缓存 1.6 常见面试题 2.1 概念 2.2 Spring优点 2.3 Spring架构 2.4 控制反转&#xff08;IOC&#xff09; 2.5 DI依赖注入 2.6 底层原理(常见面试题) 8、如何用基于 Java 配置的方式配置 Spring&#…
阅读更多...
SSM框架整合思想及步骤

SSM框架整合思想及步骤

前言 SSM框架即是将SpringMVC框架、Spring框架、MyBatis框架整合使用。以简化在web开发中繁琐、重复的操作&#xff0c;让开发人员的精力专注于业务处理的开发上。 一、SSM框架的思想 ssm框架根据SpringMVC、Spring、MyBatis三者各自的特性及应用场景对其操作的的业务进行了分…
阅读更多...
SSM框架简介

SSM框架简介

一、Java SSM框架的概念 Java SSM框架即指SpringSpringMVCMyBatis的简称&#xff0c;框架集由Spring、MyBatis两个开源框架整合而成&#xff08;SpringMVC是Spring中的部分内容&#xff09;,常作为数据源较简单的web项目的框架。 相比于之前的SSH&#xff08;SpringStrutsHibe…
阅读更多...
SSM框架讲解（史上最详细的文章）

SSM框架讲解（史上最详细的文章）

SSM框架&#xff08;白痴都看完都会&#xff09; 文章目录 SSM框架&#xff08;白痴都看完都会&#xff09;介绍SSM框架<原理>一、什么是SSM框架&#xff1f;1.Spring2.Spring MVC3.Mybatis &#xff08;核心是SqlSession&#xff09; 二、代码实战1.创建配置工程2.代码实…
阅读更多...
MySQL安装教程(超详细教程)

MySQL安装教程(超详细教程)

MySQL详细安装步骤 - windows(MySQL Installer for Windows)附链接 1.下载所需要的版本(可自选&#xff0c;5.7.29为稳定版本)下载链接&#xff0c;运行程序 2.个人学习使用server only&#xff0c;如果不确定需求&#xff0c;则选择full&#xff0c;全部安装&#xff1b;Next …
阅读更多...
Mysql详细安装教程

Mysql详细安装教程

&#x1f973;&#x1f973;&#x1f973; 茫茫人海千千万万&#xff0c;感谢这一刻你看到了我的文章&#xff0c;感谢观赏 &#x1f60f;。 &#x1f449; 作者简介&#xff1a;最爱吃鱼罐头。(抱歉&#xff0c;我真的吃鱼罐头&#x1f92b;) &#x1f97a; 本人不才&#xff…
阅读更多...
【MySQL】免安装版MySQL安装教程

【MySQL】免安装版MySQL安装教程

前言 近日&#xff0c;重新安装了一下本地的数据库&#xff0c;参考了很多博客才将MySQL给安装好&#xff0c;为了方便以后安装&#xff0c;便结合了网上博客的安装方法以及自己的一些经验写下这篇博客&#xff0c;也希望能给你们带来帮助。 一、MySQL是什么&#xff1f; My…
阅读更多...
MySQL 8.0.32安装教程

MySQL 8.0.32安装教程

目前&#xff0c;主流关系型数据库管理系统&#xff1a;Oracle&#xff08;收费的数据库&#xff0c;价钱较昂贵&#xff0c;但是除了提供软件还提供相应服务&#xff09;、MySQL&#xff08;中小型数据库&#xff0c;开源的社区版和收费版&#xff09;、Microsoft SQL server&…
阅读更多...
mysql安装教程5.1_mysql 5.1安装教程详解

mysql安装教程5.1_mysql 5.1安装教程详解

1. 下载的mysql安装文件&#xff0c;运行 mysql-5.1.62&#xff0c;出现如下界面&#xff1b; 2. 向导启动&#xff0c;按Next继续&#xff0c;有三个选项&#xff0c;我们选择用户自定义“Custom”&#xff0c;有更多的选项&#xff0c;也方便熟悉整个安装过程&#xff1b;…
阅读更多...
推荐文章

Copyright @ 2022~2023