数据结构——图结构基本操作的实现课程名称：数据结构

101 阅读 0 评论 67 点赞

我是靠谱客的博主务实小笼包，这篇文章主要介绍数据结构——图结构基本操作的实现课程名称：数据结构，现在分享给大家，希望可以做个参考。

课程名称：数据结构

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

实验目的：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#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;
}