数据结构--图的深度优先搜索,广度优先搜索,生成树的边集
一、 实验目的
树和图是两种应用极为广泛的数据结构,也是这门课程的重点。它们的特点在于非线性。 稀疏矩阵的十字链表存储结构也是图的一种存储结构。本章实验继续突出了数据结构加操作的程序设计观点,但根据这种结构的非线性特点,将操作进一步集中在遍历操作上,因为遍历操作是其它众多操作的基础。遍历逻辑的(或符号形式的)结构,访问动作可是任何操作。本次实验希望帮助学生熟悉各种存储结构的特征,以及如何应用图结构解决具体问题(即原理与应用的结合)。
二、 实验内容
1) 图遍历的演示
[问题描述]
很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示无向图的遍历操作。
[基本要求]
以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。
[测试数据]
由学生依据软件工程的测试技术自己确定。注意测试边界数据,如单个结点。
[实现提示]
设图的结点不超过30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边输入一个图,每条边为一个数对,可以对边的输入顺序做出某种限制。注意,生成树的边是有向边,端点顺序不能颠倒。
三、 实验环境
Visual Studio 2013
Windows 10
#include<stdio.h>
#include<stdlib.h>
int visited[20];
typedef struct ArcNode{
int adjvex; //邻接点域
struct ArcNode * nextarc; //指向下一个邻接点的指针域
};
typedef struct VNode{ //表头节点
int data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[20];
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct{
int start;
int end;
}Arc;
Arc BSet[20]; //广度优先搜索生成的边的边集
Arc DSet[20]; //深度优先搜索生成的边的边集
int b = 0; //广度优先搜索边集的index
int d = 0; //深度优先搜索边集的index
void createGraph(ALGraph &G){
printf("请输入图的顶点的个数。\n");
scanf_s("%d", &G.vexnum);
printf("请输入图的边的个数。\n");
scanf_s("%d", &G.arcnum);
printf("请输入顶点的信息。\n");
for (int i = 0; i<G.vexnum; i++){
scanf_s("%d", &((G.vertices[i]).data));
G.vertices[i].firstarc = NULL;
}
printf("请输入边的信息\n");
int a, b;
for (int j = 0; j<G.arcnum; j++){
scanf_s("%d%d", &a, &b);
ArcNode* s = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = a;
s->nextarc = G.vertices[b].firstarc;
G.vertices[b].firstarc = s;
s = (ArcNode*)malloc(sizeof(ArcNode));
s->adjvex = b;
s->nextarc = G.vertices[a].firstarc;
G.vertices[a].firstarc = s;
}
printf("邻接表创建完成。\n");
}
//深度优先遍历
void DFS(ALGraph G, int i){
//以i为开始开始遍历
printf("%d ", i);
ArcNode *p,*q;
visited[i] = 1; //0为假,1为真
p = G.vertices[i].firstarc;
while (p){
if (!visited[p->adjvex]){
DSet[d].start = i;
DSet[d].end = p->adjvex;
d++;
DFS(G, p->adjvex);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph G){
int j, i;
printf("请输入从哪个点开始进行深度优先搜索。\n");
scanf_s("%d", &j);
printf("深度优先搜索遍历顺序为:");
// DSet[d] = j;
for (i = 0; i<G.vexnum; i++){
visited[i] = 0;
}
for (i = j; i<G.vexnum; i++){
if (!visited[i]){
DFS(G, i);
}
}
for (i = 0; i<j; i++){
if (!visited[i]){
DFS(G, i);
}
}
printf("\n");
}
void PrintDFTree(ALGraph G){
int i = 0;
printf("深度生成树的边集为:");
for (; i < G.vexnum - 1; i++){
printf("(%d,%d)\t",DSet[i].start,DSet[i].end);
}
printf("\n");
}
//广度优先遍历
typedef struct QNode{
int data;
struct QNode* next;
}QNode, *QuePtr;
typedef struct {
QuePtr front;
QuePtr rear;
}LinkQue;
int Init(LinkQue &Q){
Q.front = Q.rear = (QuePtr)malloc(sizeof(QNode));
if (!Q.front) return -1;
Q.front->next = NULL; //不要忘了把头结点的next手动定义为null
// printf("success in initializating.\n");
return 0;
}
int enQue(LinkQue &Q, int e){
QNode *p = (QNode*)malloc(sizeof(QNode));
if (!p) return -1;
p->data = e;
p->next = NULL; //别忘了null
Q.rear->next = p;
Q.rear = p;
return 0;
}
int deQue(LinkQue &Q, int &e){
if (Q.front == Q.rear){
printf("The queue is empty now.\n");
return -1;
}
QNode* p = Q.front->next; //Q.front 是一个没有存放任何东西的头结点
e = p->data;
//printf("The data is %d\n",e);
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front; //队列中只有一个元素的情况 先把rear挪到前面来 要不然删的话把rear也一起删掉了
free(p);
return 0;
}
void BFS(ALGraph G, int i){
printf("%d ", i);
visited[i] = 1;
LinkQue Q;
int e;
Init(Q);
enQue(Q, i);
while (Q.front != Q.rear){
deQue(Q, i);
ArcNode *p = G.vertices[i].firstarc;
while (p){
if (!visited[p->adjvex]){
printf("%d ", p->adjvex);
visited[p->adjvex] = 1;
enQue(Q, p->adjvex);
BSet[b].start = i;
BSet[b].end = p->adjvex;
b++;
}
p = p->nextarc;
}
}
}
void BFSTraverse(ALGraph G){
int i, j;
printf("请输入从哪个点开始进行广度优先搜索。\n");
scanf_s("%d", &j);
printf("广度优先搜索遍历顺序为:\n");
for (i = 0; i<G.vexnum; i++){
visited[i] = 0;
}
for (i = j; i<G.vexnum; i++){
if (!visited[i]){
BFS(G, i);
}
}
for (i = 0; i<j; i++){
if (!visited[i]){
BFS(G, i);
}
}
printf("\n");
}
void PrintBFTree(ALGraph G){
int i = 0;
printf("广度生成树的边集为:\n");
for (; i < G.vexnum - 1; i++){
printf("(%d,%d)\t", BSet[i].start, BSet[i].end);
}
printf("\n");
}
int main(){
ALGraph G;
createGraph(G);
DFSTraverse(G);
PrintDFTree(G);
BFSTraverse(G);
PrintBFTree(G);
getchar();
getchar();
return 0;
1. 程序总是在最后出现闪退,加了一个getchar()不行,继续加一个getchar()成功
2. 在最开始深度优先搜索的时候每次都不会输出第一个遍历的点,原因是在第一次进入DFS的时候,visited就已经被置为1,但是自己的输出错误的写在了if结构里面,这就导致了第一个遍历的点未被输出,最后将输出语句放在了一进入DFS的位置,运行成功。
3. 在保存生成树的边集的时候最初的想法是在进入DFS函数的时候依次保存起点,在结束DFS函数的时候依次保存终点,使用一个全局的index进行控制,但是运行出现内存访问冲突的错误,于是改变策略,起点为i,终点为p->advex。
4. 在最初的时候并不能够实现指定遍历的起点,于是在traverse函数里面使用两个并列有先后次序的for循环来实现。
5. 最初的时候审题错误,输入字母的节点,之后对应编号,出了一些小错误。其实按照题目要求应该是直接用编号来表示顶点。
运行结果
测试数据为 8 个节点,10条边。
顶点为 0,1,2,3,4,5,6,7
边为(0,1)(0,2)(1,3)(1,4)(2,5)(2,6)(3,7)(4,7)(5,7)(6,7)
上一篇: POJ-2251 Dungeon Master(三维空间BFS)
下一篇: 走迷宫(广搜做法)
推荐阅读
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
【数据结构】图的遍历——深度优先搜索DFS、广度优先搜索BFS
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索
-
图的深度优先搜索和广度优先搜索
-
图的深度优先搜索和广度优先搜索
-
go语言编程学习实现图的广度与深度优先搜索
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
[SDUT](2141)数据结构实验之图论一:基于邻接矩阵的广度优先搜索遍历 ---BFS(图)
-
无向图的邻接表遍历:深度优先搜索+广度优先搜索