Box
Box
Posts List
  1. 图的概念
  2. 图的表示
  3. DFS 和 BFS
    1. 广度优先搜索
    2. 深度优先搜索
    3. DFS对比BFS
  • 代码
  • Graph

    图的概念

    • 图的分类:
      • 有向图和无向图
      • 有权图和无权图
      • 连通图(从任意一个顶点都存在一条路径到达另一个任意顶点)和非连通图

    图的表示

    • 邻接矩阵(建议5000*5000以下)

    • 边的数组
    • 邻接表

    • 链式前向星

    DFS 和 BFS

    定义图结构:

    1
    2
    3
    4
    5
    6
    7
    8
    graph = {
    "A": ["B","C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D","E"],
    "D": ["B", "C", "E","F"],
    "E": ["C", "D"],
    "F": ["D"],
    }

    如图
    A的相邻元素为B、C
    B的相邻元素为A、C、D
    C的相邻元素为A、B、D、E
    D的相邻元素为B、C、E、F
    E的相邻元素为C、D
    F的相邻元素为D

    广度优先搜索
    • 队列实现:队列,入队列,出队列

    BFS优先遍历当前节点的相邻节点,即若当前节点为A时,则继续遍历的节点为B和C;当A的所有相邻节点遍历完以后,再遍历A相邻节点B和C的所有相邻节点,以B为例,在遍历B的相邻节点时,由于A已被访问过,则需要标记为已访问,在遍历B的相邻节点时,不再需要访问A。以此类推,完成无向图的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
    42
    43
    44
    45
    46
    # -*- coding: utf-8 -*-


    def BFS(graph, vertex):
    # 使用列表作为队列
    queue = []
    # 将首个节点添加到队列中
    queue.append(vertex)
    # 使用集合来存放已访问过的节点
    looked = set()
    # 将首个节点添加到集合中表示已访问
    looked.add(vertex)
    # 当队列不为空时进行遍历
    while(len(queue) > 0):
    # 从队列头部取出一个节点并查询该节点的相邻节点
    temp = queue.pop(0)
    nodes = graph[temp]
    # 遍历该节点的所有相邻节点
    for w in nodes:
    # 判断节点是否存在于已访问集合中,即是否已被访问过
    if w not in looked:
    # 若未被访问,则添加到队列中,同时添加到已访问集合中,表示已被访问
    queue.append(w)
    looked.add(w)
    print(temp, end=' ')
    print()


    if __name__ == "__main__":
    graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"],
    }
    # 由于无向图无根节点,则需要手动传入首个节点,此处以"A"为例
    print("BFS", end="\t")
    BFS(graph, "A")


    '''
    # 结果
    BFS A B C D E F
    '''
    深度优先搜索
    • 栈和回溯方式实现:栈,压栈,出栈
    • 递归方式实现

    DFS优先遍历与当前节点0相邻的一个节点1,然后再访问与节点1相邻但与节点0不相邻的节点,即若当前节点为A,则继续遍历B或C,再访问与B或C节点相邻且与A节点不相邻的节点,即节点D或E,若没有未遍历过的相邻节点,则返回访问上一个有未被访问过相邻节点的节点进行访问,依此遍历整个图,完成无向图的DFS。

    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
    42
    43
    44
    45
    46
    # -*- coding: utf-8 -*-


    def DFS(graph, vertex):
    # 使用列表作为栈
    stack = []
    # 将首个元素添加到队列中
    stack.append(vertex)
    # 使用集合来存放已访问过的节点
    looked = set()
    # 将首个节点添加到集合中表示已访问
    looked.add(vertex)
    # 当队列不为空时进行遍历
    while len(stack) > 0:
    # 从栈尾取出一个节点并查询该节点的相邻节点
    temp = stack.pop()
    nodes = graph[temp]
    # 遍历该节点的所有相邻节点
    for w in nodes:
    # 判断节点是否存在于已访问集合中,即是否已被访问过
    if w not in looked:
    # 若未被访问,则添加到栈中,同时添加到已访问集合中,表示已被访问
    stack.append(w)
    looked.add(w)
    print(temp, end=' ')
    print()


    if __name__ == "__main__":
    graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"],
    }
    # 由于无向图无根节点,则需要手动传入首个节点,此处以"A"为例
    print("DFS", end="\t")
    DFS(graph, "A")


    '''
    # 结果
    DFS A C E D F B
    '''
    DFS对比BFS
    DFS 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
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    # -*- coding: utf-8 -*-


    def BFS(graph, start, end):
    # 使用列表作为队列
    queue = []
    # 将首个节点添加到队列中
    queue.append(start)
    # 使用集合来存放已访问过的节点
    looked = set()
    # 将首个节点添加到集合中表示已访问
    looked.add(start)
    # 当队列不为空时进行遍历
    while(len(queue) > 0):
    # 从队列头部取出一个节点并查询该节点的相邻节点
    temp = queue.pop(0)
    nodes = graph[temp]
    # 遍历该节点的所有相邻节点
    for w in nodes:
    # 判断节点是否存在于已访问集合中,即是否已被访问过
    if w not in looked:
    # 若未被访问,则添加到队列中,同时添加到已访问集合中,表示已被访问
    queue.append(w)
    looked.add(w)
    if w == end:
    print(temp, ' ', end)
    return
    print(temp, end=' ')
    print()


    def DFS(graph, start, end):
    # 使用列表作为栈
    stack = []
    # 将首个元素添加到队列中
    stack.append(start)
    # 使用集合来存放已访问过的节点
    looked = set()
    # 将首个节点添加到集合中表示已访问
    looked.add(start)
    # 当队列不为空时进行遍历
    while len(stack) > 0:
    # 从栈尾取出一个节点并查询该节点的相邻节点
    temp = stack.pop()
    nodes = graph[temp]
    # 遍历该节点的所有相邻节点
    for w in nodes:
    # 判断节点是否存在于已访问集合中,即是否已被访问过
    if w not in looked:
    # 若未被访问,则添加到栈中,同时添加到已访问集合中,表示已被访问
    stack.append(w)
    looked.add(w)
    if w == end:
    print(temp, ' ', end)
    return
    print(temp, end=' ')
    print()


    if __name__ == "__main__":
    graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"],
    }
    # 由于无向图无根节点,则需要手动传入首个节点,此处以"A"为例
    print("BFS", end="\t")
    BFS(graph, "A", "F")
    print("-----")
    print("DFS", end="\t")
    DFS(graph, "A", "F")


    '''
    # 结果
    BFS A B C D F
    -----
    DFS A C E D F
    '''
    Supporting
    Scan, Support Daidai
    • WeChat scan
    • Alipay scan