蓝桥杯丨深度优先搜索

前言

深度优先算法是图中的一个主要算法，简称DFS算法。

一、最大油田问题

问题引入

【问题描述】政府现勘探到一片油田，在这一片油田中有很多散落的石油资源。因为经费原因，政府只能开采一处油田，所以需要找到最大的油田进行施工。油田的地理情况被简化成了一个矩阵，其中每一个方格代表一块土地，0代表陆地，1代表是石油资源。如果一处石油资源和另一处石油资源相连接，则其算一块油田。现要找到最大的相互连接的石油资源，并输出它的面积。

【输入形式】

第一行为油田的长和宽，第二行为油田。

【输出形式】

最大油田的面积.

【样例输入】

7 7

0 0 0 0 1 1 0

0 1 1 0 1 1 0

0 1 1 0 0 0 0

0 0 1 0 0 1 1

0 0 0 0 0 0 0

0 0 1 1 0 0 0

0 0 0 1 0 0 1

【样例输出】

5

程序设计

def MaxArea(lst,m,n):
    arrived=[[0 for j in range(n)] for i in range(m)]
    s=0
    def DFS(x,y):
        if x>=0 and x<m and y>=0 and y<n and not arrived[x][y] and lst[x][y]==1:
            arrived[x][y]=1
            return 1+DFS(x-1,y)+DFS(x+1,y)+DFS(x,y-1)+DFS(x,y+1)
        else:
            return 0
    for i in range(m):
        for j in range(n):
            t=DFS(i,j)
            if t>s:
                s=t
    return s
m,n=map(int,input().split())
lst=[]
for i in range(m):
    lst.append(list(map(int,input().split())))
print(MaxArea(lst,m,n)) 

算法分析

本程序实现了一个求解矩阵中最大连通区域的函数MaxArea。该函数的输入参数为一个m行n列的矩阵lst，函数返回值为矩阵中最大连通区域的大小。

函数实现的思路是通过深度优先搜索算法，遍历矩阵中所有的连通块，并记录下每个连通块的大小，最后返回大小最大的连通块大小。

该程序的基本思路是先定义一个大小为m*n的全零矩阵arrived来记录每个位置是否已经被遍历过，然后遍历矩阵lst中的每个位置，如果该位置还没有被遍历过且该位置的值为1，就以该位置为起点进行深度优先搜索，并计算连通块的大小。在搜索过程中，每次访问一个位置时，将该位置标记为已访问，以免重复搜索。最后返回连通块大小的最大值即可。

该程序的时间复杂度为O(m*n)，即需要遍历矩阵中的所有位置。空间复杂度也为O(m*n)，即需要申请一个大小为m*n的数组来记录每个位置是否已经访问过。

二、员工派对

问题引入

【问题描述】

公司要举办一个员工派对，公司里所有的员工都有资格来参加。该公司的组织结构是一个二叉树结构。如果一个结点A有双亲结点B，则代表B是A的上司。实际上，每一个员工为派对带来的贡献不一样，有的人幽默，就能使派对更加有趣，而有的人恰恰相反。然而，假如该公司里的所有员工都对自己的上司不满意（假设其有上司），那么如果一个员工来到派对，其上司就不能来到派对，反之亦然。但员工和员工上司的上司可以一起参加派对，因为他们互相不熟悉。如果你是董事长的秘书，并且已知公司组织结构，应该怎么邀请员工，使得任何一组员工和上司不会同时出现在派对中，并且使得邀请的所有员工的贡献值之和最大。

【输入形式】

按二叉树层序输入员工的价值。

【输出形式】

贡献值之和的最大值。

【样例输入】

3 4 5 1 3 1

【样例输出】

9

程序设计

class treenode():
    def __init__(self,val):
        self.val=val
        self.left=None
        self.right=None
Input=list(map(int,input().split()))
tree=[treenode(0)]
for i in Input:
    tmp=treenode(i)
    tree.append(tmp)
for i in range(1,len(tree)):
    if tree[i].val==0:
        continue
    if 2*i<=len(tree)-1 and tree[2*i].val!=0:
        tree[i].left=tree[2*i]
    if 2*i+1<=len(tree)-1 and tree[2*i+1].val!=0:
        tree[i].right=tree[2*i+1]
def ans(root):
    at_val,ab_val=DFS(root)
    return max(at_val,ab_val)
def DFS(node):
    if (node==None):
        return 0,0
    left_at,left_ab=DFS(node.left)
    right_at,right_ab=DFS(node.right)
    Attend_Value=int(node.val)+left_ab+right_ab
    Absent_Value=max(left_at,left_ab)+max(right_at,right_ab)
    return Attend_Value,Absent_Value
print(ans(tree[1]))

算法分析

本题是一道二叉树的递归算法题，需要用到二叉树深度优先搜索算法（DFS）。题目要求在二叉树中选定一些节点，使得这些节点的值的和最大，但是不能选相邻的节点（即选一个节点后，它的父节点，子节点都不能被选中）。因此，对于每个节点，有两种情况：选中该节点和不选中该节点。

设一个函数DFS，该函数的输入是一个节点，输出是一个二元组(at_val,ab_val)，分别表示选中该节点和不选中该节点时，所能获得的最大权值和。最终，函数的输出结果是max(at_val,ab_val)。在DFS函数中，先递归调用左子树和右子树的DFS函数，获取左子树和右子树在选中和不选中当前节点的情况下的最大权值和。然后，计算当前节点选中的情况下的权值和和不选中的情况下的权值和，分别为Attend_Value和Absent_Value。Attend_Value就是当前节点的值加上左子树和右子树在不选中当前节点的情况下的最大权值和left_ab和right_ab。Absent_Value就是左子树中选取最大权值和的一种情况（即选中左子树的根节点或者不选中左子树的根节点），右子树中选取最大权值和的一种情况（即选中右子树的根节点或者不选中右子树的根节点），然后将两者相加即可。

最后，在主函数中，按照输入数据构造二叉树，并将根节点传入DFS函数中求解最大权值和，最终输出结果即可。

总结

DFS算法是二叉树的重要应用，在解决很多问题时都需要灵活使用，主要是一种递归的思想。