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

一部の村は道路でつながっており、無向グラフとして表すことができます。このグラフの頂点は村であり、端は村の間の道路です (グラフには循環が含まれる場合があります)。  村では  S のアルテル 行商人. 毎朝、小さな小間物を売るために、行商人は まだ行ったことのない村に行きますが、そこには現在の村から道があります。行商人のアルテルは、現在の村から道路があるすべての村を 1 日で回れるように、常にグループに分かれています。
行商人は何日ですべての村を訪れますか?問題の答えを返す \(bfs()\) 関数を書きます。


入力
最初の行には、3 つの整数 n、m、s (\(1 < = n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - 村の数、村の間の道路の数、行商人のギャングが本拠を置く村の数.  ; 次の m< /code> 行には、それぞれ u、v(\(1 < = u, v <= n\ )) - 間に道路がある 2 つの村の数。村は 1 でインデックスされます。

インプリント
行商人がすべての村を訪れるのに何日かかるか、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!