Module: BFS - Đi bộ theo chiều rộng


Problem

2/6

BFS: Bắt đầu (Trăn)

Theory Click to read/hide

BFS (tìm kiếm theo chiều rộng) là một phương pháp duyệt đồ thị, thường được sử dụng trong cả thuật toán đơn giản và nâng cao. Tìm kiếm theo chiều rộng hoạt động bằng cách đi qua các cấp độ riêng lẻ của biểu đồ, bắt đầu từ nút nguồn và dần dần di chuyển ra khỏi nút đó. Điều này được thể hiện rõ ràng trong hình ảnh động.

Để viết một BFS đơn giản, bạn cần có khả năng làm việc với hàng đợi, một cấu trúc dữ liệu cho phép bạn lấy từ đầu và đưa nó vào cuối, đồng thời có thể lưu trữ biểu đồ dưới dạng của một danh sách kề.
 
Mô tả chính thức của thuật toán
1) Đặt số đỉnh bắt đầu tìm kiếm vào hàng đợi trống ban đầu.
2) Trích xuất đỉnh U từ đầu hàng đợi và đánh dấu nó là được sử dụng trong một mảng riêng.
3) Ở cuối hàng đợi, thêm tất cả các đỉnh mà chúng ta có thể tiếp cận bằng cách sử dụng cạnh từ đỉnh U và chưa được đánh dấu.
4) Nếu hàng đợi trống thì tất cả các nút của biểu đồ liên thông đã được quét, nếu không thì quay lại bước 2.
 
Khó khăn trong công việc
Vì trong trường hợp xấu nhất, thuật toán thăm tất cả các nút của đồ thị nên khi lưu trữ đồ thị dưới dạng danh sách kề, độ phức tạp thời gian của thuật toán là O(|V| + |E|), trong đó V là tập hợp của các đỉnh của đồ thị và E là tập hợp các cạnh.  ;
Nói cách khác, thuật toán hoạt động trong trường hợp xấu nhất đối với số cạnh + số đỉnh.

 

Problem

Một số làng được nối với nhau bằng các con đường, có thể được biểu diễn dưới dạng đồ thị vô hướng. Các đỉnh của biểu đồ này là các làng và các cạnh là các con đường giữa các làng (biểu đồ có thể chứa các chu trình). Được biết, trong làng S một artel Những người bán rong. Mỗi buổi sáng, để bán những món đồ lặt vặt nhỏ của họ, những người bán rong đi đến những ngôi làng chưa đến thăm và từ đó có một con đường từ ngôi làng hiện tại. Nhóm người bán rong luôn được chia thành từng nhóm để có thể đi khắp các làng có đường từ làng hiện nay đi trong một ngày.
Trong bao nhiêu ngày những người bán hàng rong sẽ đến tất cả các ngôi làng? Viết một hàm \(bfs()\) sẽ trả về đáp án cho bài toán.


Đầu vào
Dòng đầu tiên chứa 3 số nguyên n, m, s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - số làng, số đường giữa chúng và số làng nơi nhóm người bán rong đóng trụ sở.  ;Trong các dòng m sau mỗi dòng chứa 2 số u, v(\(1 < = u, v <= n\ )) - số của hai làng giữa hai làng có một con đường. Các làng được lập chỉ mục với 1.

Dấu ấn
In ra một số - những người bán rong sẽ mất bao nhiêu ngày để đi hết các ngôi làng.
 
 
Ví dụ
<đầu>

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
# Đầu vào Đầu ra
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!