首页 / C++ / 数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历

数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3593字，纯文字阅读大概需要6分钟。

内容图文

数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历 - 文章图片

C++ 非递归深度优先遍历

#include <iostream>
#include <malloc.h>
#include <stack> 
using namespace std;
const int MaxSize=6;//图中最多顶点个数
typedef string DataType;
int visited[MaxSize] = {0};//全局数组变量visited初始化 
class MGraph{
	public:
		MGraph();//构造函数 
		~MGraph(); 
		void DFTraverse(int v);
		void BFTraverse(int v);
	private:
		DataType vertex[MaxSize] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
		int edge[MaxSize][MaxSize] = {{0,34,46,INT_MAX,INT_MAX,19}, 
								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
								{46,INT_MAX,0,17,INT_MAX,25},
								{INT_MAX,INT_MAX,17,0,38,25},
								{INT_MAX,12,INT_MAX,38,0,26},
								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
		int vertexNum=MaxSize,edgeNum=MaxSize;
}; 

MGraph::MGraph(){
	
} 

MGraph::~MGraph(){

} 

void MGraph::DFTraverse(int v){//非递归深度优先遍历 
	stack<int> DF_stack;
	DF_stack.push(v);
	cout<<vertex[DF_stack.top()];
	visited[v]=1;
	for(int j=0;j<vertexNum;j++){
		if( visited[j] == 0 && (edge[v][j]!=INT_MAX && edge[v][j]!=0 )){
			cout<<vertex[j];
			visited[j]=1;
			v = j;
			DF_stack.push(j); 
			j=0;
		}
		if(j == vertexNum-1 ){
			DF_stack.pop();
		}
	}
}
int main(){
	int i;
	MGraph MG{};
	for(i=0;i<MaxSize;i++)
		visited[i]=0;
	cout<<"深度优先遍历序列是："<<endl;
	MG.DFTraverse(0);
	cout<<endl;
}

实验结果图：

数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历 - 文章图片

C++ 递归深度优先遍历

#include <iostream>
#include <malloc.h>
#include <stack> 
using namespace std;
const int MaxSize=6;//图中最多顶点个数
typedef string DataType;
int visited[MaxSize] = {0};//全局数组变量visited初始化 
class MGraph{
	public:
		MGraph();//构造函数 
		~MGraph(); 
		void DFTraverse(int v);
		void BFTraverse(int v);
	private:
		DataType vertex[MaxSize] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
		int edge[MaxSize][MaxSize] = {{0,34,46,INT_MAX,INT_MAX,19}, 
								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
								{46,INT_MAX,0,17,INT_MAX,25},
								{INT_MAX,INT_MAX,17,0,38,25},
								{INT_MAX,12,INT_MAX,38,0,26},
								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
		int vertexNum=MaxSize,edgeNum=MaxSize;
}; 

MGraph::MGraph(){
	
} 

MGraph::~MGraph(){

} 
 
void MGraph::DFTraverse(int v){//深度优先遍历 
	cout<<vertex[v];
	visited[v]=1;
	for(int j=0;j<vertexNum;j++)
		if(visited[j] == 0 && (edge[v][j]!=INT_MAX && edge[v][j]!=0 ))
			DFTraverse(j);
}

int main(){
	int i;
	MGraph MG{};
	for(i=0;i<MaxSize;i++)
		visited[i]=0;
	cout<<"深度优先遍历序列是："<<endl;
	MG.DFTraverse(0);
	cout<<endl;
}

实验结果图：

数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历 - 文章图片

C++广度优先遍历

#include <iostream>
#include <malloc.h>
#include <stack> 
using namespace std;
const int MaxSize=6;//图中最多顶点个数
typedef string DataType;
int visited[MaxSize] = {0};//全局数组变量visited初始化 
class MGraph{
	public:
		MGraph();//构造函数 
		~MGraph(); 
		void DFTraverse(int v);
		void BFTraverse(int v);
	private:
		DataType vertex[MaxSize] = {"v0", "v1", "v2", "v3", "v4", "v5"}; //存储顶点的一维数组 
		int edge[MaxSize][MaxSize] = {{0,34,46,INT_MAX,INT_MAX,19}, 
								{34,0,INT_MAX,INT_MAX,12,INT_MAX},
								{46,INT_MAX,0,17,INT_MAX,25},
								{INT_MAX,INT_MAX,17,0,38,25},
								{INT_MAX,12,INT_MAX,38,0,26},
								{19,INT_MAX,25,25,26,0}};  //邻接矩阵
		int vertexNum=MaxSize,edgeNum=MaxSize;
}; 

MGraph::MGraph(){
	
} 

MGraph::~MGraph(){

} 
 
void MGraph::BFTraverse(int v){//广度优先遍历 
	int w,j,Q[MaxSize];//采用顺序队列
	int front=-1,rear=-1;//初始化队列
	cout<<vertex[v];
	visited[v]=1;
	Q[++rear]=v;//被访问顶点入队
	while(front!=rear){
		w=Q[++front];//将队头元素出队并送到v中
		for(j=0;j<vertexNum;j++)
			if((edge[w][j]!=INT_MAX && edge[w][j]!=0 ) && visited[j] == 0){
				cout<<vertex[j];
				visited[j] = 1;
				Q[++rear] = j;
			} 
	} 
}

int main(){
	int i;
	MGraph MG{};
	for(i=0;i<MaxSize;i++)
		visited[i]=0;
	cout<<"广度优先遍历序列是："<<endl;
	MG.BFTraverse(0);
}

实验结果图：

数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历 - 文章图片

我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞+收藏+加关注喔~

如果文章有不正确的地方，欢迎交流指正，我将虚心请教~o(>ω<)o

我会定期更新文章，继续为您提供优质文章

内容总结

以上是互联网集市为您收集整理的数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历全部内容，希望文章能够帮你解决数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/607154.html

来源：【匿名】

【上一篇】C++并发与多线程(八) async、future、packaged_task、promise 【下一篇】c++有个库什么的吗?

更多 ►

【数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历】教程文章相关的互联网学习教程文章

c++数据结构 --unorder_map【代码】【图】

#include <iostream> #include <unordered_map> usingnamespace std; class Book { private:string num;string name; public:Book() {};Book(string num,string name) { this ->name = name;this ->num = num;};string getNum() { return num;};string getName() { return name;}; }; int main() {unordered_map<string,Book>lib;Book b("001","高级语言程序设计") ;lib[b.getNum()] = b;unordered_map<string,Book>::iterator it;...

noi题库（noi.openjudge.cn） 3.9数据结构之C++STL T1——T2【代码】【图】

T1 1806:词典描述你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是，你有一本词典可以帮助你。输入首先输入一个词典，词典中包含不超过100000个词条，每个词条占据一行。每一个词条包括一个英文单词和一个外语单词，两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行，然后给出一个由外语单词组成的文档，文档不超过100000行，而且每行只包括一个外语单词。...

【C/C++】实现数据结构广义表【代码】

1. 广义表的定义每个元素可以为Atom，原子，也可以为线性表。线性表的推广。线性表元素有唯一的前驱和后继，为线性表，而广义表是多层次的线性表表头：第一个元素，可能是原子，可能是广义表表尾：除了第一个元素，剩余的元素，所构成的广义表举例： A = (a,b,(c,d),e) head(A) = a tail(A) = (b,(c,d),e) 遍历操作：取表头，取表尾，取表头.. 长度：最外层的...

字符串数据结构算法题-C++【代码】

1）最长不重复子串使用string和vector<string>string FindLongestNonRepeatSubstring(string str) {if (str.empty()) return"";string tmp;//存放临时不重复的子串vector<string> svec;//存放所有不重复的子串int start = 0;//标记每次开始查找子串的下标int pos = -1; //查找当前字符在子串中的位置下标tmp.push_back(str[0]);for (unsigned int i = 1; i < str.size(); ++i){pos = tmp.find(str[i]);if (pos == -1){tmp.push_bac...

C++数据结构知识点【代码】【图】

数据结构(data stucture)的定义：数据结构由数据元素的集合和该集合中数据元素之间的关系组成。即{D,R}。线性结构，即线性表(linearlist). ---数组(array)，文件，栈(stack)，队列(queue)，优先级队列非线性结构 ---集合，图C++类默认访问级别是privatestruct默认访问级别是 public 这可以说是他们的惟一区别。union默认访问级别也是 public流是个简单的字符序列cout<<endl; 输出一个换行符，并清空流。C++的输入输出：void main...

【数据结构】3、模拟银行窗口排队叫号系统——C++【图】

这里我们模拟一下银行排队叫号系统的实现：假设一个银行有4个窗口对外接待客户。由于每个窗口在某一时刻只能接待一个客户，在客户众多的时候需要排队，对于刚进入银行的客户，如果某个窗口正空闲，则可上前办理业务，如果所有窗口都不空闲则排在人数最少的窗口。现在要求模拟银行的某一时间段内的4个窗口的客户排队情况。这里客户到达的时刻和办理业务的时间都是随机的。首先我们银行发生事件，我们得有一个类表示事件对象/* *功...

【C++/数据结构】单链表的基本操作【图】

#pragma once #ifndef _CLIST_H_ #define _CLIST_H_#include <iostream> #include <assert.h> using namespace std;template<class Type> class List;typedef enum { FALSE, TRUE }Status;template<class Type> class ListNode {friend class List<Type>; public:ListNode() :data(Type()), next(NULL){}ListNode(Type d, ListNode<Type> *n = NULL): data(d), next(n){}~ListNode(){}void setData(const Type &d){data = d;}Type ...

C++数据结构——队列【代码】【图】

C++数据结构——队列目录 1、简介 2、基本结构 3、基本操作简介像栈一样，队列也是一种线性表。它允许在表的一端插入数据，在另一端删除元素。插入元素的这一端称之为队尾。删除元素的这一端我们称之为队头，它的特点是先进先出。首先我们来思考一下队列这种数据结构使用什么表的创建方式比较好，是头插法？尾插法？之前我们有提到，队列在队头删除元素，在队尾插入元素，如果是头插法，那么在头结点这边进行插入，在另一边进行删除...

数据结构C++版-线性表【代码】【图】

PS：资料来源慕课网视频。一、什么是线性表线性表是n个数据元素的有限序列。分类：二、补充知识点1、栈和队列有出操作、入操作，对应线性表（数组）为插入元素和删除元素，而线性表中要获取指定元素值可直接使用getelem()函数，获取后并不删除元素，可重复获取。【与只能使用一次的栈、队列有区别】 2、顺序表：遍历和寻址非常快，插入、删除效率低。 3、《链表算法说明》课程评论：静态链表基于数组，动态链表基于结构体，所...

【C/C++】c/c++基础加进阶视频教程（含数据结构和设计模式）【图】

收集整理了c和c++从基础到进阶的视频教程，共26.4G，欢迎下载。至于学习c++要不要先学c的问题也是见仁见智，个人觉得在c语言的基础上学c++会更有效率一些。这套视频教程包含了c语言课程，麻油们可以根据自己的需要选择是否要先学c。创一个小群，供大家学习交流聊天如果有对学C++方面有什么疑惑问题的，或者有什么想说的想聊的大家可以一起交流学习一起进步呀。也希望大家对学C++能够持之以恒C++爱好群，如果你想要学好C++最好加入一...

C++八股文分享---数据结构其二---哈希表【代码】

C++八股文分享—数据结构其二—哈希表前言什么是哈希表？搜索二叉树对值的查找是通过从根节点开始，逐个节点与目标值做比较，向下查找，直至找到目标值或是到达根节点未查找到，时间复杂度为O(logn)。而哈希表，则是通过将value与key成对绑定，将key带入哈希函数，即可得到目标值的存放地址，从而得到目标值，在不考虑哈希冲突的情况下，时间复杂度为O(1)。哈希表其实可以理解为一个特殊的数组。我们通常使用的数组，通过下标0...

队列的C++数组实现方法(队列--数据结构)【代码】

队列的C++实现方法(队列–数据结构) 1.队列结构 #define MaxSize //储存数据元素的最大个数 struct QNode {ElementType Data[MaxSize];int rear;int front; }; typedef struct QNode *Queue; 2.入队列 void AddQ(Queue PtrQ, ElementType item) {if((PtrQ->rear+1)%MaxSize==Ptr->front){printf("队列满")；return;}PtrQ->rear=(PtrQ->rear+1)%MaxSize;PtrQ->Data[Ptr->rear]=item; } 3.出队列 ElementType DeleteQ(Queue PtrQ) {i...

数据结构c++ 排列组合（递归）【代码】

代码内容来自互联网视频 #include <iostream> using namespace std;template<class T> inline void swap1(T& a, T& b) {T t = a;a = b;b = t; }// "abc"的排列组合 void permutations(char p[], const int st, const int end) {if(st == end) // 输出排列组合结果{cout << p << endl;}else{for(int i=st; i<=end; i++) // 递归结束条件{swap1(p[st], p[i]);permutations(p, st+1, end);swap1(p[st], p[i]);}}// // a开头// swap1(...

C++STL中的常用的数据结构

STL中常用的数据结构： [1] stack、queue默认的底层实现为deque结构。 [2] deque：用map管理多个size大小的连续内存块，方便头尾插入。 [3] vector：变长动态数组，每次增大1.5倍，删除元素时不释放空间。 [4] priority_queue底层默认采用vector向量O(nlogn)。 [5] list：双向链表容器。 [6] slist：单向链表容器。 [7] bit_vector：一个bit位元素的序列容器，常用于硬件端口的控制。区别于vector<bool>重要特性是节省空间。...

C++数据结构之链式栈(二十)【代码】【图】

引用猎豹网校main.cpp #include <iostream> #include "LinkedStack.h"using namespace std;int main() {cout << "测试链式栈" << endl;LinkedStack<int> s;s.Push(10);cout << s.Top() << endl;s.Push(20);cout << s.Top() << endl;s.Push(30);cout << s.Top() << endl;s.Pop();cout << s.Top() << endl;return 0; }Linked Stack.h #ifndef LINKEDSTACK_H #define LINKEDSTACK_Htemplate<class T> class LinkedStack;template<clas...

首页 / C++ / 数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历

数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历

内容导读

内容图文

我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞+收藏+加关注喔~

内容总结

内容备注

内容手机端

【数据结构----C++实现非递归和递归的深度优先遍历和广度优先遍历】教程文章相关的互联网学习教程文章

数据结构 - 相关标签

递归 - 相关标签

C++ - 技术教程分类

C++ - 最新教程

C++ - 最热教程