[プログラマー]ネットワークPython

3916 ワード
テキストリンク
これはBFSを利用して再帰的に使用していない問題である.
今日もすぐに解けた失败.別のビットの読み取りと解放
DFSとBFSを使う方法は何ですか?
2つの接続を参照するためのグラフィック
  • DFS
    1.特定の組み合わせを選択した場合
  • DFSはグラフィック内のすべての頂点をチェックするので、限定された問題では無効です.
  • 頂点に関連するすべての頂点を参照する必要がある場合は、
    • が必要です.
  • パスが必要な場合は、
    • を選択します.
  • サイクルのパスを検索するには、
    • を選択します.
  • BFS
    1.特定の図面において、重みが同じである場合、最短パス検索時間は
    • である.
    ->BFSを使用します.これは深さを決定する必要がない問題なので、完全なナビゲーションを行うだけです.
    BFSの実装方法
    ->主にqueue実装を使用する
    1.隣接行列を格納するために1つのキューが必要であり、複数の頂点をチェックするために1つの配列が必要である
    2.ナビゲーションを開始するノードをキューに挿入し、そのノードがキュー内で移動していることを配列に表示します.
    3.開始ノードの隣接ノードをキューに挿入し、キューが空になるまで2回繰り返す
    4.行ったことのないノードをチェックし、すべてのノードが行くまで2～3回繰り返します
    from collections import deque

def solution(n, computers):
    answer = 0
    queue = deque()
    check = [True for i in range(n)]
    
    while True in check:
        first = check.index(True)
        queue.append(first)
        check[first] = False

        while queue:
            now = queue.popleft()

            for i in range(n):
                if check[i] and computers[i][now] == 1:
                    queue.append(i)
                    check[i] = False
        answer += 1
        
    return answer
    ルートノードが同じ場合は、すべて1つのネットワークに含まれます.
    だから答え+=1は2番目のwhileゲートが回転した後に追加されたのです
    Javascriptコールバック関数の理解
    HTML/CSS]Blurアニメーションの実装