#3905. 【模板】图的遍历 广度优先搜索 深度优先搜索

【模板】图的遍历 广度优先搜索 深度优先搜索

题目描述

分别使用广度优先搜索和深度优先搜索实现图的遍历。

输入格式

第一行输入两个数 n,tn, \, t,表示有 nn 个顶点。接下来 tt 行,每行输入两个顶点 u,vu, \, v,表示加入一条连接 uuvv 的无向边。

输出格式

第一行输出广度优先搜索遍历的图依次访问的顶点,以空格分隔;第二行输出深度优先搜索遍历的图依次访问的顶点,以空格分隔。

注意:由于从不同顶点开始遍历结果不一致,因此无论是哪种搜素,都从字符 1 开始,题目保证遍历过程中不会需要重新随机选择顶点,详见样例

样例

15 20
1 2
1 3
1 11
1 14
2 6
3 4
3 6
3 8
3 8
4 5
4 13
4 14
4 11
5 7
5 12
7 9
8 12
9 10
9 15
12 13
1 2 3 11 14 6 4 8 5 13 12 7 9 10 15 
1 14 11 3 8 12 13 6 4 5 7 9 15 10 2

示例代码

  1. Python3Python3
# Author: guke

def BFS(graph, x):
    visit = []
    visit.append(x)
    visited = set()
    visited.add(x)
    while visit != []:
        vertex = visit.pop(0)
        print(vertex, end=' ')
        if vertex not in graph:
            continue
        nodes = graph[vertex]
        for node in nodes:
            if node not in visited:
                visit.append(node)
                visited.add(node)

def DFS(graph,s):
    visit = []
    visit.append(s)
    visited = set()
    visited.add(s)
    while visit != []:
        vertex = visit.pop()
        print(vertex, end=' ')
        if vertex not in graph:
            continue
        nodes = graph[vertex]
        for node in nodes:
            if node not in visited:
                visit.append(node)
                visited.add(node)

if __name__ == "__main__":
    n, t = [int(_) for _ in input().split()]
    graph = {}
    for _ in range(t):
        u, v = input().split()
        graph[u] = graph.get(u, []) + [v]

    BFS(graph, '1')
    print()
    DFS(graph, '1')