[WIL] DFS & BFS

今週習った

💡 그래프란, 정점과 정점을 연결하는 간선으로 이루어진 자료구조이고 아래는 그래프의 탐색 방법이다.

DFS (Depth First Search)

深さ優先検索は、ルートノード(または任意のノード)から開始し、左または右から次のブランチ(ブランチ)に移動する前に、ブランチを完全(最大深さ)に検索します.

はできるだけ深く入り込み、接続された隣接ノードがなくなると、前のノードに戻って再探索を行う.

すべてのノード

にアクセスする場合は、DFS方式を使用します.

再帰呼び出しまたはスタックによって実現され得る.

ノードにアクセスするかどうかをチェックしないと、無限ループに陥る危険があります.

スタックのLIFOフィーチャーに基づいて自動的に深さ優先探索が行われる.

DFS時間複雑度

隣接表:O(V+E)

の隣接行列で表されるパターン:O(V^2)

DFS実装

# DFS - 재귀호출 구현
# 방문한 내용이 초기화되지 않게 인자로 넘겨주는 것이다.
def dfs_recursive(start_v, visited):
    visited.append(start_v)

    for adj in graph[start_v]:
        if adj not in visited:
            # 해당 재귀호출에서 업데이트된 visited를 다시 인자로 넘겨준다.
            dfs_recursive(adj, visited)

    return visited
# [1, 2, 5, 6, 7, 3, 4] 재귀호출 결과
    
    
# DFS - 스택으로 구현
def dfs_stack(start_v):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start_v]

    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리 한다.
        top_v = stack.pop()
        visited.append(top_v)

        # 인접 노드가 visited에 stack에 쌓고 계속 반복문이 돌게 만들어준다.
        for adj in graph[top_v]:
            if adj not in visited:
                stack.append(adj)

    return visited
# [1, 4, 3, 5, 7, 6, 2] 스택 결과

BFS (Breadth First Search)

[幅](Width)優先的に検索します.ルートノード(または任意のノード)から開始し、まず現在の頂点付近のノードを検索します.
2つのノード間の最短経路または任意の経路を探す必要がある場合、BFS方式が使用される.

キューを使用して実装できます.

ノードにアクセスするかどうかをチェックしないと、無限ループに陥る危険があります.

キューのFIFOフィーチャーに従って、自動的に幅優先検索を行います.

BFS時間複雑度

隣接表:O(V+E)

の隣接行列で表されるパターン:O(V^2)

BFSの実装

from collections import deque

# BFS - deque를 이용하여 큐로 구현
def bfs_queue(start):
	# 시작 노드를 방문 처리한다.
    visited = [start]
    # 큐를 만들고 시작 노드를 담아준다.
    q = deque([start])

	# 큐가 빌 때까지 반복된다.
    while q:
        node = q.popleft()
        for adj in graph[node]:
        	# 인접 노드가 방문하지 않은곳이라면, 방문 처리와 큐에 쌓아준다.
            if adj not in visited:
                q.append(adj)
                visited.append(adj)
    return  visited

# [1, 2, 3, 4, 5, 6, 7] BFS 결과물이다.

📌 振り返る

DFSとBFSに直面するのは初めてで、これが本当のアルゴリズムだと感じた1週間でした.
最初は概念を理解して、例を見てから問題を解いて、今から見ればこのようにするのはあまり意味がなくて、理解してから転向して、問題の答えを見て、理解して、このようにして過ぎて、今週の目標になりました.
集中力が限界に達した時、私の主な言語JavaScriptを見て、ここでまた衝撃を受けました.
JSは私の主な言語で、数週間のPythonを使って、JSファイルの中で私がPythonの文法を使っているのを見て、振り返ってみると、私はただ勉強しているだけで、実際には自分の両手で多くのコードを書いたことがありません.
残りのアルゴリズム期間中は,アルゴリズムと主力言語の付加学習時間を割り当てるべきである.