Adjacency list+DFS,BFS(Python)

Adjacency list+DFS,BFS(Python)

노드 간의 관계가 주어지고 이를 탐색하기 위해서는 먼저 그래프로 표현해야 합니다.

그래프는 리스트 자료구조와 행렬 자료구조 두 가지의 형태로 나눌 수가 있는데,

그림 1과 같이 변으로 연결된 두 개의 노드를 서로 인접한 관계라고 하며 이러한 인접한 관계를 리스트로 구성한 것 을 인접리스트(Adjacency list)라고 합니다.

그림1(인접한 관계)

위의 1,2번 노드를 인접 리스트로 구성하면 [[ ],[2],[1]]로 표현하며 각각의 인덱스는 노드 번호를 가리킵니다.

예시로 알아보는 인접 리스트

주어진 임의의 노드 관계를 이용하여 인접 리스트 만들기 (가장 큰 노드 번호가 5, 노드는 총 5개, 간선 개수 5)

graph=[[] for _ in range(6)] for _ in range(5): A,B=map(int,input().split()) graph[A].append(B) graph[B].append(A) print(graph)

예시1

이 글에서는 위에서 다룬 인접 리스트를 활용하여 dfs와 bfs에 대해 알아보도록 하겠습니다.

깊이 우선 탐색(Depth First Search)이란?

DFS는 한 루트로 계속 들어가 탐색한 뒤 탐색을 마치면 다시 돌아가 방문하지 않은 루트로 들어가 탐색하는 과정을 말하며 보통 모든 경우의 수를 찾기 위한 백 트래킹 시 자주 사용되는 탐색 알고리즘입니다.

위에서 다룬 예시 1로 노드 정보가 주어지고 방문할 수 있는 노드가 여러 개인 경우에 작은 노드부터 방문한다고 할 때,

방문 순서는 다음과 같이 구할 수 있습니다.

def dfs(v): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(i) graph=[[] for _ in range(6)] visited=[False]*6 #방문 여부 for _ in range(5): A,B=map(int,input().split()) graph[A].append(B) graph[B].append(A) for i in graph: #노드번호에 따라 정렬 i.sort() dfs(1) print() print(visited) print(graph)

넓이 우선 탐색( Breadth First Search)이란?

시작 노드로부터 가까운 노드를 순차적으로 탐색하는 알고리즘입니다.

연결되어 있는 노드를 큐에 넣고 순차적으로 추출해나가는 과정을 통해 구현합니다.

from collections import deque def bfs(start): 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 graph=[[] for _ in range(6)] visited=[False]*6 for _ in range(5): A,B=map(int,input().split()) graph[A].append(B) graph[B].append(A) for i in graph: i.sort() bfs(1) print() print(visited)

from http://lbdiaryl.tistory.com/219 by ccl(A) rewrite - 2021-12-01 17:27:01