概述
课程名称:数据结构
实验项目名称:图结构基本操作的实现
实验目的:
1.掌握图的基本操作—遍历。
实验要求:
1、 分别用DFS和BFS的方法实现一个无向图的遍历。
实验过程:
1、 创建一个图(可用邻接矩阵或邻接表的方式进行存储);
2、 输入选项:0或1,0为DFS,1为BFS。
3、 分别输出DFS和BFS两种遍历序列;
实验报告中给出DFS和BFS两种遍历的算法代码。
实验结果:
输入顶点集:
1 2 3 4 5 6 7 8
输入边的集合:
1 2
1 3
2 4
2 5
4 8
5 8
3 6
3 7
6 7
输入:0(DFS)
输出:DFS遍历序列为:12485367
输入:1(BFS)
输出:BFS遍历序列为:12345678
实验分析:
1.简单分析DFS与BFS实现时用到的方法(DFS通过递归函数实现,用到栈的数据结构,BFS用到队列的数据结构);
2.列举调试运行过程中出现的错误并分析原因。
要求:
(1) 程序要添加适当的注释,程序的书写要采用缩进格式。
(2) 程序要具在一定的健壮性,即当输入数据非法时,程序也能适当地做出反应。
(3) 程序要做到界面友好,在程序运行时用户可以根据相应的提示信息进行操作。
简单的利用邻接链表存图 + 搜索(DFS、 BFS)
#include<bits/stdc++.h>
#define MaxInt 32767
#define MVNum 100
#define Status int
#define SElemType int
#define QElemType int
#define OK 1
#define ERROR 0
const int INF = 0x3f3f3f3f;
using namespace std ;
typedef int VerTexType;
typedef int ArcType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
LinkQueue Q;
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear = new QNode;
Q.front -> next = NULL;
return OK;
}
Status EnQueue(LinkQueue &Q, QElemType e){
QNode *p;
p = new QNode;
p -> data = e;
p -> next = NULL;
Q.rear -> next = p;
Q.rear = p;
return OK;
}
Status QueueEmpty(LinkQueue &Q){
if(Q.front == Q.rear) return 1;
else return 0;
}
Status DeQueue(LinkQueue &Q, QElemType e){
QNode *p;
if(Q.front == Q.rear) return ERROR;
p = Q.front -> next;
e = p -> data;
Q.front -> next = p -> next;
if(Q.rear ==p ) Q.rear = Q.front;
delete p;
return OK;
}
SElemType GetHead(LinkQueue Q){
if(Q.front != Q.rear)
return Q.front -> next -> data;
}
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum, arcnum;
}AMGraph;
AMGraph G;
Status CreateUDN (AMGraph &G){
int i, j;
cout << "输入顶点个数:" << endl;
cin >> G.vexnum;
cout << "输入边个数:" << endl;
cin >> G.arcnum;
cout << "输入顶点集:" << endl;
for(int i = 0; i < G.vexnum; i++)
cin >> G.vexs[i];
cout << "录入成功" << endl;
for(int i = 0; i < G.vexnum; i++){
for(int j = 0; j < G.vexnum; j++){
G.arcs[i][j] = 0;
}
}
cout << "初始化成功" << endl;
cout << "输入顶点关系集:" << endl;
int v1, v2;
for(int k = 0; k < G.arcnum; k++){
cin >> v1 >> v2;
G.arcs[v1][v2] = 1;
G.arcs[v2][v1] = G.arcs[v1][v2];
}
cout << "邻接矩阵构造成功" << endl;
return OK;
}
bool visited[MVNum];
void DFS_AM(AMGraph G, int v){
cout << v << " ";
visited[v] = true;
for(int w = 0; w < G.vexnum; w++){
if((G.arcs[v][G.vexs[w]] != 0) && (!visited[G.vexs[w]])){
DFS_AM(G,G.vexs[w]);
}
}
}
void BFS(AMGraph G, int v){
cout << v << " ";
visited[v] = true;
InitQueue(Q);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
int u = GetHead(Q);
DeQueue(Q, u);
for(int w = 0; w < G.vexnum; w++){
if((!visited[G.vexs[w]])){
cout << G.vexs[w] << " ";
visited[G.vexs[w]] = true;
EnQueue(Q,G.vexs[w]);
}
}
}
}
int main(){
CreateUDN(G);
memset(visited, false, sizeof(visited));
int te;
cout << "输入选项:0:DFS, 1:BFS, 其他: 结束程序" << endl;
cin >> te;
while(te == 0 || te == 1){
if(te == 0){
DFS_AM(G, G.vexs[0]);
cout << endl;
cout << "输入选项:0:DFS, 1:BFS, 其他: 结束程序" << endl;
cin >> te;
}
else if(te == 1){
BFS(G, G.vexs[0]);
cout << "输入选项:0:DFS, 1:BFS, 其他: 结束程序" << endl;
cin >> te;
}
else break;
memset(visited, false, sizeof(visited));
}
cout << "感谢使用" << endl;
return 0;
}
最后
以上就是务实小笼包为你收集整理的数据结构——图结构基本操作的实现课程名称:数据结构的全部内容,希望文章能够帮你解决数据结构——图结构基本操作的实现课程名称:数据结构所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复