20224開発ログ(17日目)-完全ナビゲーションのためのアルゴリズム(2):深さ優先探索(DFS)と広さ優先探索(BFS)

DFSもBFSもブラウズしたノードには,アクセス処理を残す必要がある.

アクセスなどのリスト形式で表現し、TrueやFalseを使ってアクセスを残すかどうかは便利です.

BFSとは?

Breadth-First Searchの略として、幅-優先検索とも呼ばれます.図中の広い部分を優先的に探索する構造.キュー構造を使用します.
(DFSはスタック構造を利用している.)

2種類のグラフィック表現はDFSと同じ！

前面の位置を確認します.

BFSの実装

BFSを使用して、次の図面を実装します.

from collections import deque 		#큐(Queue) 구현을 위해 deque 라이브러리 사용

def bfs(graph, start, visited):
	queue=deque([start])
	visited[start] = True		#현재 노드를 방문 처리
    print(start, end=" ")		#현재 노드 출력
    
    while queue:			#큐가 빌 때까지 반복
        v = queue.popleft()		#큐에서 하나의 원소를 뽑아 출력
        print(v, end=' ')
        for i in graph[v]:		#해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                            
                            
graph = [				#graph 만들기
    [],					#0번 노드는 보통 문제에서 없으므로, 헷갈리게 하지 않기 위해 빈 리스트로 생성만 해 둠
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9

bfs(graph,1,visited)

<출력값>
>>> 1 2 3 8 7 4 5 6

入力値でグラフィック情報を受信し、グラフィックを入力します。

実際の問題では,上記のように直接図に情報を加えることはできない.
そのため、私たちは以下の考えが必要です.

#n이 노드의 수, m이 간선 정보의 수(노드 연결 정보)

matrix = [[] for _ in range(n+1)]
for i in range(m):
    p1, p2 = map(int, sys.stdin.readline().rstrip().split())	#p1, p2는 임시 노드 변수라고 생각하면 된다.
    matrix[p1].append(p2)
    matrix[p2].append(p1)
    
#위의 그림과 같은 그래프는 n=8일 것이며, m=9이다.