图
一些基本概念不做赘述。
与图相关的算法工具主要分为几类：
-
广度优先搜索 BFS（单源最短路径问题、最小生成树算法）
一般使用邻接表 + 队列
-
深度优先搜索 DFS
一般使用邻接表 + 栈，当然递归也是一个很好的选择。
-
欧拉图
-
拓扑排序
-
强连通分量（Kosaraju算法）
-
并查集
-
最小生成树（Kruskal算法）
1. 课程表
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
我的思路是将整个依赖关系表示为一个有向图。并判断图中是否存在环。如果存在，返回 False ，否则返回 True 。使用邻接矩阵 + 拓扑排序实现。但是到第46个用例超时，说明这种做法比较低效。
换用一个邻接表 + 数组记录入度的方式，成功通过。但我写的这种可能不太标准，正常应当使用队列来做，而我用集合 + 递归。
此外也可以使用深度优先遍历来判断环，需要两个数组记录访问情况，也可以用一个数组不同数字表示不同访问情况。DFS 不再写了，直接贴别人的。
代码
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for i in range(numCourses)]
inNum = [0 for i in range(numCourses)]
for v1, v2 in prerequisites:
graph[v2].append(v1)
inNum[v1] += 1
nodeSet = set()
def delete(v: int) -> None:
for u in graph[v]:
inNum[u] -= 1
if inNum[u] == 0:
delete(u)
nodeSet.add(v)
for i in range(numCourses):
if inNum[i] == 0 and i not in nodeSet:
delete(i)
return len(nodeSet) == numCourses队列
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for i in range(numCourses)]
inNum = [0 for i in range(numCourses)]
for v1, v2 in prerequisites:
graph[v2].append(v1)
inNum[v1] += 1
queue = []
for i in range(numCourses):
if not inNum[i]:
queue.append(i)
while queue:
cur = queue.pop(0)
numCourses -= 1
for v in graph[cur]:
inNum[v] -= 1
if not inNum[v]:
queue.append(v)
return not numCoursesDFS
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
def dfs(i, adjacency, flags):
if flags[i] == -1: return True
if flags[i] == 1: return False
flags[i] = 1
for j in adjacency[i]:
if not dfs(j, adjacency, flags): return False
flags[i] = -1
return True
adjacency = [[] for _ in range(numCourses)]
flags = [0 for _ in range(numCourses)]
for cur, pre in prerequisites:
adjacency[pre].append(cur)
for i in range(numCourses):
if not dfs(i, adjacency, flags): return False
return True
作者：Krahets
链接：https://leetcode.cn/problems/course-schedule/solutions/18806/course-schedule-tuo-bu-pai-xu-bfsdfsliang-chong-fa/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。2. 省份数量
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
之前也写过，用并查集模板可以快速得出。这次用 BFS 再写一遍。
同样是借助队列 + 邻接表。
代码
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
graph = [[] for _ in range(n)]
for i in range(n):
for j in range(n):
if isConnected[i][j] == 1:
graph[i].append(j)
queue = []
visited = [0 for _ in range(n)]
cnt = 0
for v in range(n):
if not visited[v]:
queue.append(v)
cnt += 1
while queue:
cur = queue.pop(0)
visited[cur] = 1
for u in graph[cur]:
if not visited[u]:
queue.append(u)
return cnt3. 克隆图
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
有些题目的翻译属实差劲，比如这题。不过还是弄明白了什么意思。
用递归的深度优先会比较方便做出来。要注意不能重复构造相同值的节点。所以在每次构造完一个节点后，放进数组里保存，下次还需要它的时候直接取用。
代码
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
nodes = [None for _ in range(101)]
def construct(root: Node) -> Node:
if not root: return None
if nodes[root.val]:
return nodes[root.val]
res = Node(root.val, [])
nodes[root.val] = res
for f in root.neighbors:
res.neighbors.append(construct(f))
return res
return construct(node)4. 最小高度树
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
核心的点在于证明，整个树的最小高度，是树中最长路径除以二上取整，且作为根的节点要么是两个（路径中节点数为偶），要么是一个（路径中节点数为奇）。
然后要找最长路径，应当先去找最长路径的起始节点，方法是：先随便选一个点，找离这个点最远的节点，记为 x ，然后找距离 x 最远的点 y ，这俩就是最长路径的起始节点。然后再找一下整条路径即可。
这点要自己证出来确实有难度。然后在求最长路径的过程中，可选 DFS 或者 BFS ，这里就自己写一遍 BFS 做法。
这里用 BFS 找最远的点，实际上可以看做树的层序遍历，队列中的最后一个节点，一定是最下面一层的节点，也就离根最远。
代码
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1: return [0]
graph = [[] for _ in range(n)]
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
parents = [0 for _ in range(n)]
def bfs(start: int) -> int:
visited = [0 for _ in range(n)]
queue = [start]
while queue:
cur = queue.pop(0)
visited[cur] = 1
for v in graph[cur]:
if not visited[v]:
queue.append(v)
parents[v] = cur
return cur
x = bfs(0)
y = bfs(x)
parents[x] = -1
path = []
while y != -1:
path.append(y)
y = parents[y]
m = len(path)
return [path[m >> 1]] if m % 2 else [path[m >> 1], path[(m >> 1) - 1]]
Comments NOTHING