BFS & Topological Sorting

Posted on | In
Summary of BFS.

BFS

无需分层遍历的BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import deque

queue = deque()
seen = set()

queue.append(start)
seen.add(start)

while len(queue):
    head = queue.popleft()
    for neighbor in head.neighbors:
        if neighbor not in seen:
            queue.append(neighbor)
            seen.add(neighbor)

需要分层遍历的BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque

queue = deque()
seen = set()

queue.append(start)
seen.add(start)

while len(queue):
    size = len(queue)
    for _ in range(size):
        head = queue.popleft()
        for neighbor in head.neighbors:
            if neighbor not in seen:
                queue.append(neighbor)
                seen.add(neighbor)

Bidirectional BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from collections import deque

def doubleBFS(start, end):
    if start == end:
        return 1
    
    startQueue, endQueue = deque(), deque()
    startQueue.append(start)
    endQueue.append(end)
    step = 0
    
    startVisited, endVisited = set(), set()
    startVisited.add(start)
    endVisited.add(end)
    while len(startQueue) and len(endQueue):
        startSize, endSize = len(startQueue), len(endQueue)
        step += 1
        for _ in range(startSize):
            cur = startQueue.popleft()
            for neighbor in cur.neighbors:
                if neighbor in startVisited:
                    continue
                elif neighbor in endVisited: # 相交
                    return step
                else:
                    startQueue.append(neighbor)
                    startVisited.add(neighbor)
        step += 1
        for _ in range(endSize):
            cur = endQueue.popleft()
            for neighbor in cur.neighbors:
                if neighbor in endVisited:
                    continue
                elif neighbor in startVisited:
                    return step
                else:
                    endQueue.append(neighbor)
                    endVisited.add(neighbor)
    
    return -1

BFS in Binary Tree

  • Binary Tree Level Order Traversal
  • Binary Tree Serialization
  • Binary Tree Level Order Traversal II

BFS in Graph

  • Clone Graph
  • Word Ladder
  • Knight Shortest Path

BFS in Matrix

  • Number of Islands

Topological Sort

四种问法: 求任意1个Topological Order;是否存在;所有;是否存在且仅有一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def topSort(self, graph):
    # indegree represents how many nodes the node depends on
    node_to_indegree = self.get_indegree(graph)

    order = []
    start_nodes = [n for n in graph if node_to_indegree[n] == 0]
    queue = collections.deque(start_nodes)
    while len(queue):
        node = queue.popleft()
        order.append(node)
        for neighbor in node.neighbors:
            node_to_indegree[neighbor] -= 1
            if node_to_indegree[neighbor] == 0:
                queue.append(neighbor)
    
    return order

def get_indegree(self, graph):
    node_to_degree = {x: 0 for x in graph}

    for node in graph:
        for neighbor in node.neighbors:
            node_to_indegree[neighbor] += 1
    
    return node_to_indegree