1. 介绍

本文介绍了比较初级的图搜索算法,包括深度优先遍历,广度优先遍历和双向广度优先遍历。

2. 深度优先遍历DFS

2.1 算法思想

从图中某个顶点v开始,访问此节点,然后依次从v中未被访问的邻接点出发深度优先遍历图,直到图中上所有和v有路径相通的顶点都被访问;若此时图中尚有顶点未被访问,则另选图中一个未被访问顶点做起点,重复以上过程,直到图中所有顶点都被访问为止。

深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过,在G中任选一个顶点i作为遍历的初始点,则深度优先搜索遍历可定义如下:

(1)    首先访问顶点i,并将其访问标记置为访问过,即visited[i]=1;

(2)    然后搜索与顶点i有边相连的下一个顶点j,若j未被访问过,则访问它,并将j的访问标记置为访问过,visited[j]=1,然后从j开始重复此过程,若j已访问,再看与i有边相连的其它顶点;

(3)    若与i有边相连的顶点都被访问过,则退回到前一个访问顶点并重复刚才过程,直到图中所有顶点都被访问完止。

2.2 算法实现

邻接矩阵的算法描述为下面形式:

void dfs1(graph &g,int i,int n)//深度优先
{//从顶点i出发遍历  临界矩阵
	cout<<g.v[i];//输出访问顶点
	visited[i]=1;
	for(j=1;j<=n;j++)
		if((g.arcs[i][j]==1)&&(!visited[j]))
			dfs1(g,j,n);
}

邻接表算法描述为下面形式:

void dfs2(adjlist GL,int i,int n)
{//深度优先 ----从顶点i出发遍历,数据结构采用邻接表
	cout<<i<<" ";
	visited[i]=1;
	edgenode* p=GL[i];
	while(p!=NULL)
	{
		if(!visited[p->adjvex])
			dfs2(G,p.adjvex,n);
		p=p->next;
	}
}

2.3 适用范围

需要有顺序遍历图,且找到一个解后输出即可。如:trie树排序

多用于只要求解,并且解答树中的重复节点较多并且重复较难判断时使用,但往往可以用A*或回溯算法代替。

2.4 举例

数独求解。给出一个不完整的数独,让填充其中空白的数字。

更多题目:

POJ 1321 棋盘问题:http://www.cublog.cn/u3/105033/showart_2212140.html

类迷宫问题:http://www.jguoer.com/post/2010/02/17/DFS-Code.aspx

数独问题:http://acm.hdu.edu.cn/showproblem.php?pid=1426

3. 广度优先遍历BFS

3.1 算法思想

广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问,在G 任选一顶点i作为初始点,则广度优先搜索的基本思想是:

(1)首先访问顶点i,并将其访问标志置为已被访问,即visited[i]=1;

(2)接着依次访问与顶点i有边相连的所有顶点W1,W2,…,Wt;

(3)然后再按顺序访问与W1,W2,…,Wt有边相连又未曾访问过的顶点;

依此类推,直到图中所有顶点都被访问完为止。

3.2 算法实现

用邻接矩阵的算法描述如下:

void bfs1(graph g,int i)
{//从顶点i出发广度优先遍历.数据结构为邻接矩阵
	Queue q;
	cout<<g.v[i];
	visited[i]=1;
	q.insert(i);
	while(!q.empty())
	{
		int k=q.delete();
		for(j=0;j<n;j++)
		{
			if((g.a[k][j])&&!visited[j])
			{
				cout<<g.v[j];
				visited[j]=1;
				q.insert(j);
			}
		}
	}
}


用邻接表的算法描述如下 :

void bfs2(adjlist GL,int i,int n)
{//广度优先遍历 从i出发,使用邻接表作为数据结构
	queue q;
	cout<<i<<" ";
	visited[i]=1;
	q.insert(i);
	while(!q.empty())
	{
		int k=q.pop();
		edgenode* p=GL[k];
		while(p!=NULL)
		{
			if(!visited[p->adjvex])
			{
				cout<<p->adjvex;
				visited[p->adjvex]=1;
				q.insert(p->adjvex);
			}
			p=p->next;
		}
	}
}

