图的遍历-BFS广度优先搜索(C++)

解题思路:

#include<iostream>
using namespace std;
#define MAX_VERTEX_NUM 50 // 定义最大结点数;
#define MAXQSIZE 100 // 最大队长;
int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 构造空邻接矩阵;
int visited[MAX_VERTEX_NUM]; // 构造访问数组;
int u;

typedef struct // 队列的顺序存储结构;
{
	int* base; // 存储空间的基地址;
	int front; // 头指针;
	int rear; // 尾指针;
}SqQueue;

SqQueue Q;

int InitQueue(SqQueue& Q)
{
	Q.base = new int[MAXQSIZE]; // 为队列分配一个最大容量为MAXQSIZE的数组空间;
	if (!Q.base) exit(0); // 存储分配失败;
	else
	{
		Q.front = Q.rear = 0; // 头指针和尾指针指向队头，置空;
		return 1;
	}
}
int EnQueue(SqQueue& Q, int e) //入队(队尾入队)
{
	if ((Q.rear + 1) % MAXQSIZE == Q.front) // 判断队列是否已满，如果尾指针+1模MAX==头指针，说明队满;
		return 0;
	else
	{
		Q.base[Q.rear] = e; // 入队;
		Q.rear = (Q.rear + 1) % MAXQSIZE; // 队尾指针+1(若溢出，返回队头);
		return 1;
	}
}
int DeQueue(SqQueue& Q, int& e) // 出队(队头出队)
{
	if (Q.front == Q.rear)// 如果队空，不用出队;
		return 0;
	else
	{
		e = Q.base[Q.front];
		Q.front = (Q.front + 1) % MAXQSIZE;
		return e;
	}
}
int QueueEmpty(SqQueue Q)
{
	if (Q.front == Q.rear)
		return 1;
	else
		return 0;
}


int FirstAdjVex(int v, int n) // 返回u的第一个邻接点;
{
	for (int i = 0; i < n; i++)
	{
		if (graph[v][i] == 1 && !visited[i])
		{
			return i;
		}
	}
	return -1; // 如果找不到下一个邻接点，返回-1
}
int NextAdjVex(int v, int w, int n) // 返回u相对w的下一个邻接点;
{
	for (int i = w + 1; i < n; i++)
	{
		if (graph[v][i] == 1 && !visited[i])
		{
			return i;
		}
	}
	return -1; 
}


void BFS(int v,int n)
{
	cout << v << " "; // 输出访问的结点;
	visited[v] = 1; // 对于访问过的结点，令访问数组值为1;
	InitQueue(Q); // 初始化辅助队列Q，并置空;
	EnQueue(Q, v); // 访问过的结点v入队;
	while (!QueueEmpty(Q)) // 如果队列非空;
	{
		DeQueue(Q, u); // 队头元素出队并置为u;
		for (int w = FirstAdjVex(u,n); w >= 0; w = NextAdjVex(u, w,n)) // 依次检查u的所有邻接点w,FirstAdjVex()表示u的第一个邻接点，NextAdjVex()表示u相对于w的下一个邻接点,w>=0表示存在邻接点(V0,V1,V2,V3);
		{
			if (!visited[w])
			{
				cout << w<<" ";
				visited[w] = 1;
				EnQueue(Q, w);
			}
		}
	}
}

int main()
{
	int n;
	cin >> n; // 输入结点总数;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> graph[i][j]; // 构造邻接矩阵;
		}
	}
	for (int i = 0; i < n; i++)
		visited[i] = 0; // 初始化访问数组(令其所有值为0);

	BFS(0, n);

	return 0;
}

注意事项:

参考代码: