SCNU_数据结构作业_实验5 图的算法与应用
2021/11/28 20:42:20
本文主要是介绍SCNU_数据结构作业_实验5 图的算法与应用,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、 邻接矩阵(验证实验【必做】)
以lab5_1.cpp为基础,参考课本180页-182页的内容,建立无向图的邻接矩阵存储结构,对建立的无向图进行深度优先遍历和广度优先遍历。请把答案代码直接补充在源文件中。课本178页图6-7的输入和输出样张如下图所示。
#include <iostream> using namespace std; const int MaxSize = 10; //图中最多顶点个数 int visited[MaxSize]={0};//对全局的点初始化,表示都没有被访问 template <class DataType> class MGraph { public: MGraph(DataType a[] , int n, int e); //构造函数,建立具有n个顶点e条边的图 ~MGraph( ){} //析构函数为空 void DFTraverse(int v); //深度优先遍历图 void BFTraverse(int v); //广度优先遍历图 private: DataType vertex[MaxSize]; //存放图中顶点的数组 int edge[MaxSize][MaxSize]; //存放图中边的数组 int vertexNum, edgeNum; //图的顶点数和边数 }; 补充1// //构造函数-图的建立 template <class DataType> MGraph<DataType>::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n; edgeNum = e; //存放顶点 for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; //初始化邻接矩阵 for(i = 0; i < vertexNum; i++) for(j = 0; j < vertexNum; j++) edge[i][j] = 0; //依次输入每一条边 for(k = 0; k < edgeNum; k++) { cout<< "请输入两个边的顶点序号:"; cin >>i >>j;//输入边依附的两个顶点的编号 edge[i][j] = 1; edge[j][i] = 1;//初始化边 } } //深度优先遍历 template <class DataType> void MGraph<DataType>::DFTraverse(int v) { cout <<vertex[v]; visited[v] = 1;//访问了的点,就改写为1,表示已经访问过了 for(int j = 0; j < vertexNum; j++) if(edge[v][j] == 1 && visited[j] == 0)//如果边存在,且点没被访问 DFTraverse(j); } //广度优先遍历 template <class DataType> void MGraph<DataType>::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] == 1 && visited[j] == 0)//如果边存在,点未被访问 { cout <<vertex[j];//输出点数据 visited[j] = 1;//表示已经访问 Q[++rear] = j;//推下一个进来 } } } // int main( ) { int i; char ch[]={'A','B','C','D','E','F'}; MGraph<char> MG(ch, 6, 6);//建立6个顶点,6条边的无向图 补充2// for(i = 0; i < MaxSize; i++) visited[i] = 0;//对每个点初始化未被访问 cout << "深度优先遍历序列是:"; MG.DFTraverse(0);//从顶点0出发进行深度优先遍历 cout << "\n"; for(i = 0; i < MaxSize; i++) visited[i] = 0; cout<< "广度优先遍历序列是:"; MG.BFTraverse(0);//从顶点0出发进行广度优先遍历 return 0; // }
太难了,完全是照着书本来,不然根本不会(捂脸)
磕磕碰碰,各种小错误,完全像新学一样,懵懵懂懂的,什么都不懂。
这篇关于SCNU_数据结构作业_实验5 图的算法与应用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享