841. 钥匙和房间

• 思路

  • example

  • 图

    • 有向图 (有起点和终点)

      
      
      
      

  • 连通分支 （但是这里还是有方向的区别）

• 复杂度. 时间：O(n+m), 空间: O(n^2)

遍历O(n+m) 建一个n^2表格 （有向图表）
再判断哪个房间作为终点不到到达。

TBA

• 记忆化 DFS （或者BFS)
  • 复杂度. 时间：O(n+m), 空间: O(n) (m 是钥匙数量总数）

从起点0出发，深搜，标记已访问目的地j。
最后遍历判断是否有目的地未标记。
不需要回溯，因为从0出发深搜能到达的点，标记后即可。
回溯：需要找可行解（线路）的时候考虑。

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(room, index):
            if visited[index] == True:
                return  
            visited[index] = True 
            size = len(rooms[index]) 
            for i in range(size):
                dfs(rooms, rooms[index][i])  
            return  
        n = len(rooms)
        visited = [False for _ in range(n)]
        # visited[0] = False  # 这里的dfs写法：cannot initialize this to be True 
        dfs(rooms, 0) # DFS starting from 0
        # check visited
        for i in range(n):
            if visited[i] == False:
                return False  
        return True  

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(index):
            if visit[index] == True:
                return 
            visit[index] = True 
            n = len(rooms[index]) 
            for i in range(n):
                dfs(rooms[index][i]) 
            return 
        n = len(rooms) 
        visit = [False for _ in range(n)] 
        dfs(0) 
        for i in range(n):
            if visit[i] == False:
                return False 
        return True 

• BFS

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms) 
        que = collections.deque() 
        que.append(0) 
        visit = [False for _ in range(n)]
        while que:
            size = len(que) 
            for i in range(size):
                idx = que.popleft() 
                if visit[idx] == True:
                    continue 
                visit[idx] = True
                for j in range(len(rooms[idx])):
                    que.append(rooms[idx][j]) # !!! 
        for i in range(n):
            if visit[i] == False:
                return False 
        return True  

• 并查集 (如何处理有向图？）

127. 单词接龙

• 思路

  • example

  • 最短转换序列

    
    

  • 图

    • 无向图，只要两个单词相差一个字符，就表示相连。
      • 需要建立图表（二维数组，或者用dict(list)）
        • 暴力法添加会比较复杂麻烦
        • 用中间变量（虚拟节点）过渡，比如'hit' -> '@it', 'h@t', 'hi@', 所有跟'hit'相差一个字符的必定在跟前面三种情况之一相连。
    • 最短路径：用BFS （用deque容器, FIFO)
    • 标记单词，避免重复访问
      • distance数组，每个单词（ID）标记第几步到达（初始inf)

