[数据结构与算法]BFS广度优先遍历

其思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域。

也可以类似树的层次遍历

即用到队列来实现BFS

结点结构

? ? ? ? 图：

? ? ? ? ? ? ? ? 点集

? ? ? ? ? ? ? ? 边集

? ? ? ? ? ? ? ? 点数

? ? ? ? ? ? ? ? 边数

? ? ? ? 队列：

? ? ? ? ? ? ? ? 数据数组

? ? ? ? ? ? ? ? 长度

? ? ? ? ? ? ? ? 前后索引

方法

图的基本方法

循环队列的基本方法

BFS

初始化队列，先访问当前index下标的节点，并且设置visited数组为1（表示已访问），再入队

只要队列不为空，就进入循环，记录当前出队的结点下标，利用for循环在邻接矩阵里查找该（出队结点那一行）节点是否有孩子，若有孩子且没有被访问过，则访问它并设置visited数组，再入队，反复以上的操作即可

#include<iostream>
#include<string.h>
#define mymax 65535
using namespace std;
typedef struct Graph
{
	char* spot;
	int** line;
	int spotNum;
	int lineNum;
}Graph;
Graph* initGraph(int dianNum)
{
	Graph* G = new Graph;
	G->spot = new char[dianNum];
	G->line = new int* [dianNum];
	G->spotNum = dianNum;
	G->lineNum = 0;
	for (int i = 0; i < dianNum; i++)
	{
		G->line[i] = new int[dianNum];
	}
	return G;
}
void createGraph(Graph* G, const char* dian, int* bian)
{
	for (int i = 0; i < G->spotNum; i++)
	{
		G->spot[i] = dian[i];
		for (int j = 0; j < G->spotNum; j++)
		{
			G->line[i][j] = *(bian + i * G->spotNum + j);
			if (G->line[i][j] > 0 && G->line[i][j] < mymax)
			{
				G->lineNum++;
			}
		}
	}
	G->lineNum /= 2;
}
void visit(Graph* G, int index)
{
	cout << G->spot[index] << " ";
}
typedef struct Queue
{
	int* data;
	int length;
	int front;
	int rear;
}Queue;
Queue* initQueue(int len)
{
	Queue* q = new Queue;
	q->length = len;
	q->data = new int[len];
	memset(q->data, 0, len * sizeof(q->data));
	q->front = q->rear = 0;
	return q;
}
bool isFull(Queue* q)
{
	if ((q->rear + 1) % q->length == q->front)
		return 1;
	else
		return 0;
}
bool isEmpty(Queue* q)
{
	if (q->front == q->rear)
		return 1;
	else
		return 0;
}
int enQueue(Queue* q, int x)
{
	if (isFull(q))
		return 0;
	else
	{
		q->data[q->rear] = x;
		q->rear = (q->rear + 1) % q->length;
		return 1;
	}
}
int deQueue(Queue* q)
{
	if (isEmpty(q))
		return 0;
	else
	{
		int x = q->data[q->front];
		q->front = (q->front + 1) % q->length;
		return x;
	}
}
//先访问，再入队，将孩子入队
void BFS(Graph* G, int* visited, int index)
{
	Queue* q = initQueue(G->spotNum);
	visit(G, index);
	visited[index] = 1;
	enQueue(q, index);
	while (!isEmpty(q))
	{
		int i = deQueue(q);
		for (int j = 0; j < G->spotNum; j++)
		{
			if (G->line[i][j] == 1 && !visited[j])
			{
				visit(G, j);
				visited[j] = 1;
				enQueue(q, j);
			}
		}
	}
}
int main()
{
	char array[] = {'A','B','C','D','E'};
	int num = sizeof(array) / sizeof(char);
	Graph* G = initGraph(num);
	int bian[] = { 0,1,1,1,0,1,0,1,1,1,1,1,0,0,0,1,1,0,0,1,0,1,0,1,0 };
	int dianNumber = G->spotNum;
	int* visited = new int[dianNumber];
	memset(visited, 0, dianNumber * sizeof(visited));
	createGraph(G, array, bian);
	BFS(G, visited, 0);
	cout << endl;
}