C++实现图的深度优先遍历和广度优先遍历

article/2025/9/20 6:51:19

图的深度和广度优先遍历

  • 图的深度优先遍历
    • 1、算法思想
    • 2、邻接矩阵构造图
    • 3、邻接表构造图
  • 图的广度优先遍历
    • 1、算法思想
    • 2、邻接矩阵构造图
  • 参考

图的深度优先遍历

1、算法思想

  • （1）从图中的某个初始点 v 出发，首先访问初始点 v.
  • （2）选择一个与顶点 v 相邻且没被访问过的顶点 ver ，以 ver为初始顶点，再从它出发进行深度优先遍历。
  • （3）当路径上被遍历完，就访问上一个顶点的第 二个相邻顶点。
  • （4）直到所有与初始顶点 v联通的顶点都被访问。

举例：

  • 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。
  • 若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；
  • 然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，
  • 并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。
    在这里插入图片描述
1.从0开始，首先找到0的关联顶点32.由3出发，找到1；由1出发，没有关联的顶点。3.回到3，从3出发，找到2；由2出发，没有关联的顶点。4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。所以最后顺序是0,3,1,2,4

2、邻接矩阵构造图

#include <iostream>
#include <vector>using namespace std;#define VERTEXNUM 5void createGraph(vector<vector<int>>&edge, int start, int end);
void displayGraph(vector<vector<int>>&edge);
void DFS(vector<vector<int>>&edge , vector<int>& vertexStatusArr);
void DFScore(vector<vector<int>>&edge, int i, vector<int>& vertexStatusArr);int main(void) {//初始化邻接矩阵vector<vector<int>>edge(VERTEXNUM, vector<int>(VERTEXNUM, 0));//存放顶点的遍历状态，0：未遍历，1：已遍历  vector<int> vertexStatusArr (VERTEXNUM,0);cout << "after init: " << endl;displayGraph(edge);//创建图createGraph(edge, 0, 3);createGraph(edge, 0, 4);createGraph(edge, 3, 1);createGraph(edge, 3, 2);createGraph(edge, 4, 1);cout << "after create: " << endl;displayGraph(edge);//深度优先遍历DFS(edge, vertexStatusArr);return 0;
}
//创建图 
void createGraph(vector<vector<int>>&edge, int start, int end) {edge[start][end] = 1;
}
//打印存储的图
void displayGraph(vector<vector<int>>&edge) {int i, j;for (i = 0; i<VERTEXNUM; i++) {for (j = 0; j<VERTEXNUM; j++) {//printf("%d ", edge[i][j]);cout << edge[i][j] << " ";}cout << endl;}
}
//深度优先遍历
void DFS(vector<vector<int>>&edge, vector<int>& vertexStatusArr) {cout << "start BFT graph: " << endl;for (int i = 0; i<VERTEXNUM; i++) {DFScore(edge, i, vertexStatusArr);}cout << endl;
}
void DFScore(vector<vector<int>>&edge, int i, vector<int>& vertexStatusArr) {if (vertexStatusArr[i] == 1) {return;}cout << i << " ";vertexStatusArr[i] = 1;for (int j = 0; j<VERTEXNUM; j++) {if (edge[i][j] == 1) {DFScore(edge, j, vertexStatusArr);}}
}

在这里插入图片描述
设有n个点，e条边
邻接矩阵：矩阵包含n ^2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n^2)

3、邻接表构造图

#include <stdio.h>
#include <malloc.h>#define VERTEXNUM 5//存放顶点的邻接表元素  
typedef struct edge {int vertex;struct edge* next;
}st_edge;void createGraph(st_edge** edge, int start, int end);
void displayGraph(st_edge** edge);
void delGraph(st_edge** edge);
void DFT(st_edge** edge, int* vertexStatusArr);
void DFTcore(st_edge** edge, int i, int* vertexStatusArr);int main(void) {//动态创建存放边的指针数组   st_edge** edge = (st_edge**)malloc(sizeof(st_edge*)*VERTEXNUM);int i;for (i = 0; i<VERTEXNUM; i++) {edge[i] = NULL;}//存放顶点的遍历状态，0：未遍历，1：已遍历  int* vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);for (i = 0; i<VERTEXNUM; i++) {vertexStatusArr[i] = 0;}printf("after init:\n");displayGraph(edge);//创建图  createGraph(edge, 0, 3);createGraph(edge, 0, 4);createGraph(edge, 3, 1);createGraph(edge, 3, 2);createGraph(edge, 4, 1);printf("after create:\n");displayGraph(edge);//深度优先遍历 DFT(edge, vertexStatusArr);//释放邻接表占用的内存  delGraph(edge);edge = NULL;free(vertexStatusArr);vertexStatusArr = NULL;return 0;
}
//创建图 
void createGraph(st_edge** edge, int start, int end) {st_edge* newedge = (st_edge*)malloc(sizeof(st_edge));newedge->vertex = end;newedge->next = NULL;edge = edge + start;while (*edge != NULL) {edge = &((*edge)->next);}*edge = newedge;
}
//打印存储的图 
void displayGraph(st_edge** edge) {int i;st_edge* p;for (i = 0; i<VERTEXNUM; i++) {printf("%d:", i);p = *(edge + i);while (p != NULL) {printf("%d ", p->vertex);p = p->next;}printf("\n");}
}
//释放邻接表占用的内存 
void delGraph(st_edge** edge) {int i;st_edge* p;st_edge* del;for (i = 0; i<VERTEXNUM; i++) {p = *(edge + i);while (p != NULL) {del = p;p = p->next;free(del);}edge[i] = NULL;}free(edge);
}
//深度优先遍历 
void DFT(st_edge** edge, int* vertexStatusArr) {printf("start BFT graph:\n");int i;for (i = 0; i<VERTEXNUM; i++) {DFTcore(edge, i, vertexStatusArr);}printf("\n");
}void DFTcore(st_edge** edge, int i, int* vertexStatusArr) {if (vertexStatusArr[i] == 1) {return;}printf("%d ", i);vertexStatusArr[i] = 1;st_edge* p = *(edge + i);while (p != NULL) {DFTcore(edge, p->vertex, vertexStatusArr);p = p->next;}
}

在这里插入图片描述
邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）

图的广度优先遍历

1、算法思想

广度优先遍历( Breadth_First_Search) ，又称为广度优先搜索，简称BFS。

它的思想是：

  • 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，
  • 然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
  • 如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。
在这里插入图片描述

2、邻接矩阵构造图

#include <iostream>
#include <vector>
#include <queue>using namespace std;#define VERTEXNUM 5void createGraph(vector<vector<int>>&edge, int start, int end);
void displayGraph(vector<vector<int>>&edge);
void DFS(vector<vector<int>>&edge, vector<int>& vertexStatusArr);
void DFScore(vector<vector<int>>&edge, int i, vector<int>& vertexStatusArr);
void BFS(vector<vector<int>>&edge, vector<int>& vertexStatusArr);int main(void) {//初始化邻接矩阵vector<vector<int>>edge(VERTEXNUM, vector<int>(VERTEXNUM, 0));//存放顶点的遍历状态，0：未遍历，1：已遍历  vector<int> vertexStatusArr(VERTEXNUM, 0);cout << "after init: " << endl;displayGraph(edge);//创建图createGraph(edge, 0, 3);createGraph(edge, 0, 4);createGraph(edge, 3, 1);createGraph(edge, 3, 2);createGraph(edge, 4, 1);cout << "after create: " << endl;displayGraph(edge);//深度优先遍历//DFS(edge, vertexStatusArr);BFS(edge, vertexStatusArr);return 0;
}
//创建图 
void createGraph(vector<vector<int>>&edge, int start, int end) {edge[start][end] = 1;
}
//打印存储的图
void displayGraph(vector<vector<int>>&edge) {int i, j;for (i = 0; i<VERTEXNUM; i++) {for (j = 0; j<VERTEXNUM; j++) {//printf("%d ", edge[i][j]);cout << edge[i][j] << " ";}cout << endl;}
}//BFS
void BFS(vector<vector<int>>&edge ,vector<int>& vertexStatusArr) {queue<int>q;q.push(0);vertexStatusArr[0] = 1;int idx = 0;while (!q.empty()){idx = q.front();q.pop();cout << idx << " ";for (int j = 0; j< VERTEXNUM; j++) {if (edge[idx][j] == 1 && vertexStatusArr[j] == 0){q.push(j);vertexStatusArr[j] = 1;}}}cout << endl;
}

在这里插入图片描述

参考

1、https://blog.csdn.net/todd911/article/details/9191481
2、https://blog.csdn.net/weixin_42109012/article/details/94199335
3、https://blog.csdn.net/Strive_Y/article/details/81810012?utm_medium=distribute.pc_relevant.none-task-blog-BlogCfData-2.add_param_isCf&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCfData-2.add_param_isCf
4、https://blog.csdn.net/weixin_40953222/article/details/80544928?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.add_param_isCf&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.add_param_isCf


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

相关文章

深度优先遍历

深度优先遍历

1.先序序列为a,b,c,d 的不同二叉树的个数是 &#xff08;14&#xff09; 。 13 14 15 16 f&#xff08;n&#xff09;c(n 2n)/n1 2.在构建哈弗曼树时&#xff0c;要使树的带权路径长度最小&#xff0c;只需要遵循一个原则&#xff0c;那就是&#xff1a;权重越大的结点离树…
阅读更多...
图的遍历——深度优先遍历与广度优先遍历

图的遍历——深度优先遍历与广度优先遍历

目录 何谓遍历&#xff1f; 图的遍历特点 图的遍历方式 深度优先搜索 过程分析 案例分析&#xff1a; 算法的代码实现 测试案例&#xff1a; 测试结果如下&#xff1a; 遍历非连通图 算法复杂度分析 额外补充 广度优先搜索 过程分析 辅助队列 算法的代码实现 队…
阅读更多...
图的深度优先遍历和广度优先遍历

图的深度优先遍历和广度优先遍历

本文参考自《大话数据结构》 文章目录 定义图的存储结构邻接矩阵邻接表 图的遍历深度优先遍历邻接矩阵代码邻接表代码 广度优先遍历邻接矩阵邻接表 最小生成树最短路径算法 定义 图(Graph) 是由顶点的有穷非空集合和顶点之间边的集合组成&#xff0c;通常表示为G(V&#xff0…
阅读更多...
深度优先遍历和广度优先遍历

深度优先遍历和广度优先遍历

深度优先遍历和广度优先遍历 什么是 深度/广度 优先遍历&#xff1f; 深度优先遍历简称DFS&#xff08;Depth First Search&#xff09;&#xff0c;广度优先遍历简称BFS&#xff08;Breadth First Search&#xff09;&#xff0c;它们是遍历图当中所有顶点的两种方式。 这…
阅读更多...
图的遍历（深度优先搜索）

图的遍历（深度优先搜索）

1、深度优先搜索遍历过程 图的深度优先搜索(Depth First Search)&#xff0c;和树的先序遍历比较类似。 它的思想&#xff1a;假设初始状态是图中所有顶点均未被访问&#xff0c;则从某个顶点v出发&#xff0c;首先访问该顶点&#xff0c;然后依次从它的各个未被访问的邻接点出…
阅读更多...
图的遍历算法之深度优先遍历（DFS）(C++)

图的遍历算法之深度优先遍历（DFS）(C++)

图的深度优先遍历思想是&#xff1a; 从图中某结点出发&#xff0c;访问其某一相邻结点&#xff0c;再访问该结点的相邻结点&#xff0c;直至访问完所有的结点。 形象的比喻就是&#xff1a;一条路走到头&#xff0c;回头再走没走过的路。 可见&#xff0c;深度优先遍历是一…
阅读更多...
图的深度优先遍历

图的深度优先遍历

一 图遍历介绍 所谓图的遍历&#xff0c;即是对结点的访问。一个图有那么多个结点&#xff0c;如何遍历这些结点&#xff0c;需要特定策略&#xff0c;一般有两种访问策略。 1 深度优先遍历 2 广度优先遍历 二 深度优先遍历基本思想 图的深度优先搜索(Depth First Search…
阅读更多...
图的遍历 ——深度优先遍历

图的遍历 ——深度优先遍历

图的遍历 ——深度优先遍历 深度优先搜索&#xff08;Depth First Search&#xff0c;DFS&#xff09;是最常见的图搜索方法之一。 深度优先搜索沿着一条路径一直搜索下去&#xff0c;在无法搜索时&#xff0c;回退到刚刚访问过的节点。深度优先遍历是按照深度优先搜索的方式…
阅读更多...
二、图的遍历——深度优先遍历

二、图的遍历——深度优先遍历

深度优先遍历&#xff0c;也有称为深度优先搜索&#xff0c;简称为DFS。 深度优先遍历其实就是一个递归的过程&#xff0c;它从图中某个顶点ⅴ出发&#xff0c;访问此顶点&#xff0c;然后从V的未被访问的邻接点出发深度优先遍历图&#xff0c;直至图中所有和V有路径相通的顶点…
阅读更多...
图的遍历（深度优先遍历DFS，广度优先遍历BFS）以及Ｃ语言的实现

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

遍历的定义&#xff1a; 从已给的连通图中某一顶点出发&#xff0c;沿着一些边访遍图中所有的顶点&#xff0c;且使每个顶点仅被访问一次&#xff0c;就叫做图的遍历&#xff0c;它是图的基本运算&#xff0e; 一:深度优先遍历&#xff08;&#xff24;&#xff26;&#xff…
阅读更多...
使用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中的部分内容)。常作为数据源较简单的…
阅读更多...
推荐文章

Copyright @ 2022~2023