Module: BFS - 广度行走


Problem

2/6

BFS：开始（Python）

Theory Click to read/hide

BFS（广度优先搜索）是一种图遍历方法，在简单算法和高级算法中都非常常用。广度优先搜索的工作原理是逐步遍历图形的各个级别，从源节点开始并逐渐远离它。动画中清楚地显示了这一点。

要编写一个简单的 BFS，您需要能够使用队列，这是一种数据结构，可以让您从头到尾获取数据，还能够以以下形式存储图形邻接表。
 
算法的正式描述
1) 将开始搜索的顶点编号放入最初为空的队列中。
2) 从队列的开头提取顶点 U 并将其标记为在单独的数组中使用。
3) 在队列的末尾，添加我们可以使用从顶点 U 开始的边到达但尚未标记的所有顶点。
4) 如果队列为空，则连通图的所有节点都扫描完毕，否则返回步骤2。
 
工作难度
由于在最坏的情况下，算法会访问图的所有节点，当以邻接表的形式存储图时，算法的时间复杂度为 O(|V| + |E|)，其中 V 是集合图的顶点的集合，E 是边的集合。 ;
换句话说，该算法在边数 + 顶点数的最坏情况下有效。

 

Problem

一些村庄之间有道路相连，可以表示为无向图 。此图的顶点是村庄，边是村庄之间的道路（图中可能包含循环）。 已知在 village S 中有一个 artel 小贩。 每天早上，为了出售他们的小杂货店，小贩们会去尚未去过的村庄，并且从现在的村庄到那里有一条路。小贩的队伍总是分组，这样他们一天就可以绕过所有有路的村庄。
小贩们将在多少天内走访所有的村庄？编写一个 \(bfs()\) 函数，返回问题的答案。


输入
第一行包含3个整数n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - 村庄的数量，它们之间的道路数量，以及小贩团伙所在的村庄的数量。  ;在接下来的 m 行中，每行包含 2 个数字 u, v(\(1 < = u, v <= n\ )) - 有道路的两个村庄的数量。村庄索引为 1。

印记
打印一个数字——小贩走遍所有村庄需要多少天。
 
 
例子
<头> <日># <正文>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
Python
输入 输出
1 6 7 1
1 2
15
23
5 4
34
36
4 6		 4
Write the program below 
def bfs():            
n, m, s = map(int, input().split())
s -= 1
used = [False] * n  # True, если были в вершине i
tm = [0] * n    # tm[i] - день, когда в деревню i пришла артель коробейников
g = []     # список смежности
for i in range(n):
    g.append([])


for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

print(bfs())

     

Program check result

To check the solution of the problem, you need to register or log in!