图的遍历-邻接矩阵

541 次访问 2020-09-18

Walker

图是由顶点和边或弧两部分组成。顶点不分大小、主次，可以用一个一维数组来存储。
邻接矩阵：
用来表示顶点之间相邻关系的矩阵。用二维数组进行储存。

假设图有 5 个顶点，用一维数组表示为 vertex = ["A", "B", "C", "D", "E"]
用邻接矩阵, 即二维数组A[5][5]表示顶点间的关系.
A B C D E
A 0 1 0 1 0
B 1 0 1 0 1
C 0 1 0 1 1
D 1 0 1 0 0
E 0 1 1 0 0
如，若 "A" 与 "B" 是互连的, 则 A[0][1] 和 A[1][0] 都等于 1，反之则都等于 0
用二维数组表示：A = [
[0, 1, 0, 1, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 1],
[1, 0, 1, 0, 0],
[0, 1, 1, 0, 0]
]

同上一篇"图的遍历-邻接表"例子：
图有 8个顶点，使用一维数组表示顶点集合 vertex = [1, 2, 3, 4, 5, 6, 7, 8]
使用二维数组表示顶点间的关系：
A = [
[0, 1, 1, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
]
同样的，由于每个顶点都只能遍历一次，那么就应该再建立一个一维数组，用于记录顶点是否访问过。
初始化：visit = [0] * length

邻接矩阵建立：

vertex = [1, 2, 3, 4, 5, 6, 7, 8]

A = [
    [0, 1, 1, 0, 0, 0, 0, 0],
    [1, 0, 0, 1, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
]

深度优先搜索
递归：

def dfs_recursion2(vertex: List, A: List[List], vex: int) -> None:
    def _dfs(i):
        print(vertex[i], end="")
        visited[i] = 1
        for j in range(0, length):
            if A[i][j] and not visited[j]:
                _dfs(j)

    length = len(vertex)
    visited = [0] * length
    _dfs(vex - 1)
    for i in range(length):
        if not visited[i]:
            _dfs(i)

非递归：

def dfs_not_recursion2(vertex: List, A: List[List], vex: int) -> None:
    def _dfs(i):
        print(vertex[i], end="")
        visited[i] = 1
        op_stack.append((i, 1))
        while op_stack:
            i, j = op_stack.pop(-1)
            for j in range(j, length):
                if A[i][j] and not visited[j]:
                    print(vertex[j], end="")
                    visited[j] = 1
                    op_stack.append((i, j + 1))
                    op_stack.append((j, 1))
                    break

    length = len(vertex)
    visited = [0] * length
    op_stack = []
    _dfs(vex - 1)
    for i in range(length):
        if not visited[i]:
            _dfs(i)

广度优先搜索

def bfs_not_recursion2(vertex: List, A: List[List], vex: int) -> None:
    def _bfs(i):
        op_queue.append(i)
        while op_queue:
            i = op_queue.pop(0)
            if visited[i]:
                continue
            print(vertex[i], end="")
            visited[i] = 1
            for j in range(1, length):
                if A[i][j] and not visited[j]:
                    op_queue.append(j)

    length = len(vertex)
    visited = [0] * length
    op_queue = []
    _bfs(vex - 1)
    for i in range(length):
        if not visited[i]:
            _bfs(i)