典型的BFS和DFS算法

Feb 28,2012 BFS 算法 DFS

在学校ACM队也混过一些日子，也学到了一些东西，不过，目前处于游离状态，最近也已经很久没有碰过C和C++了。刚看到桌面上还有2011年暑假留校时候，学长写的两个程序，分别是深度优先搜索算法（Depth First Search , DFS）和广度优先搜索算法（Breadth First Search , BFS），很简洁经典，现在把它发出来。

**申明：**以下两份代码的归属权为张飞学长所有！！！

DFS：属于图算法的一种，其过程简要来说就是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

#include <iostream>
#include <cstring>
using namespace std;

const int dir[] = {0,1,1,0,0,-1,-1,0};
const int maxSize = 10;
int Map[maxSize][maxSize];

void dfs(int i,int j)
{
	cout <<Map[i][j] <<endl;
	Map[i][j] = 0;
	int p;
	for(p=0;p<4;p++)
	{
		int ti = i+dir[p*2];
		int tj = j+dir[p*2+1];
		if(Map[ti][tj])
		{
			dfs(ti,tj);
		}
	}
}

void init(int r,int c)
{
	memset(Map,0,sizeof(Map));
	int i,j;
	for(i=1;i<=r;i++)
	{
		for(j=1;j<=c;j++)
		{
			Map[i][j] = (i-1)*r+j;
		}
	}
}

int main()
{
	int r,c;
	while(cin >>r >>c)
	{
		init(r,c);
		dfs(1,1);
	}

	return 0;
}

BFS：是最简单的图搜索算法之一。其过程是说在搜索过程中，按层次进行搜索，本层的节点没有处理完毕前，不能对下一层节点进行处理，即深度越小的节点越先进行处理。

#include <iostream>
#include <cstring>
using namespace std;

const int dir[] = {0,1,1,0,0,-1,-1,0};
const int maxSize = 10;
int Map[maxSize][maxSize];

void dfs(int i,int j)
{
	cout <<Map[i][j] <<endl;
	Map[i][j] = 0;
	int p;
	for(p=0;p<4;p++)
	{
		int ti = i+dir[p*2];
		int tj = j+dir[p*2+1];
		if(Map[ti][tj])
		{
			dfs(ti,tj);
		}
	}
}

void init(int r,int c)
{
	memset(Map,0,sizeof(Map));
	int i,j;
	for(i=1;i<=r;i++)
	{
		for(j=1;j<=c;j++)
		{
			Map[i][j] = (i-1)*r+j;
		}
	}
}

int main()
{
	int r,c;
	while(cin >>r >>c)
	{
		init(r,c);
		dfs(1,1);
	}

	return 0;
}

total 0 comments