Data Structure & Algorithm
자료구조와 알고리즘, graph, dfs, bfs
준희닷
2024. 7. 1. 17:07
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 정점 간의 관계를 나타내는 데 사용됩니다. 그래프는 다양한 형태로 존재하며, 여러 가지 문제를 해결하는 데 유용합니다.
그래프의 기본 용어
- 정점(Vertex): 그래프의 노드를 의미합니다. 정점은 데이터를 저장할 수 있습니다.
- 간선(Edge): 정점 간의 연결을 나타냅니다. 간선은 방향이 있을 수도(유향 그래프) 없을 수도(무향 그래프) 있습니다.
- 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점들입니다.
- 경로(Path): 한 정점에서 시작하여 다른 정점으로 가는 일련의 간선들입니다.
- 가중치(Weight): 간선에 부여된 값으로, 두 정점 간의 비용이나 거리를 나타냅니다. 가중치가 있는 그래프를 가중치 그래프(Weighted Graph)라고 합니다.
그래프의 종류
- 무향 그래프(Undirected Graph): 간선에 방향이 없는 그래프입니다.
- 유향 그래프(Directed Graph): 간선에 방향이 있는 그래프입니다.
- 가중치 그래프(Weighted Graph): 간선에 가중치가 있는 그래프입니다.
- 비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프입니다.
그래프의 표현 방법
- 인접 행렬(Adjacency Matrix): 정점을 행과 열로 표현하고, 정점 간의 연결을 행렬의 값으로 나타냅니다. 연결되어 있으면 1, 연결되어 있지 않으면 0으로 표시합니다. 가중치가 있는 그래프에서는 가중치를 행렬의 값으로 표시합니다.
- 인접 리스트(Adjacency List): 각 정점에 대해 인접한 정점들의 리스트를 저장합니다. 인접 리스트는 공간 효율성이 좋고, 그래프의 정점과 간선이 많을 때 유리합니다.
1. 인접 행렬(Adjacency Matrix)
개념
인접 행렬은 정점을 행과 열로 표시하고, 두 정점 사이에 간선이 존재하면 해당 행렬 위치에 1(또는 가중치 값)을, 존재하지 않으면 0을 기록합니다.
시간 복잡도
- 공간 복잡도: (O(V^2)) - (V)는 정점의 수
- 간선 추가: (O(1))
- 간선 삭제: (O(1))
- 간선 존재 여부 확인: (O(1))
- 정점의 모든 인접 정점 탐색: (O(V))
장점
- 간선 존재 여부 확인이 빠름: 특정 두 정점 사이의 간선 존재 여부를 (O(1)) 시간에 확인할 수 있습니다.
- 간선 추가/삭제가 빠름: (O(1)) 시간에 간선을 추가하거나 삭제할 수 있습니다.
단점
- 공간 비효율성: 정점의 수가 많고 간선의 수가 적은 경우(희소 그래프) 많은 공간이 낭비됩니다.
- 정점의 인접 정점 탐색이 느림: 특정 정점의 모든 인접 정점을 찾으려면 행렬의 해당 행 전체를 확인해야 하므로 \(O(V)\) 시간이 걸립니다.
2. 인접 리스트(Adjacency List)
개념
인접 리스트는 각 정점에 대해 연결된 인접 정점의 리스트를 저장합니다. 배열이나 링크드 리스트를 사용해 구현할 수 있습니다.
시간 복잡도
- 공간 복잡도: (O(V + E)) - (E)는 간선의 수
- 간선 추가: (O(1))
- 간선 삭제: (O(E / V)) 평균적으로, 최악의 경우 (O(V))
- 간선 존재 여부 확인: (O(E / V)) 평균적으로, 최악의 경우 (O(V))
- 정점의 모든 인접 정점 탐색: (O(V)) 최악의 경우, 하지만 평균적으로 인접한 정점의 수에 비례
장점
- 공간 효율성: 희소 그래프의 경우 공간을 절약할 수 있습니다.
- 정점의 인접 정점 탐색이 빠름: 특정 정점의 모든 인접 정점을 빠르게 탐색할 수 있습니다. 평균적으로 인접한 정점의 수에 비례한 시간에 탐색이 가능합니다.
단점
- 간선 존재 여부 확인이 느림: 특정 두 정점 사이의 간선 존재 여부를 확인하려면 인접 리스트를 순회해야 하므로 최악의 경우 (O(V)) 시간이 걸립니다.
- 간선 삭제가 느림: 간선을 삭제하려면 인접 리스트에서 해당 간선을 찾아야 하므로 시간이 더 걸릴 수 있습니다.
선택 기준
- 그래프의 밀도: 그래프가 밀집되어 있고 간선의 수가 정점의 수의 제곱에 비례한다면 인접 행렬이 적합합니다. 반대로, 희소 그래프에서는 인접 리스트가 공간 효율성이 높습니다.
- 간선 존재 여부 확인: 두 정점 사이의 간선 존재 여부를 빈번하게 확인해야 한다면 인접 행렬이 더 효율적입니다.
- 정점의 인접 정점 탐색: 특정 정점의 모든 인접 정점을 자주 탐색해야 한다면 인접 리스트가 더 효율적입니다.
이러한 비교와 장단점을 고려하여, 그래프의 특성과 요구사항에 따라 적합한 표현 방법을 선택하는 것이 중요합니다.
시간 복잡도
인접 리스트를 사용한 구현
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
addEdge(vertex1, vertex2) {
if (!this.adjacencyList[vertex1]) this.addVertex(vertex1);
if (!this.adjacencyList[vertex2]) this.addVertex(vertex2);
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
removeEdge(vertex1, vertex2) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
(v) => v !== vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
(v) => v !== vertex1
);
}
removeVertex(vertex) {
for (let key in this.adjacencyList) {
if (this.adjacencyList[key].includes(vertex)) {
this.adjacencyList[key] = this.adjacencyList[key].filter(
(v) => v !== vertex
);
}
}
delete this.adjacencyList[vertex];
console.log('after this.adjacencyList[key]:', this.adjacencyList);
}
}
let basicGraph = new Graph();
basicGraph.addVertex('A');
basicGraph.addVertex('B');
basicGraph.addEdge('A', 'B');
basicGraph.addEdge('A', 'C');
basicGraph.addEdge('A', 'D');
basicGraph.addEdge('B', 'C');
basicGraph.removeVertex('A');
console.log(basicGraph);
그래프 탐색 알고리즘
- 너비 우선 탐색(BFS, Breadth-First Search): 시작 정점에서 가까운 정점부터 탐색하는 알고리즘입니다. 주로 큐(Queue)를 사용하여 구현합니다.
- 깊이 우선 탐색(DFS, Depth-First Search): 시작 정점에서 한 방향으로 깊이 탐색하다가 더 이상 갈 수 없으면 다른 경로로 탐색하는 알고리즘입니다. 주로 스택(Stack)을 사용하여 구현하거나 재귀 호출로 구현합니다.
너비 우선 탐색(BFS) 구현
bfs(vertex) {
// This function should accept a starting vertex
// Create a queue (you can use an array) and place the starting vertex in it
// Create an array to store the node visited
// Create an object to store nodes visited
// Mark the starting vertex as visited
// Loop as long as there is anything in the queue
// Remove the first vertex from the queue and push it into the array stores nodes visited
// Loop over each vertex in the adjacency list for the vertex you are visiting
// If it is not inside the object that stores nodes visited, mark it as visited and enqueue that vertex
let queue = [];
let results = [];
let visited = {};
let targetVertex;
queue.push(vertex);
visited[vertex] = true;
while (queue.length) {
console.log('queue:', queue);
targetVertex = queue.shift();
results.push(targetVertex);
this.adjacencyList[targetVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
});
}
return results;
}
깊이 우선 탐색(DFS) 구현 - 재귀
dfRecursive(startVertex) {
// The function should accept a starting node
// Create a 'results' variable to store the end result, to be returned at the very end
// Create an object 'visitied' to store visited vertices
// Create a helper function which accepts a vertex
// The helper function should return early if the vertex is empty
// The helper function should place the vertex it accepts into the visited object and push that vertex into the result array
// Loop over all of the values in the adjacencyList for that vertex
// If any of those values have not been visited, recursively invoke the helper function with that vertext
let results = [];
let visited = {};
let adjacencyList = this.adjacencyList;
/**
* { A : true, B: true, ... }
*/
function helper(vertex) {
if (!vertex) return null;
visited[vertex] = true;
results.push(vertex);
adjacencyList[vertex].forEach((neighbor) => {
if (!visited[neighbor]) {
return helper(neighbor);
}
});
}
helper(startVertex);
return results;
}
/**
const list = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B', 'E', 'F'],
E: ['C', 'D', 'F'],
F: ['D', 'E'],
};
*/
/**
* basicGraph.dfRecursive('A')
*
* [ 'A', 'B', 'D', 'E', 'C', 'F' ]
*/
깊이 우선 탐색(DFS) 구현 - 순환
dfIterative(vertex) {
// The function should accept a starting node
// Create a stack to help use keep track of vertices (use a list/ array)
// Create a list to store the end result, to be returned at the very end
// Create an object to store visited vertices
// Add the starting vertex to the stack, and mark it visited
// While the stack has something in it:
// Pop the next vertext from the stack
// If that vertext hasn't been visited yet:
// Mark it as visited
// Add it to the result list
// Push all of its neighbors into the stack
let stack = [];
let results = [];
let visited = {};
let targetVertex;
stack.push(vertex);
visited[vertex] = true;
while (stack.length) {
console.log('stack:', stack);
targetVertex = stack.pop();
results.push(targetVertex);
this.adjacencyList[targetVertex].forEach((neighbor) => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return results;
}
/**
const list = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B', 'E', 'F'],
E: ['C', 'D', 'F'],
F: ['D', 'E'],
};
*/
/**
*basicGraph.dfIterative('A')
*
* stack: [ 'A' ]
* stack: [ 'B', 'C' ]
* stack: [ 'B', 'E' ]
* stack: [ 'B', 'D', 'F' ]
* stack: [ 'B', 'D' ]
* stack: [ 'B' ]
*
* [ 'A', 'C', 'E', 'F', 'D', 'B' ]
*/
그래프의 응용
- 네트워크: 컴퓨터 네트워크, 소셜 네트워크 등에서 노드 간의 연결을 나타내기 위해 사용됩니다.
- 경로 찾기: 지도나 길 찾기 애플리케이션에서 최단 경로를 찾기 위해 사용됩니다.
- 일정 관리: 프로젝트 관리에서 작업 간의 의존성을 나타내기 위해 사용됩니다.
- 순위 계산: 페이지 랭크 알고리즘과 같은 검색 엔진에서 페이지의 중요도를 계산하기 위해 사용됩니다.
그래프는 데이터 간의 관계를 나타내는 데 매우 유용한 자료 구조로, 다양한 분야에서 중요한 역할을 합니다.