DFS & BFS Algorithm

2037 ワード
テキストリンク

DFS


DFSはDepth-First探索、深さ優先探索とも呼ばれ、図形の中で深部を優先的に探索するアルゴリズムである.DFSを説明する前に,まず図形の基本構造を理解しなければならない.グラフィックライブラリは基本的にノード(N,Node)と幹線(E,Edge)として表現され,このときノードは頂点(V,Vertex)とも呼ばれる.グラフィックブラウズとは、1つのノードから複数のノードにアクセスすることです.また、2つのノード間に干渉接続がある場合は、「2つのノードが隣接している」ことを示します.
簡単にノードを都市、幹線を道路と考えます.

基本構成は上図の通りです.

DFS基本コード

# DFS 메소드 정의
from operator import truediv


def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
    ]
print()
# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

BFS


BFSの意味はbreadth First Search,幅優先ナビゲーションである.簡単に言えば,近接ノードから探索を開始するアルゴリズムである.DFSはできるだけ遠くのノードを優先的に閲覧するように動作するが,BFSは逆であるという.BFSを実施する際には,先入先出のキュー資料構造を採用することが慣例である.アルゴリズムを記述して隣接ノードをキューに繰り返し入れると、最初に入ったノードは自動的に終了し、近いノードから検索を開始します.

BFS基本コード

from collections import deque
# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = ' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
BOJ 7568
マルチ継承(大学院生類)