그래프(Graph) 자료구조
- 이전에 살펴본 트리는 그래프의 일종이다. 그래프는 트리를 포괄하는 개념이다.
- 그래프를 코딩하는 방법은 여러 가지가 있으나,
인접 리스트(Adjacency List)
를 사용하여 그래프를 만들어본다.
- 그래프는 유한한(가변적인) 꼭지점(노드)들의 집합으로 구성된 데이터 구조다. 이 꼭지점들의 집합에 순서가 없는 경우에는
무방향 그래프(Undirected graph)
이고, 순서가 있는 경우에는 방향 그래프(Directed graph)
라고 한다.
- 즉, 그래프는 노드와 노드들의 연결을 모은 것이다. 아래와 같은 이미지도 유효한 그래프다. 트리와 달리 부모 노드 같은 것은 없다. 그래프에서 노드는 모두 똑같이 취급되며, 단지 서로 다른 방식으로 연결될 뿐이다.
- 그래프 활용 사례
- 그래프 관련 용어
Vertex(정점)
: 노드, 위 그림에서 동그라미
Edge(간선)
: 노드 사이의 연결, 위 그림에서 노드를 잇는 줄
Undirected/Directed(무방향, 방향)
- 무방향 그래프는 양방향 연결이다. 간선에 방향이 없다.
- 방향 그래프는 간선에 정해진 방향(화살표)이 있다.
Weighted/Unweightet(가중, 비가중)
인접 리스트(Adjanceny List)
- 그래프의 노드와 간선 관계를 아래 이미지처럼 해시 테이블을 이용한 인접 리스트로 저장할 수 있다. 만약 아래 예시에서 C노드와 다른 노드들 간 간선을 확인하려면, 인접리스트의 ‘C’ 키에 있는
['B', 'D']
밸류를 통해 C 노드는 B노드 및 D노드와 연결되어 있다.
그래프의 기본 구조(Constructor)
class Graph {
constructor() {
this.adjacencyList = {};
}
}
정점 추가 메서드(addVertex)
- 정점 추가 메서드는, 입력 받은 정점이 인접리스트에 없으면 인접리스트에 정점 key에 빈 배열을 value로 지정해준다.
addVertex(vertex) {
if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
}
간선 추가 메서드(addEdge)
- 간선 추가 메서드는, 추가하려는 간선으로 이어진 두 개의 정점을 입력받고, 이들을 인접리스트에서 서로의 정점의 배열에 push하도록다.
addEdge(vertex1, vertex2) {
this.adjacencyList[vertex1].push(vertex2);
this.adjacencyList[vertex2].push(vertex1);
}
간선 제거 메서드(removeEdge)
- 간선 제거 메서드는, 제거하려는 간선으로 이어진 두 개의 정점을 입력받고, 인접리스트의 각각 정점들의 value에서 상대 정점만 제외하여 반환(filter 메서드 사용)된 배열을 재할당한다.
removeEdge(vertex1, vertex2) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(v => v !== vertex2);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1);
}
정점 제거 메서드(removeVertex)
- 정점을 제거하려면, 정점과 연결된 모든 간선들을 제거하고 그 정점도 삭제해야 한다.
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
}
코드 실행 결과
- 해당 클래스의 인스턴스 메서드들을 아래와 같이 실행하면, 주석과 같은 그래프 자료구조가 만들어진다.
const g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");