数据结构学习笔记（C++）：邻接表实现图的存储结构(广度优先遍历详解)

广度优先遍历还没理解的小伙伴们看这里

代码骑士的一张图让你深刻理利用队列实现广度优先的奥秘：

输入样例：

0 1

0 2

0 3

1 3

3 2

输出样例：

示例代码：

#include

#define MAXSIZE 100

using namespace std;

//定义标记表
int visited[MAXSIZE] = { 0 };

//定义边表结点
struct EdgeNode
{
	int verSubscript;
	EdgeNode* next;
};
//定义顶点表结点
struct VertextNode
{
	char vertex;
	EdgeNode* edgeHead;
};

class adjacencyList
{
public:
	adjacencyList(char c[],int n,int e);
	~adjacencyList();
public:
	void depthTraverse(int v);
	void breadthTraverse(int v);
private:
	VertextNode vertexList[MAXSIZE];
	int vertextNum, edgeNum;
};

adjacencyList::adjacencyList(char c[],int n, int e)
{
	vertextNum = n;
	edgeNum = e;
	for (int i = 0; i < n; i++)
	{
		vertexList[i].vertex = c[i];
		vertexList[i].edgeHead = NULL;
	}

	EdgeNode* s = NULL;
	for (int k = 0; k < edgeNum; k++)
	{
		int i, j;
		cin >> i >> j;
		s = new EdgeNode;
		s->verSubscript = j;//注意边表中数据存的是下标
		s->next = vertexList[i].edgeHead;
		vertexList[i].edgeHead = s;
	}
}

adjacencyList::~adjacencyList()
{
	EdgeNode* p = NULL, * q = NULL;
	for (int i = 0; i < vertextNum; i++)
	{
		p = q = vertexList[i].edgeHead;
		while (p != NULL)
		{
			p = p->next;
			delete q;
			q = p;
		}
	}
}

void adjacencyList::depthTraverse(int v)
{
	//第一步：访问顶点表
	cout << vertexList[v].vertex; visited[v] = 1;
	//第二步：访问边表
	EdgeNode* p = NULL;
	p = vertexList[v].edgeHead;
	while (p != NULL)
	{
		int j = p->verSubscript;
		if (visited[j] == 0)
			depthTraverse(j);
		p = p->next;
	}
}

void adjacencyList::breadthTraverse(int v)
{
	//第一步：创建队列及其初始化
	int Q[MAXSIZE];
	int rear, front;
	rear = front = -1;
	//第二步：访问顶点及其入队
	cout << vertexList[v].vertex; visited[v] = 1;
	Q[++rear] = v;
	//第三步：访问边表及其出队
	EdgeNode* p = NULL;
	int temp,sub;
	while (rear != front)
	{
		temp = Q[++front];
		p = vertexList[temp].edgeHead;
		while (p != NULL)
		{
			sub = p->verSubscript;
			if (visited[sub] == 0)
			{
				cout << vertexList[sub].vertex;
				visited[sub] = 1;
				Q[++rear] = sub;
			}
			p = p->next;
		}
	}
}

int main()
{
	char ch[4] = { 'A','B','C','D' };
	int i;
	adjacencyList adj(ch, 4, 5);
	for (i = 0; i < MAXSIZE; i++)
		visited[i] = 0;
	cout << endl << "深度优先遍历：" << endl;
	adj.depthTraverse(0);
	for (i = 0; i < MAXSIZE; i++)
		visited[i] = 0;
	cout << endl << "广度优先遍历：" << endl;
	adj.breadthTraverse(0);
	return 0;
}