图的DFS

发表于 | 分类于 ，

类型一：邻接表

题目一：员工的重要性

题目描述

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

示例 1:

1
2
3
4
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。

注意:

  1. 一个员工最多有一个直系领导，但是可以有多个直系下属
  2. 员工数量不超过2000。

思路：DFS

  【注意点：应使用局部变量（weight）记录结果，不能使用全局变量】

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
# Employee info
class Employee(object):
    def __init__(self, id, importance, subordinates):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""
class Solution(object):
    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        if not employees:
            return 0
        ##局部变量
        weight = 0
        for item in employees:
            if item.id == id:
                weight += item.importance
                for j in item.subordinates:
                    weight += self.getImportance(employees, j)
        return weight

题目二：钥匙和房间

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

1
2
3
4
5
6
7
8
输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

1
2
3
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. 所有房间中的钥匙数量总计不超过 3000。

思路：DFS

每个房间找钥匙，找到则到下一个钥匙对应的房间DFS。采用一个visited列表存储是否到达过这个房间，最后如果所有房间都达到过则返回True。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def canVisitAllRooms(rooms):
    if not rooms:
        return True
    n = len(rooms)
    visited = [False] * n 
    visited[0] = True
    def dfs(rooms,keys,visited):
        for key in keys:
            if not visited[key]:
                visited[key] = True
                dfs(rooms,rooms[key],visited)
    dfs(rooms,rooms[0],visited)
    return all(visited)

类型二：DAG拓扑排序

题目一：课程安排207

题目二：课程安排210

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

1
2
3
输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

1
2
3
4
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

  1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
  2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
  3. 拓扑排序也可以通过 BFS 完成。

思路：DFS

　　1、建立图

　　2、循环n次，每次是遍历一个节点是否已经visited且合法地加入path中了，如果False不合法则直接返回【】。

　　3、遍历一个节点时会将其后面的所有子节点都处理掉。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import defaultdict
def findPath(n,arr):
    if n == 0:
        return []
    graph = defaultdict(list)
    for u , v in arr:
        graph[v].append(u)
    # 0为Unkown，1为visiting，2为visited
    path = []
    visited = [0] * n
    for i in range(n):
        if not DFS(graph,visited,path,i):
            return []
    return path[::-1]
def DFS(graph,visited,path,i):
    ####i节点：其正在遍历，但它的子节点的子节点也是它，表示产生了有环，则return FALSE
    if visited[i] == 1: return False
    ####i节点 ：已经遍历过，后面已经没有节点了，return true
    elif visited[i] == 2:return True
    ####表示正在遍历i节点
    visited[i] = 1
    for j in graph[i]:
        if not DFS(graph,visited,path,j):
            return False
    path.append(i)
    visited[i] = 2
    return True


n = 5
arr = [[1,0],[2,0],[3,1],[3,2],[4,0]]
print(findPath(n,arr))