图的遍历算法常用的有BFS(宽度优先遍历)和DFS(深度优先遍历)

一、宽度优先遍历

1、宽度优先遍历

宽度优先搜索(BFS, Breadth First Search)是一个针对图和树的遍历算法。发明于上世纪50年代末60年代初，最初用于解决迷宫最短路径和网络路由等问题。

BFS使用队列(queue)来实施算法过程，队列(queue)有着先进先出FIFO(First Input First Output)的特性，BFS操作步骤如下：
1、把起始点放入queue；
2、重复下述2步骤，直到queue为空为止：
1) 从queue中取出队列头的点；
2) 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入queue中。

下面结合一个图来说明BFS的流程和原理：

重复2-4步骤，直到队列为空完成整个遍历过程。

为什么需要一张set表？ 

因为在弹出B的时候，b的nexts包含A，如果没有set表去重，就会导致遍历过程一直不停的进行下去，所以需要set表

2、代码实现

class Solution
{
public:
	void BFS(Node* node) {
		if (node == nullptr) {
			return;
		}
		queue<Node*> queue;
		set<Node*> set;
		queue.push(node);
		set.insert(node);
		while (queue.size()) {
			Node* queuetop = queue.front();
			cout << queuetop->value << " ";
			queue.pop();
			for (auto next : queuetop->nexts) {
				if (!set.count(next)) {
					set.insert(next);
					queue.push(next);
				}
			}
		}
	}
};

二、深度优先遍历

1、深度优先搜索

深度优先搜索（DFS，Depth-First Search）是搜索算法的一种，它从某一个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直到找到最终的解。

DFS使用栈(stack)来实施算法过程，栈(stack)有着先进后出的特性，DFS操作步骤如下：
1、把起始点放入stack；
2、重复下述2步骤，直到queue为空为止：
1) 从stack中取出栈顶的点；
2) 找出与此点邻接的且尚未遍历的一个点，进行标记，然后把该点和邻接点重新放入stack中。

下面结合一个图来说明BFS的流程和原理：

重复2-4直到stack为空结束整个过程，相当于一条路走到黑，如果出现新的节点直接break重新压入继续走即可。 

2、代码实现 

class Solution
{
public:
	void DFS(Node* node) {
		if (node == nullptr) {
			return;
		}
		stack<Node*> stack;
		set<Node*> set;
		stack.push(node);
        set.insert(node);
		while (stack.size()) {
			Node* cur = stack.top();
			stack.pop();
			for (auto next : node->nexts) {
				if (!set.count(next)) {
					stack.push(cur);
					stack.push(next);
					set.insert(next);
					cout << next->value << " ";
					break;
				}
			}
		}
	}
};