数据结构--图的深度优先搜索，广度优先搜索，生成树的边集

时间：2022-12-22 12:33:39

一、 实验目的

树和图是两种应用极为广泛的数据结构，也是这门课程的重点。它们的特点在于非线性。 稀疏矩阵的十字链表存储结构也是图的一种存储结构。本章实验继续突出了数据结构加操作的程序设计观点，但根据这种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其它众多操作的基础。遍历逻辑的（或符号形式的）结构，访问动作可是任何操作。本次实验希望帮助学生熟悉各种存储结构的特征，以及如何应用图结构解决具体问题（即原理与应用的结合）。

 

二、 实验内容

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）



标签：

相关文章