算法：图的遍历算法

?1.广度优先遍历（BFS）

算法思想

优先遍历与之接近的结点，把所有与之相连的遍历完再遍历下一层，因为队列遵循队头出，队尾入，故可以来利用队列的结构实现该算法

eg：?

?

?

?代码实现

#include <stdbool.h>
typedef struct Node
{
	int key;
	bool a;
	struct Node* next;
}Node;

//广度优先遍历（BFS）
void Bfs(Node arr[], int size)
{
	//初始化把所有结点置为未访问状态
	//未访问的可都初始化为false或者-1
	InitNode();

	//判断是否全部已经访问完成
	for (int i = 0; i < size; i++)
	{
		//判断该结点是否已经访问过
		if (IsVisitedNode(arr[i].a))
		{
			continue;
		}

		//从某个结点开始访问，结点入队
		InputQueue();

		//访问结点
		VisitNode();

		//判断队列是否为空，为空即访问结束
		while (IsEmptyQueue())
		{
			//队头出队，并让与之相连的结点入队
			OutputQueue();

			while (IsVisitedNode(arr[i].a))
			{
				InputQueue();
			}
		}
	}
}

2.深度优先遍历（DFS）

算法思想

先访问最深层次的结点，和二叉树的中序遍历同理?

?

?水一章嘿嘿