1. Given a source vertex s and a target vertex t, is there a path from s to t?
2. Given a source vertex s, find all reachable vertices and edges from s.
3. Given a graph, traverse all the nodes inside it.
4. ...
伪代码
MetaGraphSearchAlgorithm(graph, s):
#systematically explore all the vertices that are reachable from s.
# put in Bag as well as mark s accordingly
while bag is not empty:
extract a node from the bag
for neighbor in graph.neighbors(node):
if neighbor is not marked:
put neighbor in bag and mark neighbor.
# O(V+E*T)
# T: the time complexity for putting a node in bag 如果是queue
# 的结构，T=1
Breadth First Search
就像是近视的人找眼镜，剥洋葱似的先从最近的一圈开始找。For breadth first search algorithm, we will finish visiting all vertices that are reachable from source by k moves before visiting vertices that are reachable from source by k+1 moves. Thus we just need to replace the bag with a queue. 先放进bag的要先拿出来。
Data Structure: Maintain a FIFO queue, put all traversed nodes that haven't been expanded.
Expand a node s, e.g. visit/print its value
Generate s's neighbor nodes" reach out to its neighboring nodes
Termination condition: do a loop until the queue is empty
Optionally deduplicate visited nodes (typically for graph not for tree)
- e.g. each node is expanded only once
- e.g. each node is generated only once
分层打印Binary Tree
# q.size会动态变化，所以要在进循环之前就要记录，不然循环永远出不来
class Solution(object):
def layerByLayer(self, root):
"""
input: TreeNode root
return: int[][]
"""
# write your solution here
result = []
if not root:
return result
line = [root]
while line:
nextline = []
size = len(line)
for i in range (0,size):
curr = line.pop(0)
nextline.append(curr.val)
if curr.left:
line.append(curr.left)
if curr.right:
line.append(curr.right)
result.append(nextline)
return result
BFS(graph, s):
frontier = [s]
has_seen = set(s)#防止走出一个环，无法停止
while frontier:
next=[]
for u in frontier:
for v in neighbors(u):
if v not in has_seen:
next.append(v)
has_seen.add(v)
frontier = next
Given a binary tree, return the zigzag level order traversal of its nodes' values.也就是每一层变换访问顺序，从左到右-从右到左-从左到右。
BFS(root):
if not root:
return []
frontier = [root]
reverse = False
ans=[]
#在tree的结构不会需要has_seen，因为不会从叶子往根找。
while frontier:
next=[]
curr=[]
for u in frontier:
curr.append(u.value)
if u.left:
next.append(u.left)
if u.right:
next.append(u.right)
ans.append(curr if not reverse else curr[::-1])
frontier = next
reverse = not reverse
Check Islands
2. Given a 2d grid map of '1's(land) and '0's(water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Claim: At a given cell that contains '1', we perform a BFS from this node. After this is done, we find all the lands that is reachable from this '1' and all these lands define an island. When we do BFS, we shoud start from a land that
def BFS(grid, r, c, marked):
dr, dc = [-1,0,1,0],[0,1,0,-1]
marked.add((r,c))
while frontier:
next=[]
for r,c in frontier:
for d in xrange(4):
nr,nc = r+dr[d], c+dr[d]
if 0<=nr<len(grid) and 0<=nc<len(grid[0] #合法
and grid[nr][nc])=='1'#陆地
and (nr,nc) not in marked:#没走过
node = (nr, nc)
marked.add(node)
next.apped(node)
frontier = next
class Solution(object):
def numIslands(self, grid):
res, marked = 0, set()
for r in xrange(len(grid)):
for c in xrange(len(grid[0])):
if grid[r][c]=='1' and (r,c) not in marked:
res += 1
BFS(grid, r, c, marked)
return res
beginWord endWord
3. Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord such that:
only 1 letter can be changed at a time
each transformed word must exist in the word list. (beginWord is not a transformed word)
This is a BFS problem, because the vertex are the words, and edges are the changes.
import string
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
wordList = set(wordList)
if endWord not in wordList:
return 0
ans = 1
frontier = [beginWord]
used = set(frontier)
while frontier:
next = []
for word in frontier:
for p in xrange(len(word)):
for c in string.ascii_lowercase:
newWord = word[:p] + c + word[p+1:]
if newWord == endWord:
return ans+1
if newWord in wordList and newWord not in used:
used.add(newWord)
next.append(newWord)
frontier = next
ans += 1
return 0
Bipartite
4. Given an undirected graph, return true if and only if it is bipartite.
Bipartite: 2染色，使一个图的两个短点不一样的颜色；if we can split its set of nodes into 2 independent subsets A and B such that every edge in the graph has 1 node in A and another node in B.
input是adjacency list.
A graph is bipartite <-> this graph does not contain odd cycle. 对于BFS的spanning tree结构来说，就是有连接同一层的边, 因为跨层的环一定包含的是偶数条边，偶数条边一定是bipartite的。所以在算法的层面，实际上是在每一层检查一个node是否被探索过的同时还要检查它能不能和同一层的某一个node相连；如果相连，就不是二分图（bipartite）。直到把所有node都查看了位置。在修改模板伪代码的时候，（1）把has_seen变成一个hashset（2）利用BFS的性质，邻居的距离+1就是现在到root的距离 （3）比较两个距离。
class Solution(object):
def bipartite(self, graph):
"""
input : List<GraphNode> graph
return : boolean
"""
# write your solution here
visited = {}
for v in range(len(graph)):
if graph[v] not in visited and not self.bfs(graph, visited, graph[v]):
return False
return True
def bfs(self, graph, visited, u):
visited[u] = 0
frontier = [u]
while frontier:
next = []
for u in frontier:
for v in u.neighbors:
if v not in visited:
visited[v] = visited[u] + 1
next.append(v)
elif visited[v] == visited[u]:
return False
frontier = next
return True
class Solution(object):
def isCompleted(self, root):
"""
input: TreeNode root
return: boolean
"""
# write your solution here
if not root:
return True
flag = False
line = [root]
while line:
curr = line.pop(0)
if not curr.left:
flag = True
elif flag:
return False
else:
line.append(curr.left)
if not curr.right:
flag = True
elif flag:
return False
else:
line.append(curr.right)
return True
Kth Smallest Number in Sorted Matrix
class Solution(object):
def kthSmallest(self, matrix, k):
"""
input: int[][] matrix, int k
return: int
"""
# write your solution here
import heapq
rows, columns = len(matrix), len(matrix[0])
visited = {(0,0)}
minheap = []
heapq.heappush(minheap, (matrix[0][0], 0, 0))
count, curr = 0, None
while minheap and count<k:
curr, x, y = heapq.heappop(minheap)
count+=1
if x+1<rows and (x+1,y) not in visited:
visited.add((x+1,y))
heapq.heappush(minheap, (matrix[x+1][y], x+1, y))
if y+1<columns and (x,y+1) not in visited:
visited.add((x,y+1))
heapq.heappush(minheap, (matrix[x][y+1], x, y+1))
return curr
Closest Door
5. Given a m*n 2D grid initialized with 3 possible values: -1 for wall, 0 for a gate, inf means an empty room; fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with inf.
class Solution(object):
def wallAndGates(self, rooms):
if not rooms:
return
dr, dc = [-1,0,1,0],[0,1,0,-1]
N, C = len(rooms), len(rooms[0])
frontier, INF = [(r,c) for r in xrange(N)
for c in xrange(C) if rooms[r][c]==0], 2147483647
distance = 0
while frontier:
next = []
for r, c in frontier:
for d in xrange(4):
nr, nc = r+dr[d], c+dc[d]
if 0<=nr<N and 0<=nc<C and rooms[nr][nc]==INF:
rooms[nr][nc] = distance + 1
next.append((nr, nc))
frontier = next
distance += 1
