DFS&BFSコンセプト

DFS

深さ優先ブラウズアルゴリズム

グラフィックで深さノードを優先ブラウズする

スタックデータ構造または再帰関数

を使用する.

動作過程

スタックに

ナビゲーション開始ノードを挿入し、

アクセスを処理する

スタック内の隣接ノードがアクセスしていない場合、アクセス処理のためにスタックに格納されます.アクセスされていない隣接ノードがない場合、最上位ノード

がスタックから取り出される.
ステップ

を2つ目のプロセスが実行できなくなるまで繰り返します.
※一般番号の低い隣接ノードは

へのアクセスを開始する.

ノードのブラウズ順序(スタックに入る順序)

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

graph = [
	[],         # 0번노드 : 존재하지 않음. 인덱스와 1번부터 시작하는 그래프 노드의 key를 맞추기 위함.
    [2, 3, 8],  # 1번노드 : 인접노드는 2,3,8 노드
    [1,7],      # 2번노드 : 인접노드는 1,7 노드
    [1,4,5],    # 3번노드 : ...
    [3,5],      # 4번노드 : ...
    [3,4],
    [7],
    [2,6,8],
    [1,7],      # 8번노드 : ...
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

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

DFS2

以下のI/Oを使用してデータを受信する場合、DFSアルゴリズムはどのように変化しますか?

I/O例

#입력
4 5 1
1 2
1 3
1 4
2 4
3 4
# 출력
1 2 4 3

コード#コード#

n, m, v = map(int, input().split(" "))
matrix = [[0] * (n+1) for _ in range(n+1)] # n + 1 하는 이유 : 0번 인덱스부터 하면 헷갈리니까 맞추려고
visited = [0] * (n+1)
for i in range(1, m+1):
    frm, to = map(int, input().split(" "))
    matrix[frm][to] = matrix[to][frm] = 1

def dfs(graph, visited, v):
    if visited[v] == 0:
        visited[v] = 1
        print(v, end = " ")
    for i in range(1, n+1):
        if graph[v][i] == 1 and visited[i] == 0:
            dfs(graph, visited, i)
dfs(matrix, visited, v)

BFS

幅優先ナビゲーションアルゴリズム

キューリソース構造

角画像(幹線)のコストは、同一の仮定における最短距離の計算に用いることができる.

動作過程

ナビゲーション開始ノードをキューに挿入し、

アクセスを処理する

キューから1つのノードを取り出し、そのノードのすべての隣接ノードのすべての未アクセスノードをキューに挿入し、アクセス処理

を行う.
ステップ

を2つ目のプロセスが実行できなくなるまで繰り返します.
※一般番号の低い隣接ノードは

へのアクセスを開始する.

ノードのナビゲーション順序(キューに入る順序)

from collections import deque

def bfs(graph, start, visited):
	# 큐 구현을 위해 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 = True

graph = [
	[],         # 0번노드 : 존재하지 않음. 인덱스와 1번부터 시작하는 그래프 노드의 key를 맞추기 위함.
    [2, 3, 8],  # 1번노드 : 인접노드는 2,3,8 노드
    [1,7],      # 2번노드 : 인접노드는 1,7 노드
    [1,4,5],    # 3번노드 : ...
    [3,5],      # 4번노드 : ...
    [3,4],
    [7],
    [2,6,8],
    [1,7],      # 8번노드 : ...
]

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

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

BFS2

以下のI/Oを使用してデータを受信する場合、BFSアルゴリズムはどのように変化しますか?

I/O例

#입력
4 5 1
1 2
1 3
1 4
2 4
3 4
# 출력
1 2 3 4

コード#コード#

n, m, v = map(int, input().split(" "))
matrix = [[0] * (n+1) for _ in range(n+1)] # n + 1 하는 이유 : 0번 인덱스부터 하면 헷갈리니까 맞추려고
visited = [0] * (n+1)
for i in range(1, m+1):
    frm, to = map(int, input().split(" "))
    matrix[frm][to] = matrix[to][frm] = 1

def dfs(graph, visited, v):
    if visited[v] == 0:
        visited[v] = 1
        print(v, end = " ")
    for i in range(1, n+1):
        if graph[v][i] == 1 and visited[i] == 0:
            dfs(graph, visited, i)
dfs(matrix, visited, v)