3.3 适用范围

求问题的最优解

3.4 举例

给定一个8*8的格子地图,再给定初始状态和终止状态,输出从初始点到达终止点的最少步数。

更多题目:

http://www.cppblog.com/firstnode/archive/2009/03/07/75839.html

http://blog.sina.com.cn/s/blog_6635898a0100hwe3.html

http://blog.csdn.net/super_chris/archive/2009/12/26/5082666.aspx

http://www.chenyajun.com/2010/05/08/4540

4. 双向广度优先遍历

4.1 算法思想

有些问题按照广度优先搜索法则扩展结点的规则,既适合顺序,也适合逆序,于是我们考虑在寻找目标结点或路径的搜索过程中,初始结点向目标结点和目标结点向初始结点同时进行扩展,直至在两个扩展方向上出现同一个子结点,搜索结束,这就是双向搜索过程。

出现的这个同一子结点,我们称为相交点,如果确实存在一条从初始结点到目标结点的最佳路径,那么按双向搜索进行搜索必然会在某层出现“相交”,即有相交点,初始结点一相交点一目标结点所形成的一条路径即是所求路径。

4.2 算法实现

转自:http://blog.sina.com.cn/s/blog_8627bf080100ticx.html

现在再来看看双向广搜模版:

void TBFS()
{
  bool found=false;
  memset(visited,0,sizeof(visited)); // 判重数组
  while(!Q1.empty()) Q1.pop(); // 正向队列
  while(!Q2.empty()) Q2.pop(); // 反向队列

  //======正向扩展的状态标记为1,反向扩展标记为2
  visited[s1.state]=1; // 初始状态标记为1
  visited[s2.state]=2; // 结束状态标记为2
  Q1.push(s1); // 初始状态入正向队列
  Q2.push(s2); // 结束状态入反向队列
  while(!Q1.empty() || !Q2.empty())
  {
    if(!Q1.empty())
      BFS_expand(Q1,true); // 在正向队列中搜索
    if(found) // 搜索结束
      return ;

    if(!Q2.empty())
      BFS_expand(Q2,false); // 在反向队列中搜索

    if(found) // 搜索结束
      return ;
  }
}

void BFS_expand(queue<Status> &Q,bool flag)
{
  s=Q.front(); // 从队列中得到头结点s
  Q.pop()
  for( 每个s 的子节点 t )
  {
    t.state=Gethash(t.temp) // 获取子节点的状态
    if(flag) // 在正向队列中判断
    {
      if (visited[t.state]!=1)// 没在正向队列出现过
   {
        if(visited[t.state]==2) // 该状态在反向队列中出现过
          {
            //各种操作;
            found=true;
            return;
         }
        visited[t.state]=1; // 标记为在在正向队列中
        Q.push(t); // 入队
    }
  }else // 在正向队列中判断
  {
    if (visited[t.state]!=2) // 没在反向队列出现过
   {
        if(visited[t.state]==1) // 该状态在正向向队列中出现过
        {
          各种操作;
          found=true;
          return;
        }
        visited[t.state]=2; // 标记为在反向队列中
        Q.push(t); // 入队
    }
  }
}   

4.3 适用范围

最优化问题中,知道问题的起始状态和最终状态,且两个状态可相互到达。

4.4 举例

棋盘上有四个棋子,给你两个状态,问可否8步内将一个状态转移到另一个状态?

5. DFS与BFS比较

数据结构:DFS采用栈,而BFS采用队列

算法思想:深度搜索与广度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复的节点,从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的一个,而广度搜索扩展的则是本次扩展的节点的兄弟节点

使用范围:DFS可以迅速的找到一个解,然后利用这个解进行剪枝,而BFS可找到最优解。

原创文章,转载请注明: 转载自董的博客

本文链接地址: 算法之图搜索算法(一)

微信公众号:hadoop-123,专注于大数据技术分享,欢迎加入!

说点什么

avatar
  Subscribe  
提醒