深度优先搜索（DFS）

深度优先搜索（DFS） 深度优先搜索 介绍

深度优先搜索（DFS）为随机沿一条支路走到头，后返回上一岔路继续重复 *** 作，最后遍历全部的过程。

一条路线：
A出发，随机三条支路选择B；B访问C；C访问D；因为遍历过A，所以不能从D访问A，应返回到C，继而返回到B，最后返回到A，由A访问E。

全部过程为：
A->B->C->D->E
或者：
A->E->B->C->D
A->E->D->C->B
等等。

案例（LeetCode 第695题岛屿最大面积，C++实现） 案例链接：https://leetcode-cn.com/problems/max-area-of-island/ 案例描述：

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

简单的说，就是遍历坐标，返回相邻1（土地）个数的最大值（岛屿的面积）。

代码分析

遍历每个岛屿的面积

	
    int dfs(vector>& grid, int cur_i, int cur_j)
    {
    	//每个坐标不为1或不满足题意返回面积为0
        if(grid.size()==0 || cur_i<0 || cur_j<0 || cur_i==grid.size() || 
            cur_j==grid[0].size() || grid[cur_i][cur_j]!=1)
        {
            return 0;
        }
        //找到开始为1的坐标，开始遍历后，已经访问的位置置0，避免回溯时重复访问
        grid[cur_i][cur_j]=0;   //第一个1置零
        //以访问的位置为中心，向上下左右访问，如果为1，面积就加1
        int dfs_i[4]={0,0,1,-1};
        int dfs_j[4]={1,-1,0,0};   //向四个方向遍历
        int ans=1;	//最初的面积
        for(int count=0;count<4;count++)
        {
            int next_i=cur_i + dfs_i[count];
            int next_j=cur_j + dfs_j[count];   //四个方向的位置坐标

            ans += dfs(grid, next_i, next_j);     //递归
        }
        return ans;
    }

遍历容器，找到面积的最大值

int maxAreaOfIsland(vector>& grid) {
        int ans=0;	//一开始并未找到1，先令面积为0
        for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5579376.html