即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

MOOC_Learn_深搜

编程语言 TaiFu_S 13℃ 0评论
本文目录
[隐藏]

深度优先搜索

深度优先搜索算法(Depth-First-Search),是搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的

分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源

节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进

行直到所有节点都被访问为止(属于盲目搜索)。


基本思想:

      (1)访问顶点v;

      (2)从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;

      (3)重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。

算法复杂度:

若有v个顶点、E条边,则

用邻接表储存图,有O(V+E)

用邻接矩阵储存图,有O(V^2)

伪代码:

   递归实现:

             (1)访问顶点v;visited[v]=1;//算法执行前visited[n]=0

             (2)w=顶点v的第一个邻接点;

             (3)while(w存在)

               if(w未被访问

               从顶点w出发递归执行该算法;

               w=顶点v的下一个邻接点;

//布尔型数组Visited[]初始化成false
void DFS(Vetex v)
{
    Visited[v] = true;
    for each w adjacent to v
        if (!Visited[w])
            DFS(w);
}




*在图上寻找路径


在图上如何寻找从1到8的路径?


一种策略:只要能发现没走过的点,就走到它。有多个点可走就随便挑一个,如果无路可走就回退,再看有没有没走

的点可走。










运气最好:1->2->4->8


运气稍差:1->2->4->5->6->8


运气坏:1->3->7->9
=>7->A=>7=>3->5->6->8(双线箭头表示回退)







不连通的图,无法从节点1 走到节点8。完整的尝试过程可能如下:1 ->2->4->3->7=>3=>4=>2->9=>2=>1

结论:不存在从1 到 8的路径得出这个结论之前,一定会把从1 出发能走到的点全部都走过。

/*

深度优先搜索(Depth-First-Search)

从起点出发,走过的点要做标记,发现有没走过的点,就随意挑一个往前走,走不了就回退,此种路径搜索策略就称

为“深度优先搜索” ,简称“深搜” 。

实称为“远度优先搜索” 更容易理解些。因为这种策略能往前走一步就往前走一步,总是试图走得更远。所谓远

近(或深度) ,就是以距离起点的步数来衡量的。

*/

判断从V出发是否能走到终点:

bool Dfs(V) 
{
 if( V 为终点)
  return true;
 if( V 为旧点)
  return false;
 将V标记为旧点;
 对和V相邻的每个节点U 
 {
  if( Dfs(U) == true)
  return true;
 }
 return false;
}

int main()
{
 将所有点都标记为新点;
 起点 = 1
 终点 = 8
 cout << Dfs(起点;
}

判断从V出发是否能走到终点,如果能,要记录路径:


Node path[MAX_LEN]; //MAX_LEN取节点总数即可
int depth;
bool Dfs(V) 
{
 if( V为终点) 
 {
  path[depth] = V;
  return true;
 }
 if( V 为旧点)
  return false;
 将V标记为旧点;
 path[depth]=V;
 ++depth;
 对和V相邻的每个节点U 
 {
  if( Dfs(U) == true)
  return true;
 }
 --depth;
 return false;
}

int main()
{
 将所有点都标记为新点;
 depth = 0;
 if( Dfs(起点)) 
 {
  for(int i = 0;i <= depth; ++ i)
  cout << path[i] << endl;
 }
}





1->3->7->9=>7->A=>7=>3->5->6->8


path:
1,3,5,6,8




*遍历图上所有节点




Dfs(V) 
{
 if( V是旧点)
  return;
 将V标记为旧点;
 对和V相邻的每个点 U 
 {
  Dfs(U);
 }
}

int main() 
{
 将所有点都标记为新点;
 while(在图中能找到新点k)
  Dfs(k);
}

*图的表示方法 -- 邻接表





用一个二维数组G存放图, G[i][j] 表示节点i 和节点j之间边的情况(如有无边,边方向,权值大小等) 。


遍历复杂度: O(n2) n为节点数目


每个节点V对应一个一维数组(vector) ,里面存放从V连出去的边,边的信息包括另一顶点,还可能包含边权值等。








例1:城堡问题

总时间限制: 
1000ms 
内存限制: 
65536kB
描述


1 2 3 4 5 6 7

#############################

1 # | # | # | | #

#####---#####---#---#####---#

2 # # | # # # # #

#---#####---#####---#####---#

3 # | | # # # # #

#---#########---#####---#---#

4 # # | | | | # #

#############################

(图 1)



# = Wall

| = No wall

- = No wall




图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成m*n(m≤50,n≤50)个方块,每个方块可以有0~4面墙。


输入
程序从标准输入设备读入数据。第一行是两个整数,分别是南北向、东西向的方块数。在接下来的输入行里,每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙,1表示西墙,2表示北墙,4表示东墙,8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。
输出
城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。


样例输入
4 
7 
11 6 11 6 3 10 6 
7 9 6 13 5 15 5 
1 10 12 7 13 7 5 
13 11 10 8 10 12 13 
样例输出
5
9




解题思路:


把方块看作是节点,相邻两个方块之间如果没有墙,则在方块之间连一条边,这样城堡就能转换成一个图。



求房间个数,实际上就是在求图中有多少个极大连通子图。



一个连通子图,往里头加任何一个图里的其他点,就会变得不连通,那么这个连通子图就是极大连通子图
(如: (8,5,6))


对每一个房间,深度优先搜索,从而给这个房间能够到达的所有位置染色。最后统计一共用了几种颜色,以及每种颜色的数量。



比如


1 1 2 2 3 3 3


1 1 1 2 3 4 3


1 1 1 5 3 5 3


1 5 5 5 5 5 3



从而一共有5个房间,最大的房间(1 )占据9个格子

/*
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
*/

#include 
#include 
#include 
using namespace std;
int R, C;
int rooms[60][60];
int color[60][60];
int maxRoomArea, roomNum;
int roomArea;

void Dfs(int i, int j)
{
    if(color[i][j])
        return ;
    ++roomArea;
    color[i][j] = 1;//roomNum
    if ((rooms[i][j] & 1) == 0)//向西
        Dfs(i, j - 1);
    if ((rooms[i][j] & 2) == 0)//向北
        Dfs(i - 1, j);
    if ((rooms[i][j] & 4) == 0)//向东
        Dfs(i, j + 1);
    if ((rooms[i][j] & 8) == 0)//向南
        Dfs(i + 1, j);
}

int main()
{
    while (scanf("%d%d", &R, &C) == 2)
    {
        printf("%d\n%d\n", R, C);
        maxRoomArea = 0, roomNum = 0;
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                scanf("%d", &rooms[i][j]);
        memset(color, 0, sizeof(color));
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                if(!color[i][j])
                {
                    ++roomNum;
                    roomArea = 0;
                    Dfs(i, j);
                    maxRoomArea = max(roomArea, maxRoomArea);
                }
        printf("%d\n%d\n", roomNum, maxRoomArea);
    }
    return 0;
}
//复杂度:O(R*C)



例2:踩方格

1.
总时间限制:
1000ms
内存限制:
65536kB
描述

有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:


a.    每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;


b.    走过的格子立即塌陷无法再走第二次;


c.    只能向北、东、西三个方向走;


请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。


输入
允许在方格上行走的步数n(n <= 20)
输出
计算出的方案数量
样例输入
2
样例输出
7

解题思路


递归


从 (i,j) 出发,走n步的方案数,等于以下三项之和:


从(i+1,j) 出发,走n-1 步的方案数。前提: (i+1,j) 还没走过


从(i,j+1) 出发,走n-1 步的方案数。前提: (i,j+1) 还没走过


从(i,j-1) 出发,走n-1 步的方案数。前提: (i,j-1) 还没走过



#include 
#include 
#include 
using namespace std;
int vis[30][50];

int ways(int i, int j, int n)
{
    if (n == 0)
        return 1;
    vis[i][j] = 1;
    int num = 0;
    if (!vis[i][j-1])
        num += ways(i, j-1, n-1);
    if (!vis[i][j+1])
        num += ways(i, j+1, n-1);
    if (!vis[i+1][j])
        num += ways(i+1, j, n-1);
    vis[i][j] = 0;
    return num;
}
int main()
{
    int n;
    while (scanf("%d", &n) == 1)
    {
        memset(vis, 0, sizeof(vis));
        printf("%d\n", ways(0, 25, n));
    }
    return 0;
}



To be continued.


转载请注明:CodingBlog » MOOC_Learn_深搜

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情