我是靠谱客的博主 务实小笼包,最近开发中收集的这篇文章主要介绍数据结构——图结构基本操作的实现课程名称:数据结构,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

课程名称:数据结构

 

实验项目名称:图结构基本操作的实现

 

实验目的:

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;
}

 

最后

以上就是务实小笼包为你收集整理的数据结构——图结构基本操作的实现课程名称:数据结构的全部内容,希望文章能够帮你解决数据结构——图结构基本操作的实现课程名称:数据结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(49)

评论列表共有 0 条评论

立即
投稿
返回
顶部