BFS和DFS

BFS（广度优先搜索）、

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点(左节点和右节点)，再依次遍历每个相邻节点的相邻节点(左节点和右节点)。

BFS（深度优先搜索）、

深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。¹

#include<iostream>
using namespace std;
#include<cassert>
#include<algorithm>
#include<string>
#include<time.h>
#include<vector>
#include<queue>
#include<stack>


class node
{
public:
	node(node* _1 = nullptr, node* _2 = nullptr, node* _3 = nullptr, int data = 0, int number = 0):
		_1(_1),_2(_2),_3(_3),data(data),number(number){}

	~node(){}
	node* _1 = nullptr;
	node* _2 = nullptr;
	node* _3 = nullptr;
	int data = 0;
	int number = 0;
};

void BFS(const vector<node*>&nodes,node * start)
{
	bool* is_visited = new bool[nodes.size()] {};
	memset(is_visited, false, sizeof(bool) * nodes.size());
	queue<node*> q{};
	node* tmp = nullptr;
	q.push(start);
	while (!q.empty())
	{
		tmp = q.front();
		q.pop();
		if (!is_visited[tmp->number - 1])
		{
			cout << tmp->data << "  ";
			is_visited[tmp->number - 1] = true;
		}
		if (tmp->_1 &&!is_visited[tmp->_1->number - 1])
		{
			q.push(tmp->_1);
		}
		if (tmp->_2 && !is_visited[tmp->_2->number - 1])
		{
			q.push(tmp->_2);
		}
		if (tmp->_3 && !is_visited[tmp->_3->number - 1])
		{
			q.push(tmp->_3);
		}
	}
	delete[]is_visited;
	is_visited = nullptr;
}

//DFS可以使用栈实现或者递归实现
void DFS(const vector<node*>& nodes, node* start)
{
	bool* is_visited = new bool[nodes.size()] {};
	memset(is_visited, false, sizeof(bool) * nodes.size());
	stack<node*> s{};
	s.push(start);
	node* tmp = nullptr;
	while (!s.empty())
	{
		tmp = s.top();
		s.pop();
		if (!is_visited[tmp->number - 1])
		{
			cout << tmp->data << "  ";
			is_visited[tmp->number - 1] = true;
		}
		if (tmp->_1 && !is_visited[tmp->_1->number - 1])
		{
			s.push(tmp->_1);
		}
		if(tmp->_2 && !is_visited[tmp->_2->number - 1])
		{
			s.push(tmp->_2);
		}
		if(tmp->_3 && !is_visited[tmp->_3->number - 1])
		{
			s.push(tmp->_3);
		}
	}
	delete[]is_visited;
	is_visited = nullptr;
}


int main()
{

	vector<node*> nodes{};

	for (int i = 1; i <= 10; ++i)
	{
		nodes.push_back(new node{ nullptr,nullptr,nullptr,i,i });
	}

	nodes[0]->_1 = nodes[1];
	nodes[0]->_2 = nodes[2];
	nodes[0]->_3 = nodes[3];
	nodes[1]->_1 = nodes[0];
	nodes[2]->_1 = nodes[0];
	nodes[3]->_1 = nodes[0];
	nodes[1]->_2 = nodes[4];
	nodes[4]->_1 = nodes[8];
	nodes[4]->_2 = nodes[1];
	nodes[8]->_2 = nodes[4];
	nodes[2]->_3 = nodes[5];
	nodes[2]->_2 = nodes[6];
	nodes[5]->_1 = nodes[9];
	nodes[5]->_2 = nodes[2];
	nodes[6]->_3 = nodes[2];
	nodes[9]->_1 = nodes[5];
	nodes[3]->_2 = nodes[7];
	nodes[7]->_1 = nodes[3];


	BFS(nodes, nodes[0]);
        cout << endl;
	DFS(nodes, nodes[0]);

	for (auto c : nodes)
	{
		delete c;
		c = nullptr;
	}


	return 0; 
}