类型一：邻接表

题目一：员工的重要性

给定一个保存员工信息的数据结构，它包含了员工唯一的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, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1

输出: 11

解释:

员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。

注意:

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

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

"""

# 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],[]]

输出: true

解释:

我们从 0 号房间开始，拿到钥匙 1。

之后我们去 1 号房间，拿到钥匙 2。

然后我们去 2 号房间，拿到钥匙 3。

最后我们去了 3 号房间。

由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：[[1,3],[3,0,1],[2],[0]]

输出：false

解释：我们不能进入 2 号房间。

提示：

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

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

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:

输入: 2, [[1,0]]

输出: [0,1]

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

示例 2:

输入: 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] 。

说明:

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

提示:

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

　　1、建立图

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

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

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))

题目三：解题报告，连除----399

已经给出了某些变量的比值，求新的变量的比值。如果这个变量没有出现过，或者不可到达，那么返回-1.

题目中给了顶点和顶点之间的关系，其实就是制定了这个图的样子。然后要求的新的比值其实就是从一个顶点到达另外一个顶点的路径，并且把这条路径上所有的权重相乘。

注意，如果a/b=3，那么从a到b是3，那么从b到a是1/3.

既然是从一个顶点出发到达另外一个顶点，所以应该是dfs解决的问题。

原文：https://blog.csdn.net/fuxuemingzhu/article/details/82591165

　　1、建立图　　{a：{b : 2.0} 、b：{a：1 /2.0，c：3.0}、c：{b：1/3.0}}

　　2、不在图中则返回-1　　

　　3、在图中，x == y，返回1，x != y，返回x到y的拓扑排序的权重相乘值。

　　

from collections import defaultdict

def solveque(arr ,values , que):

    if not arr:

        return [-1] * len(que)

    if not que:

        return []

    graph = defaultdict(dict)

    for (x,y) , value in zip(arr,values):

        graph[x][y] = value

        graph[y][x] = 1/value if value else 0

    for x,y in que:

        if x in graph and y in graph:

            return dfs(graph,x,y,set())

        else:

            return -1.0

def dfs(graph,x,y,visited):

    if x == y:

        return 1.0

    visited.add(x)

    for k in graph[x]:

        if k in visited:continue

        visited.add(k)

        d = dfs(graph,k,y,visited)

        if d > 0:

            return d*graph[x][k]

    return -1.0

arr = [['a','b'],['b','c']]

values = [2.0,3.0]

que = [['a','c'],['a','v']]

print(solveque(arr ,values , que))

rooms