Graph
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
정점(vertex) : 하나의 점
간선(edge) : 정점들을 연결하는 하나의 선. 가중치와 방향을 가질 수 있음
직접적인 관계가 있는 경우 두 정점을 이어주는 간선이 존재하고 간접적인 관계라면 몇개의 정점과 간선으로 이루어짐
단방향 그래프 directed graph
간선이 방향이 존재하며 간선의 방향으로만 이동할 수 있음
무방향 그래프 undirected graph
두 정점을 연결하는 간선에 방향이 없는 그래프
가중치 그래프
두 정점을 이동할 때 비용이 드는 그래프
완전 그래프
모든 정점이 간선으로 연결되어 있는 그래프
용어
•
진입차수 in-degree : 한 정점에 진입하는 간선(들어오는 간선)의 개수
•
진출차수 out-degree: 한 정점에 진출하는 간선(나가는 간선)의 갯수
•
인접 adjacency : 두 정점에 간선이 직접 이어져있는 경우, 두 정점은 인접
•
자기 루프 self loop : 정점에서 출발한 간선이 자기 자신에게 진입하는 경우
•
사이클 cycle : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우
그래프 표현방식
인접 행렬
그래프의 정점들간 인접함을 2차원 배열로 작성하여 표시
각 정점들 사이에 간선이 존재하는지 여부를 0이나 1로 나타냄
인접 행렬 구현하기
// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
constructor() {
this.matrix = [];
}
addVertex() {
//버텍스를 추가합니다.
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {
this.matrix[i].push(0);
}
this.matrix.push(new Array(currentLength + 1).fill(0));
}
contains(vertex) {
//TODO: 버텍스가 있는지 확인합니다.
return (this.matrix[vertex] !== undefined);
}
addEdge(from, to) {
const currentLength = this.matrix.length;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//TODO: 간선을 추가할 수 없는 상황에서는 추가하지 말아야 합니다.
if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//TODO: 간선을 추가해야 합니다.
this.matrix[from][to] = 1;
}
hasEdge(from, to) {
//TODO: 두 버텍스 사이에 간선이 있는지 확인합니다.
return this.matrix[from][to] ? true : false;
}
removeEdge(from, to) {
const currentLength = this.matrix.length;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//TODO: 간선을 지울 수 없는 상황에서는 지우지 말아야 합니다.
if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//TODO: 간선을 지워야 합니다.
this.matrix[from][to] = 0;
}
}
JavaScript
복사
•
장점 : 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1)의 시간복잡도면 가능, 구현이 비교적 간편
•
단점 : 모든 정점에 대한 간선 정보를 대입해야하므로 O(n^2)의 시간복잡도 소요, 무조건 2차원 배열이 필요하므로 필요 이상의 공간 낭비
인접 리스트
// undirected graph (무향 그래프)
// adjacency list (인접 리스트)
class GraphWithAdjacencyList {
constructor() {
this.vertices = {};
}
addVertex(vertex) {
// TODO: 정점을 추가합니다.
// 넘겨받은 인자(정점)은 키가 되며, 빈 배열을 값으로 할당합니다.
// 이미 존재하는 정점이라면, 덮어 씌워지지 않아야 합니다.
if (!this.vertices[vertex]) {
this.vertices[vertex] = [];
}
}
contains(vertex) {
// 인자로 넘겨받은 정점의 존재여부를 반환합니다.
return !!this.vertices[vertex];
}
addEdge(fromVertex, toVertex) {
// TODO: 간선을 추가합니다.
// - fromVertex의 인접 리스트에 toVertex를 추가하고
// - toVertex의 인접 리스트에 fromVertex를 추가합니다.
// 넘겨받은 2개의 정점 모두 존재하는 정점이어야 합니다.
if (!this.contains(fromVertex) || !this.contains(toVertex)) {
return;
}
if (!this.hasEdge(fromVertex, toVertex)) {
this.vertices[fromVertex].push(toVertex);
}
if (!this.hasEdge(toVertex, fromVertex)) {
this.vertices[toVertex].push(fromVertex);
}
}
hasEdge(fromVertex, toVertex) {
// 만약 정점(fromVertex)이 존재하지 않는다면
if (!this.contains(fromVertex)) {
// false를 반환합니다
return false;
}
// 존재한다면 해당 정점의 리스트에 toVertex가 포함되어있는지 반환합니다
return !!this.vertices[fromVertex].includes(toVertex);
}
removeEdge(fromVertex, toVertex) {
// TODO: 간선을 삭제합니다.
// 인자로 넘겨받은 두 정점이 모두 존재한다면
// - fromVertex의 인접 리스트에 있는 toVertex를 삭제하고
// - toVertex의 인접 리스트에 있는 fromVertex를 삭제합니다.
if (!this.contains(fromVertex) || !this.contains(toVertex)) {
return;
}
if (this.hasEdge(fromVertex, toVertex)) {
const index = this.vertices[fromVertex].indexOf(toVertex);
this.vertices[fromVertex].splice(index, 1);
}
// TODO: 두번째 정점의 인접 리스트에 첫번째 정점이 있을 경우
if (this.hasEdge(toVertex, fromVertex)) {
const index = this.vertices[toVertex].indexOf(fromVertex);
this.vertices[toVertex].splice(index, 1);
}
}
removeVertex(vertex) {
// TODO: 정점을 삭제합니다.
// 인자로 넘겨받은 정점(A)이 존재한다면
// - 이 정점(A)을 삭제함은 물론,
// - 다른 모든 정점들의 리스트를 순회하며 넘겨받은 정점(A)과 이어져 있는 간선을 제거합니다
if (this.contains(vertex)) {
for (let key in this.vertices) {
if (this.hasEdge(key, vertex)) {
this.removeEdge(key, vertex);
}
}
delete this.vertices[vertex];
}
}
}
JavaScript
복사
•
장점 : 연결 정보를 탐색할 때 O(n)의 시간 (n : 간선의 갯수)
•
단점 : 필요한 만큼의 공간만 사용해 공간의 낭비가 없음
탐색 방법
그래프의 모든 정점을 한 번씩 탐색하는 것이 목적
너비 우선 탐색 BFS (Breadth-First Search)
시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선방문하는 방법입니다. 일반적으로 QUEUE를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현합니다.
•
장점 : 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장, 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리
•
단점 : 큐를 사용하여 다음 탐색 노드들을 저장하기 때문에 노드의 수가 많을수록 필요없는 노드들까지 저장해야하므로 큰 저장공간 필요
평균 탐색 노드의 수 = (b^d - 1) / (b - 1) + (1 + b^d) / 2 (b : 가지 수, d : 깊이)
// 인접 행렬을 인자로 받는 경우
function bfs(matrix, from, to) {
const check = new Array(matrix.length).fill(false);
const queue = [from];
check[from] = true;
while (queue.length > 0) {
let now = queue.shift();
if (now === to) return true;
for (let i = 0; i < matrix[now].length; i++) {
if (matrix[now][i] === 1 && !check[i]) {
queue.push(i);
check[i] = true;
}
}
}
return false;
}
// 인접 리스트를 인자로 받는 경우
function bfs(adjList, vertex, visited) {
const queue = [vertex];
visited[vertex] = true;
while (queue.length > 0) {
let now = queue.shift();
for (let i = 0; i < adjList[now].length; i++) {
if (!visited[adjList[now][i]]) {
queue.push(adjList[now][i]);
visited[adjList[now][i]] = true;
}
}
}
}
JavaScript
복사
깊이 우선 탐색 DFS (Depth-First Search)
갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회하는 방식입니다. 간단히 재귀호출을 사용하여 구현하거나 스택을 사용하여 구현
•
장점 : BFS에 비해 저장공간의 필요성이 적음, 백트래킹을 해야하는 노드들만 저장, 찾아야하는 노드가 깊은단계에 있을수록, 그 노드가 좌측에 있을수록 BFS 보다 유리
•
단점 : 답이 아닌 경로가 매우 깊다면 그 경로에 깊이 빠질 우려가 있음
평균 탐색 노드의 수 = {(1 + d) + (b^(d + 1) - 1)(b - 1)} / 2