数据结构与算法王卓-习题-第六章图-采用邻接矩阵表示图的广度优先搜索遍历

目录

算法描述

算法预期效果

重难点

个人解法

总结

测试样例与输出

---

算法描述

创建图的邻接矩阵, 并输出bfs广度优先搜索遍历结果

算法预期效果

依次输入顶点数，边数，顶点V1~Vn，边A1~An，根据输入的顶点与边的关系，输出形如右边的邻接矩阵，接着使用BFS进行广度优先遍历，输出所有结点。

效果一：输出形如右边的邻接矩阵

效果二：输出类似右下角的遍历结果

重难点

使用非递归的结构，如何有序且不重复的遍历结点；visited数组如何声明与引用

个人解法

#include 
using namespace std;
#define MVNum 100

typedef struct {
	char *base;
	int front, rear, size;
}Queue;   //队列

typedef struct {
	char vexs[MVNum];
	int arcs[MVNum][MVNum];
	int vexnum,arcnum;
}AMGraph; //adjacency matrix graph

void InitQueue(Queue &Q, int n) {
	Q.base = new char[n];
	if (!Q.base) exit(-1);
	Q.front = Q.rear = 0; Q.size = n;
}         //队列初始化

void inq(Queue &Q, char e){
	if ((Q.rear + 1) % Q.size == Q.front) exit(-1);
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear + 1) % Q.size;
}         //入队

void outq(Queue &Q, char &e) {
	if (Q.front == Q.rear) exit(-1);
	e = Q.base[Q.front];
	Q.front = (Q.front + 1) % Q.size;
}         //出队

int Searchvex(AMGraph A, char n) {
	for (int i = 0; i < A.vexnum; i++) 
		if (n == A.vexs[i])
			return i;
	return -1;
}         //根据元素n，得到其在A.vex定点表中对应的下标

void CreateUDG(AMGraph &A) {
	char a, b;
	cout << "creating undigraph(1/4): how many vertices do you have in this AMG?\n";
	cin >> A.vexnum;
	cout << "creating undigraph(2/4): how many arcs do you have in this AMG?\n";
	cin >> A.arcnum;
	for (int i = 0; i < A.vexnum; i++) {
		cout << "creating undigraph(3/4): Please Enter the vertex NO. " << i + 1 << endl;
		cin >> A.vexs[i];
	}
	cout << "creating undigraph(4/4): Initializing the Adjacency Matrix" << endl;
	for (int i = 0; i < A.vexnum; i++)
		for (int j = 0; j < A.vexnum; j++)
			A.arcs[i][j] = 0;
	for (int i = 0; i < A.arcnum; i++) {
		cout << "creating undigraph(4/4): Please Enter the arcs No. " << i + 1 <> a >> b;
		int row = Searchvex(A, a);
		int col = Searchvex(A, b);
		A.arcs[row][col] = A.arcs[col][row] = 1;
	}
	cout << "undigraph created!"<< endl;
}         //创建无向图的邻接矩阵

void AMshow(AMGraph A) {
	cout << "showing Adjacency Matrix..."<< endl; 
	for (int i = 0; i < A.vexnum; i++) 
		for (int j = 0; j < A.vexnum; j++) {
			if (j) {
				cout << A.arcs[i][j] << " ";
			}
			else {
				cout << endl;
				cout << A.arcs[i][j] << " ";
			}
		}
	cout << "complete" << endl;
}         //打印无向图的邻接矩阵

int Firstadjvex(AMGraph A, char &e) {
	int v = Searchvex(A, e);
	for (int i = 0; i < A.vexnum; i++) {
		if (A.arcs[v][i])
			return i;
	}
	return -1;
}         //与e相邻的第一个顶点

int Nextadjvex(AMGraph A, char &e, char w) {
	int v = Searchvex(A, e);
	for (int i = 0; i < A.vexnum; i++) {
		if (A.arcs[v][i] == 1 && A.vexs[i] != w)
			if (i < Searchvex(A, w)) continue; //单向向后遍历，小于号用于保证不重复
			else return i;
	}
	return -1;
}         //与e相邻的w之后的下一个顶点

void BFS(AMGraph A, Queue &Q,int *&vst) {
	InitQueue(Q, A.vexnum); int w; char e;
	cout << A.vexs[0] << "→" ;
	inq(Q, A.vexs[0]); vst[0] = 1;
	while (Q.front != Q.rear) {
		outq(Q,e);
		for (w = Firstadjvex(A, e); w >= 0; w = Nextadjvex(A, e, A.vexs[w])) 
			if (vst[w] == 0) {
				cout << A.vexs[w] << "→";
				inq(Q, A.vexs[w]);
				vst[w] = 1;
			}
	}
	cout << "end";
}         //广度优先搜索

int main(){
	AMGraph a; Queue q;
	CreateUDG(a);
	AMshow(a);
	int n = a.vexnum;
	int *b = new int [n];
	for (int i = 0; i < a.vexnum; i++)
		b[i] = 0;
	cout << "showing BFS search result..." << endl;
	BFS(a, q, b);
	return 0;
}

总结

遇到问题：花了一下午去理解为什么能自动跳转到下一个结点？

解决方法：我在nextadjvex（寻找下一个结点）中，在i遍历到最后一个时（遍历完了）为了跳转到新结点，加了一些跳转语句，结果从来没运行过，但算法每次结果都正确。

。

我第一次为了让算法出错，找千奇百怪的例子，但都能通过。

。

琢磨了一下午为什么能自动跳转节点，发现虽然nextadjvex名为寻找下一个结点，且在for中作为w的推动方式，但别忘了for是在while的大前提下，while会自动推进队列，只要for找到了某个节点，该节点就会入队，根据新的入队结点改变w，而不是w只能由nextadjvex推进。

。

我真的好笨呜呜呜呜呜呜呜呜呜，写出答案还不知道对

测试样例与输出