그래프 + 그래프 순회 정리

• 요즘 소소한 알고리즘 스터디를 하고 있다. 매주 주제를 정해서 하루에 하나씩 문제를 풀고 있는데, 이번주 주제가 DFS/BFS였다.
• DFS/BFS 공부를 할 겸, 그래프와 순회 강의를 들으며 정리한 것을 간략히 기록한다.

강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다.

---

그래프 (Graph)

: 노드/점들의 집합으로 구성된 데이터 구조

→ 간단히 말해, 노드와 노드 간의 연결(Connection)로 이루어진 구조이다

 

어디에 사용되나?

그래프는 다양한 곳에 사용된다. 밑의 리스트는 한 번쯤 주변에서 경험해봤을, 그래프의 사용처들이다.

1. SNS: Facebook이나 인스타그램 등. 사용자 간의 팔로우 관계가 그래프로 나타난다.
2. Location Mapping
3. 각종 추천 시스템 등

 

구조

아래 그림과 같이 노드를 나타내는 정점(Vertex)과 정점 사이의 연결을 나타내는 간선(Edge)으로 구성되어있다.

 

유형

그래프는 그 특징에 따라 유형을 나눌 수 있다.

• 가중/비가중(Weighted - Unweighted): 간선에 값(가중치)이 부여된 것. 알고리즘 문제 등에서 나오는 도로 간 통행료나 거리 등을 생각하면 된다.
• 방향/무방향(Directed - Undirected): 간선에 극성 유무에 따라 나뉜다. 극성이 없다면(방향이 없다면) 무방향, 방향이 있다면 방향 그래프로 나뉘며, 방향 그래프의 간선은 보통 방향을 나타낼 수 있도록 화살표로 그려진다.

 

그래프의 표현 방법

그래프의 표현 방법에는 아래와 같은 방법들이 존재한다.

 

1. 인접 행렬(Adjacency Matrix)

행렬의 형태로 정점 사이의 연결을 표현하는 방법. 자바스크립트에선 이차원 배열로 구현할 수 있다.

 

2. 인접 리스트(Adjacency List)

각 정점에 간선으로 연결된 다른 정점들의 리스트를 갖게 하는 것. 위와 같은 그래프는 자바스크립트에서 아래의 형태로 구현될 수 있다.

{
    "A": ["B", "E"],
    "B": ["A", "C"],
    "C": ["B", "D"],
    "D": ["C", "E"],
    "E": ["A", "D"]
}

 

 

→ 인접 행렬의 경우, 전체 접점 사이에 가능한 모든 간선을 표현하는 만큼, 간선이 적은 그래프에선 공간 효율이 떨어진다.

→ 또한 모든 간선에 대한 순회가 느리다. 실제론 간선이 존재하지 않는 데이터도 순회해야 하기 때문.

→ 인접 리스트는 위의 행렬의 단점을 갖지 않지만, 특정 간선을 확인하기 어렵다는 단점이 존재한다.

 

 

그래프 순회

어떤 때 쓰나?

1. 가장 가까운 경로 찾기
2. SNS 등의 '가장 가까운 ~ 추천' 서비스
3. 웹 크롤러
4. Peer to Peer 네트워킹 등

 

순회 방법

너비우선탐색(Breadth First Search, BFS), 깊이우선탐색(Depth First Search, DFS)이 있다.

 

DFS

: 시작 정점에서 시작해서, 간선을 따라 인접점의 다음 인접점을 차례대로 탐색하는 방법.

→ 재귀와 반복으로 구현할 수 있다.

 

재귀형 구현

아래와 같은 흐름으로 구현한다.

1. 정점을 인자로 받는 재귀 함수를 만든다.
2. 정점을 방문 처리한다.
3. 정점의 각 인접점에 대해, 아직 방문하지 않은 접점이면 재귀 함수를 호출한다.

이를 실제로 구현하면 아래와 같아진다.

const visited = {}; // 이미 방문한 접점을 기록
const adjacencyList = ...; // 각 접점 사이의 간선을 기록한 인접 리스트

const DFS = (v) => {
	if (!v) return null;
	visited[v] = true;

	adjacencyList[v].forEach((vertex) => {
		if (!visited[vertex]) return DFS(vertex); // 방문하지 않은 접점에 대해 재귀함수 호출
	});
};

// 순회를 1번 접점에서 시작한다 가정.
DFS(1);

 

 

반복형 구현

1. 접점을 넣을 스택을 생성한다.
2. 스택에 순회를 시작할 시작 접점을 넣는다.
3. 스택에 아무것도 남지 않을 때까지, 다음을 반복한다.
   1. 스택에서 접점을 꺼낸다.
   2. 꺼낸 접점이 아직 방문하지 않은 접점이라면, 방문 처리한다.
   3. 접점의 각 인접점에 대해, 아직 방문하지 않은 인접점을 스택에 넣는다.

const stack = [1]; // 시작 접점을 1이라 가정, 스택에 시작점을 넣은채로 시작
const visited = {};
const adjacencyList = ...; // 각 접점 사이의 간선을 기록한 인접 리스트

while (stack.length > 0) {
    const currentVertex = stack.pop();
    visited[currentVertex] = true;
    
    adjacencyList[currentVertex].forEach((v) => {
    	if (!visited[v]) {
        	stack.push(v);
        }
    });
}

 

※ 위의 방법은 같은 DFS이나, 출력값은 다르다고 한다.

개인적으로는 재귀가 직관적인 느낌이 들어서 선호하게 되었는데, 자바스크립트의 재귀 스택 때문에 그래프가 크면 클수록 반복을 사용하여 구현하는 것이 더 안전하다는 것 같다.

 

 

BFS

: 시작 정점에서 시작해서, 정점의 각 인접점을 먼저 탐색하는 방법

 

구현 방법

큐를 사용하여 BFS를 구현할 수 있다.

1. 큐를 생성하고, 순회를 시작할 정점을 넣는다.
2. 시작 접점을 방문 처리 한다.
3. 큐에 아무것도 남지 않을 때까지, 다음을 반복한다.
   1. 큐에서 접점을 꺼내, 방문하지 않은 접점이면 방문처리 한다.
   2. 접점의 각 인접점에 대해, 아직 방문하지 않은 인접점을 큐에 넣는다.

const queue = [1]; // 시작 접점을 1이라 가정, 큐에 시작점을 넣은채로 시작
const visited = {};
const adjacencyList = this.adjacencyList;

visited[start] = true;
let currentVertex;

while (queue.length > 0) {
	currentVertex = queue.shift();
	visited[currentVertex] = true;

	adjacencyList[currentVertex].forEach((vertex) => {
		if (!visited[vertex]) {
			visited[vertex] = true;
			queue.push(vertex);
		}
	});
}

 

---

• 알고리즘 문제를 풀기 위해 휘리릭 본 강의였다. 지금 더 찾아보니, DFS/BFS의 구현에 대해서는 더욱 깊게 파고들어갈 여지가 있는 것 같다. 나중에 조금 더 깊게 알아볼 시간을 가지려 한다.