欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 20:26:11
...

一、 实验目的

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

 

二、 实验内容

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)