wordId['hit'] = 0, wordId['@it'] = 1, wordId['h@t'] = 2, wordId['hi@'] = 3 (每个单词对应唯一的编号）
wordId['hot'] = 4, wordId['@ot'] = 5, wordId['ho@'] = 6
edge[0] = [1,2,3]
edge[1] = [0]
edge[2] = [0,4]
edge[3] = [0]
edge[4] = [5,2,6]
‘hit'和'hot'的连接通过'h@t'实现

• 复杂度. 时间：?, 空间: (列表单词长度）

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def addWord(word):
            nonlocal nodeNum  
            if word not in wordId:
                wordId[word] = nodeNum 
                nodeNum += 1

        def addEdge(word):
            addWord(word)
            id1 = wordId[word]
            chars = list(word)
            for i in range(len(chars)):
                temp = chars[i]
                chars[i] = '@'
                newWord = ''.join(chars)
                addWord(newWord)
                id2 = wordId[newWord]
                edge[id1].append(id2)  
                edge[id2].append(id1)
                chars[i] = temp  


        n = len(wordList)  
        wordId = collections.defaultdict(int)  
        edge = collections.defaultdict(list)
        nodeNum = 0

        addEdge(beginWord)
        for i in range(n):
            addEdge(wordList[i])
        # 没有必要加endWord进 edge  
        # 如果endWord不在wordList中，return 0
        if endWord not in wordId:
            return 0 

        distance = [float('inf') for _ in range(nodeNum)] 
        beginId, endId = wordId[beginWord], wordId[endWord]
        distance[beginId] = 0

        que = collections.deque([beginId])
        while que:
            Id = que.popleft()
            if Id == endId:
                return distance[endId]//2 + 1 
            for it in edge[Id]:
                if distance[it] == float('inf'):
                    distance[it] = distance[Id] + 1
                    que.append(it)
        return 0 

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # wordId['cook'] = 123
        # hit: 通过 *it, h*t, hi* 过渡
        # graph: edge[id1] = id2 
        # BFS, deque 
        # visit[id] = True or False 
        def addWord(word):
            nonlocal cnt 
            if word not in wordId:
                wordId[word] = cnt 
                cnt += 1

        def addEdge(word):
            addWord(word) 
            id1 = wordId[word]
            chs = list(word)  
            for i in range(len(chs)):
                ch = chs[i] 
                chs[i] = '*' 
                newWord = ''.join(chs) 
                addWord(newWord) 
                id2 = wordId[newWord] 
                edge[id1].append(id2) 
                edge[id2].append(id1) 
                chs[i] = ch # backtrack 

        # main function
        wordId = collections.defaultdict(int) 
        edge = collections.defaultdict(list) 
        n = len(wordList) 
        cnt = 0

        # Graph
        addEdge(beginWord) 
        for i in range(n):
            addEdge(wordList[i]) 
        if endWord not in wordId:
            return 0 
        
        beginId, endId = wordId[beginWord], wordId[endWord] 
        visit = [False for _ in range(len(wordId))] 

        # BFS
        que = collections.deque() 
        que.append(beginId) 
        distance = 0 
        while que:
            size = len(que) 
            for i in range(size):
                Id = que.popleft() 
                if Id == endId:
                    return distance // 2 + 1
                for idx in edge[Id]:
                    if visit[idx] == True:
                        continue 
                    visit[idx] = True 
                    que.append(idx) 
            distance += 1
        return 0 

• 不需要使用wordId

TBA

图论

• 图：节点， 边

  
  
• 类似多叉树结构

/* 图节点的逻辑结构 /
class Vertex {
int id;
Vertex[] neighbors;
}
/ 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}

• 邻接表， 邻接矩阵

  
  

// 邻接表
// graph[x] 存储 x 的所有邻居节点
List<Integer>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;

• 邻接表，好处是占用的空间少; 但无法快速判断两个节点是否相邻

在常规的算法题中，邻接表的使用会更频繁一些，主要是因为操作起来较为简单

• 入度（indegree）和出度（outdegree）

无向图

如果连接无向图中的节点 x 和 y，把 matrix[x][y] 和 matrix[y][x] 都变成 true 不就行了；邻接表也是类似的操作，在 x 的邻居列表里添加 y，同时在 y 的邻居列表里添加 x。

加权图
如果是邻接表，我们不仅仅存储某个节点 x 的所有邻居节点，还存储 x 到每个邻居的权重.
如果是邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 表示没有连接，其他值表示权重.

图的遍历

• 类似多叉树遍历，但是图可能包含环
  • 使用visited标记已访问过的节点

// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    onPath[s] = false;
}

类比贪吃蛇游戏，visited 记录蛇经过的格子，而 onPath 仅仅记录蛇身。在图的遍历过程中，onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景.

• DFS vs 回溯

回溯算法的「做选择」和「撤销选择」在 for 循环里面
onPath 数组的「做选择」和「撤销选择」操作在 for 循环外面

// DFS 算法，关注点在节点
void traverse(TreeNode root) {
    if (root == null) return;
    printf("进入节点 %s", root);
    for (TreeNode child : root.children) {
        traverse(child);
    }
    printf("离开节点 %s", root);
}

// 回溯算法，关注点在树枝
void backtrack(TreeNode root) {
    if (root == null) return;
    for (TreeNode child : root.children) {
        // 做选择
        printf("从 %s 到 %s", root, child);
        backtrack(child);
        // 撤销选择
        printf("从 %s 到 %s", child, root);
    }
}

797. 所有可能的路径

• 思路
  • example
  • 有向无环图（DAG）
  • graph[i][j] != i（即不存在自环）
  • 给定邻接表

时间复杂度：，其中 n 为图中点的数量。我们可以找到一种最坏情况，即每一个点都可以去往编号比它大的点。此时路径数为 ，且每条路径长度为 O(n)，因此总时间复杂度为 。每个点（除了起点和终点）都有两种选择：选与不选，故最坏时间复杂度为.
空间复杂度：O(n)，其中 n 为点的数量。主要为栈空间的开销。注意返回值不计入空间复杂度。

• 写法1: 选择撤销在循环内 （需要单独把初始起点单独加入path)

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def traversal(graph, i): # 常规回溯框架, 选择|撤销操作 在循环内 
            if i == len(graph) - 1: # 节点判断以及处理
                res.append(path[:]) 
                return 
            for j in graph[i]: # 深搜, 无环：不需要去重, 否则要用visited 
                path.append(j) # 选择
                traversal(graph, j) # 递归回溯
                path.pop() # 撤销
        res = []
        path = [0] # 调用遍历函数前，先加入起点进path 
        traversal(graph, 0)
        return res 

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def backtrack(idx):
            if idx == n - 1:
                res.append(path[:]) 
                return 
            for node in graph[idx]:
                path.append(node) 
                backtrack(node) 
                path.pop() 
            return 
        n = len(graph) 
        res = [] 
        path = [0] # !!!
        backtrack(0)
        return res 

• 写法2: 选择撤销在循环外 （不需要单独把初始节点加入path)

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def traversal(graph, i): # dfs框架?, 选择|撤销操作 在循环外 
            path.append(i) # 选择：把节点加入path; 循环外 
            if i == len(graph) - 1: # 节点判断以及处理
                res.append(path[:]) 
                path.pop() # 提早return, 所以要单独把最后加进的节点pop出来
                return # 提早return, 所以要单独把最后加进的节点pop出来
            for j in graph[i]: # 深搜, 无环：不需要去重, 否则要用visited 
                traversal(graph, j) # 递归dfs
            path.pop() # 撤销；循环外
        res = []
        path = [] # 调用遍历函数前，不需要单独加入起点进path 
        traversal(graph, 0)
        return res 

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def dfs(idx):
            path.append(idx)
            if idx == n - 1:
                res.append(path[:]) 
                path.pop() # !!!!!!
                return 
            for node in graph[idx]:
                dfs(node) 
            path.pop()
            return 
        n = len(graph) 
        res = [] 
        path = [] # !!!
        dfs(0)
        return res 

• BFS

TBA

二分图

二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。

双色问题

应用：电影与演员的映射关系. 常规：两个hash表。用「图」结构存储，将电影和参演的演员连接，很自然地就成为了一幅二分图：

785. 判断二分图

• 思路
  • example
  • 输入一个 邻接表 表示一幅无向图，请你判断这幅图是否是二分图
  • dfs

一边遍历(dfs)一边着色，注意相邻节点必须用不同颜色。

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(graph, start, color_code):
            if visited[start]: # 已经着色
                return color[start] == color_code # 是否协调
            color[start] = color_code 
            visited[start] = True 
            for j in graph[start]:
                flag = dfs(graph, j, color_code^1)
                if flag == False:
                    return False 
            return True 
        n = len(graph)
        visited = [False for _ in range(n)] # 节点是否已着色
        color = [-1 for _ in range(n)] # 每个节点的着色，0 or 1
        for i in range(n): # 可能有多个连通分支，所以每个点都要当作起始点检查一遍
            if not visited[i]:
                flag = dfs(graph, i, 0) # color_code = 0 (1 也可以)
                if flag == False: # 已经找到冲突，提早返回False 
                    return False 
        return True 

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(graph, x, status):
            new_status = (status + 1) % 2
            if mark[x] != -1:
                return mark[x] == new_status
            mark[x] = new_status 
            for y in graph[x]:
                if dfs(graph, y, new_status) == False:
                    return False 
            return True 
        n = len(graph)
        mark = [-1 for _ in range(n)] 
        for i in range(n): # !!!
            if mark[i] != -1:
                continue 
            if dfs(graph, i, 0) == False:
                return False 
        return True 

• bfs

TBA

886. Possible Bipartition

• 思路
  • example

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        def dfs(graph, i, color_code):
            if color[i] != -1:
                return color[i] == color_code 
            color[i] = color_code 
            for j in graph[i]:
                if dfs(graph, j, color_code^1) == False:
                    return False 
            return True 
        color = [-1 for _ in range(n+1)] # -1, 0, 1 
        graph = collections.defaultdict(list)
        for dislike in dislikes:
            u, v = dislike[0], dislike[1]
            graph[u].append(v)
            graph[v].append(u) 
        for i in range(1, n+1):
            if color[i] == -1:
                if dfs(graph, i, 0) == False:
                    return False 
        return True 

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        def dfs(graph, i, status):
            if color[i] != -1:
                return color[i] == status 
            color[i] = status 
            for j in graph[i]:
                if dfs(graph, j, status^1) == False:
                    return False 
            return True 
        graph = collections.defaultdict(list)
        color = [-1 for _ in range(n+1)] 
        for i in range(len(dislikes)):
            x, y = dislikes[i][0], dislikes[i][1] #!!!
            graph[x].append(y) 
            graph[y].append(x) 
        for i in range(1, n):
            if color[i] == -1:
                if dfs(graph, i, 0) == False:
                    return False 
        return True