DFS搜索算法详解_dfs算法

                                                                             深度优先搜索

                                                                                                ---一条道走到黑

DFS其实叫深度优先搜索算法，起始它只是一种搜索的方法思路，并没有固定的算法格式。让我们通过一个社交图的例子来看。

我们拿到一个社交关系无向图：

通过无向图可以得到邻接矩阵 

用1表示他们有社交关系，0表示没有社交关系。

 我们提出一个问题，怎样通过无向图能够找出一个人所有的朋友呢，答案可以是深度优先搜索。

借助邻接矩阵可以得到各个人物之间的社会关系，通过一个人去找他的朋友（它朋友的朋友也是他的朋友），比如zzx的朋友有lxh、lrz、cy。

首先能够找到lxh，通过lxh找到了lrz，再通过lxh找到了cy。可以看出搜索的过程中，有时候需要前一个已经访问到的朋友，自然而然的可以想起递归的方式。

使用递归，首先循环体是得到朋友的下标，遍历朋友那一行，访问朋友的朋友。这个过程中我们要知到哪些朋友已经访问过了，所以在访问之后应该标记为以访问状态。代码如下：

递归循环体，用true表示已访问状态，顺便打印出朋友名称，遍历朋友那一行找出新朋友，当得到新朋友的时候，重复上一次的操作。（写递归，首先简化问题，找出循环体，找出出递归条件）

        cout << i << m_v[i].c_str() << "->";
		arr[i] = true;
 
		for (int j = 0; j < m_v.size(); ++j)
		{
			if (m_edges[i][j]!=0 && arr[j]==false)
			{
				  _DFS(j, arr);//此处没有return 因为函数没有返回值，有return会产生意想不到的错误
 
			}
		}

完整代码

    void _DFS(int i, vector<bool> & arr)
	{
		//&  使用递归的时候应该注意的是，当递归参数要在整个程序中保持最新值的时候，
		//参数应该传引用，或者指针，因为局部变量的话，在函数体出栈的时候，会更新成
		//本次栈中的局部变量，产生与预期不符的结果
 
		cout << i << m_v[i].c_str() << "->";
		arr[i] = true;
 
		for (int j = 0; j < m_v.size(); ++j)
		{
			if (m_edges[i][j]!=0 && arr[j]==false)
			{
			   _DFS(j, arr);//此处没有return 因为函数没有返回值，有return会产生意想不到的错误
			}//for循环的终止条件作为递归的终止条件。
		}
	}
	void DFS(const V & val)
	{
		int ret = GetVertexIndex(val);
		vector<bool> flag(m_v.size(), false);
 
		_DFS(ret, flag);
	}

工程：https://github.com/lixuhui123/Graph

再看一个放扑克牌的例子。有三个桶，三张扑克牌，要求每个桶发一张扑克牌，输出牌的所有排列组合。

使用DFS，约定扑克牌按从小到大的方式放，有三个桶，依次在桶里放一张，循环体是，在所有的未使用的牌当中，放一张到当前桶中去。（这里需要一个数组标记这个牌有没有被使用）

        for (int i = 1; i <= pai; ++i)
	{
		if (flags[i]==false)
		{
			books[steps] = i;
			flags[i] = true;
		}
	}

什么时候输出一种排列组合呢，当到达的桶的序号大于给定桶的个数的时候，意味着所有的桶已经被装填。

        if (steps == pai + 1)
	{
		for(int i=1;i<=pai;++i)
		{
			cout << books[i] << ' ';
		}
		cout << endl;
		return;
	}

当当前桶被放满的时候，就需要进入下一个桶，也就是

        for (int i = 1; i <= pai; ++i)
	{
		if (flags[i]==false)
		{
			books[steps] = i;
			flags[i] = true;
            dfs(steps + 1);
		}
	}

要输出所有的排列组合，一张牌要被使用好多次，涉及到牌的回收重新标记未使用。这个过程应该在每次递归出栈之后做，而且标记数组必须传引用或者是全局变量。

        for (int i = 1; i <= pai; ++i)
	{
		if (flags[i]==false)
		{
			books[steps] = i;
			flags[i] = true;
                dfs(steps + 1);
			flags[i] = false;
		}
	}

 完整代码：

//输出的是给定所有牌的全排列
#include <iostream>
#include<vector>
using namespace std;
//首先是每次都要重复干的事情，每次就是在盒子前面将手里的牌按从小到大的顺序放一张放到
//盒子里面
bool flags[4] = { false };
int  books[4];
int pai = 3;
void dfs(int steps)
{
	//先做三个盒子三张扑克牌
	if (steps == pai + 1)
	{
		for(int i=1;i<=pai;++i)
		{
			cout << books[i] << ' ';
		}
		cout << endl;
		return;
	}
	for (int i = 1; i <= pai; ++i)
	{
		if (flags[i]==false)
		{
			books[steps] = i;
			flags[i] = true;
            dfs(steps + 1);
			flags[i] = false;
		}
	}
		
 
}
int main()
{
	dfs(1);
	system("pause"); 
	return 0;
}