一、深度遍历
1.员工的重要性 leetcode 690
思路：深度遍历
"""
# Employee info
class Employee:
def __init__(self, id, importance, subordinates):
# It's the unique id of each node.
# unique id of this employee
self.id = id
# the importance value of this employee
self.importance = importance
# the id of direct subordinates
self.subordinates = subordinates
"""
class Solution:
def getImportance(self, employees, id):
"""
:type employees: Employee
:type id: int
:rtype: int
"""
self.res = 0
emp_infos = dict()
for employee in employees:
emp_infos[employee.id] = [employee.importance,employee.subordinates]
def dfs(subs):
for sub in subs:
self.res += emp_infos[sub][0]
dfs(emp_infos[sub][1])
dfs([id])
return self.res
2.图像渲染 leetcode 773
以中心点上下左右扩散
思路：深度搜索，遍历中心点的上下左右四个点，然后到达一个点，再继续遍历其到上下左右到节点，直到碰到边界，就返回
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
self.recode = []
self.m = len(image)
self.n = len(image[0])
def dfs(sr,sc,image):
directions = [[-1,0],[1,0],[0,-1],[0,1]]#上下左右
for d in directions:
new_sr = sr+d[0]
new_sc = sc+d[1]
if new_sr >= 0 and new_sr < self.m and new_sc >= 0 and new_sc < self.n:#未越界
if image[new_sr][new_sc] == image[sr][sc] and [new_sr,new_sc] not in self.recode:
print(new_sr,new_sc)
self.recode.append([new_sr,new_sc])
dfs(new_sr,new_sc,image)
dfs(sr,sc,image)
image[sr][sc] = newColor
for src in self.recode:
n_sr,n_sc = src[0],src[1]
image[n_sr][n_sc] = newColor
return image
3.岛屿的个数 leetcode200
思路：深度搜索
class Solution(object):
dx = [1,0,-1,0]
dy = [0,-1,0,1]
def numIslands(self, grid):
ans = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(grid,i,j)
ans +=1
return ans
def dfs(self,grid,i,j):
grid[i][j] = '.'
for k in range(4):
m = i+self.dx[k]
n = j+self.dy[k]
if m>-1 and m<len(grid) and n >-1 and n<len(grid[0]) and grid[m][n] == '1':
self.dfs(grid,m,n)
return
4.两点间路径条数
思路：深度遍历
# row, col = map(int, input().split())
# graph = []
# for _ in range(row):
# graph.append(list(map(int, input().split())))
# print(graph)
# x1, y1, x2, y2 = map(int, input().split())
dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]#上,下,右,左
M = 10 ** 9
res = [0]
graph = [[0, 1, 0, 0, 0], [0, 2, 3, 0, 0], [0, 0, 4, 5, 0], [0, 0, 7, 6, 0]]
row = 4
col = 5
x1, y1, x2, y2 = 0, 1, 3, 2
def dfs(x1, y1, visited):
if x1 == x2 and y1 == y2:
res[0] += 1
return
for i, j in dirs:#遍历4个方向,判断下一步哪步可行,然后从这步开始,继续深度遍历,直到到达终点
tmp_x = i + x1
tmp_y = j + y1
if 0 <= tmp_x < row and 0 <= tmp_y < col and graph[tmp_x][tmp_y] > graph[x1][y1]
and (tmp_x, tmp_y) not in visited:
dfs(tmp_x, tmp_y, visited | {(tmp_x, tmp_y)})
print (visited)
dfs(x1, y1, {(x1, y1)})
print(res[0] % M)
二、广度遍历
（一）图
- 图结构：节点、边
- 分类：有向图、无向图
- 特殊的图：二叉树（二叉搜索树）、普通树（并查集）、堆
- 连通图与非连通图
连通图（Connected Graphs）指图内任意两个节点间，总能找到一条路径连接它们，否则，为非连通图（Disconnected Graphs）。也就是说，如果图中包含岛（Island）,则是非连通图。如果岛内的节点都是连通的，这些岛就被成为一个部件（Component，有时也叫 Cluster）。
（二）算法
一、图结构（节点、边）
1.连通性（割点、边）
2.最小生成树
3.最短路径
计算给定的两个节点之间最短（最小权重和）的路径。算法能够实时地交互和给出结果，可以给出关系传播的度数（degree），可以快速给出两点之间的最短距离，可以计算两点之间成本最低的路线等等。
4.搜索（BFS和DFS）
5.欧拉回路
6.哈密尔顿回路
7.拓扑排序
二、分类（有向图、无向图）
三、特殊的图（二叉树、普通树(并查集)、堆）
参考文献：
【2】https://www.oreilly.com/library/view/graph-algorithms/9781492047674/
【3】https://www.tutorialspoint.com/parallel_algorithm/parallel_search_algorithm.htm
【4】书 https://learning.oreilly.com/library/view/graph-algorithms/9781492047674/ch03.html