[Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조)

탐색 알고리즘

DFS(Depth^[각주:1]-First Search)와 BFS(Breadth^[각주:2]-First Search)는 탐색 알고리즘이다. 그렇담, 탐색이란 무엇일까? 

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 탐색 알고리즘의 종류는 굉장히 다양한데 그중 DFS와 BFS는 그래프 탐색 알고리즘(Graph traversal algorithm)에 속한다. 그래프 탐색 알고리즘이란, 그래프의 모든 꼭짓점(Node 또는 Vertex라 한다)을 방문하는 알고리즘을 의미한다. 트리 탐색은(Tree traversal) 그래프 탐색의 특수한 일종이며, 방문한 노드는 다시 방문하지 않는다. 

 

그래프

그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조의 일종이다.

 

자료구조 & 알고리즘이란:

자료구조와 알고리즘

자료구조란 데이터의 표현 및 저장방법을 뜻한다. 프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다. 여기서 데이터의 표현은 데이터의 저장을 포함하는 개념이며, 데이터의 저장을 담당하는 것이 자료구조이다. 데이터 처리는 알고리즘, 즉 문제의 해결 방법을 뜻한다. 

 

간단하게 그린 그래프

 

리스트, 스택, 큐 등 한 번쯤은 이것들에 대해 들어보았을 것이다. 이것들은 선형구조로, 자료구조의 일종이다. 트리와 그래프는 비선형 구조의 자료구조로, 트리는 그래프의 일종이다. 간선으로 연결되어 있는 노드들은 인접하다(adjacent)라고 표현하며, 그래프를 구현하는 방식은 두 가지이다.

 

1. 인접 행렬(Adjecency matrix): 2차원 배열을 활용하여 그래프를 표현하는 방식

2. 인접 리스트(Adjacent list): 연결 리스트를 활용하여 표현하는 방식

 

인접 행렬

인접 행렬은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. A와 A끼리는 자기 자신이니 0으로 표현하고, 연결되어 있다면 1로, 아니라면 0으로 표현한다. 이걸 코드로 쓰면 다음과 같다.

 

graph = [
    [0, 1, 1, 0], 
    [1, 0, 1, 1], 
    [1, 1, 0, 0], 
    [0, 1, 0, 0]
]

 

인접 리스트

인접 리스트는 모든 노드에 연결된 노드들의 정보를 차례대로 기록하는 방식이다. C나 Java같은 언어들은 배열을 사용할 때 미리 배열의 크기를 지정하고 선언해야 하는데, 파이썬의 리스트는 append()와 같은 메소드를 가지고 있음으로 배열과 연결 리스트의 기능은 모두 제공한다. 그리하여 파이썬으로는 2차원 배열로도 그래프를 표현하기 충분하다. 

 

graph = [[] for _ in range(4)]

# 노드 A
graph[0].append('B')
graph[0].append('C')

# 노드 B
graph[1].append('A')

...

graph = [['B', 'C'], ['A', 'C', 'D'], ['A', 'B'], ['B']]

 

연결 리스트:

위에서 말했듯 배열을 선언할 때부터 길이가 이미 정해져 있어(정적이어서) 변경이 불가하다. 이를 해결하기 위해서 등장한 것이 바로 동적인 메모리 구성이다. 배열의 길이를 늘려야 할 때마다 데이터를 저장할 공간(변수)을 하나 더 생성해(=메모리 동적 할당) 그곳의 위치를 저장하여 배열처럼 서로 연결하는 것이다. 

 

쉽게 설명하자면, 변수를 생성할 때마다 '데이터를 저장할 장소'와, '다음 변수의 위치를 저장하는 장소'를 구분하여 생성한 뒤, 데이터와 위치를 모두 저장하는 것이다. 

 

연결 리스트

인접 행렬 vs 인접 리스트

1. 인접 행렬

    - 장점: 두 노드의 간선의 존재 여부를 바로 알 수 있음

    - 단점: 모든 관계를 기록함으로 노드의 개수가 많을 수록 불필요한 메모리 낭비가 일어남

2. 인접 리스트

    - 장점: 연결된 것들만 기록함 / 어떤 노드의 인접한 노드들을 바로 알 수 있음

    - 단점: 두 노드가 연결되어 있는지 확인이 인접 행렬보다 느림

 

이러한 장단점이 있기에 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프일 경우, 인접 리스트는 간선이 적은 희소 그래프일 경우 사용한다.

 

결론

 

그래프에 대해서 더 자세히 알고 싶다면 이 글을 읽어보길 추천한다. 

 

이로써 탐색 알고리즘과 그래프를 어떻게 코드로 표현하는지도 알았으니 이제 DFS와 BFS에 대해서 알아보도록 하자. 

 

다음 글: [Python] DFS & BFS

 

---

참조:

 

1. https://en.wikipedia.org/wiki/Graph_traversal

Graph traversal - Wikipedia

2. 이것이 코딩 테스트다 with 파이썬 - 나동빈 저

3. 윤성우의 열혈 자료구조 C언어를 이용한 자료구조 학습서 - 윤성우 저 

---

1. (위 표면에서 아래쪽 바닥까지의) 깊이 -출처: 네이버 사전 [본문으로]
2. 폭, 너비 -출처: 네이버 사전 [본문으로]