图的遍历, since 2020.03.07

Depth-Firth Search(DFS)深度优先搜索:

用栈stack实现，记录每个vertex是否被访问过，其流程如下：

1 初始化，设置一个数据结构(比如字典)，记录每个结点是否被访问过，visited[i] = 0;

2 选择DFS的初始结点，如k，visited[k] = 1;

3 k塞入一个栈结构，S;

4 

while S非空:

    x = 栈顶元素

    if x的邻近节点有未被访问的节点w:

        w进栈, visited[w] = 1;

    else:

        x出栈.

2020.03.08 Sun

Breadth-First Search(BFS)广度优先搜索:

用队列(queue)实现。流程如下:

1 初始化，设置一个数据结构(比如字典)，记录每个结点是否被访问过，visited[i] = 0;

2 选择BFS的初始结点，如k，visited[k] = 1;

3 k塞入一个队列queue, S;

4 

while S非空:

    x=S首元素出队列;

    W = x的邻域点集合;

    for w in W:

        if visited[w] == 1: continue

        else: visited[w] = 1 并且w进S队列 (为标记任一点距离首发点的距离可将w与距离组成元组加入S)

复杂度: n个顶点和m条边的BFS复杂度O(n+m).[1]

reference:

1 M.T. Goodrich and etc., Data Structures and Algorithms in Python.