[Data Structure] Graph
정의
네트워크 구조를 추상화한 모델. 간선(edge)으로 연결된 노드(node)의 집합이다.
그래프에 대한 설명과 구현은 이 곳에 잘 나와있다.
http://blog.benoitvallon.com/data-structures-in-javascript/the-graph-data-structure/
그래프의 용어를 그림 하나로 정리해보면 아래와 같다.
동적 그래프 자료구조는 인접리스트(adjacency list)로 표현 가능하다.
위 그래프를 인접리스트로 나타낸 것이다.
A : B C D
B : A E F
C : A D G
D : A C G H
E : B I
G : C D
H : D
I : E
Graph Class 구현하기
1let Dictionary = function Dictionary(){ let items = {}; }
2
3function Graph(){
4 let verices = []; // 정점은 배열로 저장
5 let adjList = new Dictionary();
6 // 인접리스트는 딕셔너리로 저장. 정점 이름이 key, 정점 리스트가 value.
7
8 /* 정점 추가하는 메서드 구현*/
9 this.addVertex = function(V) {
10 vertices.push(v); // 인자를 v에 받아서 verices 배열에 넣는다.
11 adjList.set(v, []); // key가 v이고 값은 빈 배열인 딕셔너리를 인접 리스트로 세팅한다.
12 };
13
14 /* 간선을 추가하는 메서드 구현 */
15 this.addEdge = function(v, w) {
16 adjList.get(v).push(w);
17 // v, w를 인자로 받아서 w를 v의 인접리스트에 넣고 v -> w 방향의 간선을 추가한다.
18 adjList.get(w).push(v);
19 // 무방향 그래프를 만들기 위해 w -> v 간선도 추가한다.
20
21 // get()은 mapObj.get(key) 형태로 사용하는데 key와 연결된 value를 반환한다.
22 };
23
24 /* 인접 리스트를 문자열로 바꾸기 */
25 this.toString = function() {
26 let s = '';
27 for (let i = 0; i < vertices.length; i++) {
28 s += vertices[i] + ' -> ';
29 let neighbors = adjList.get(vertices[i]);
30 for (let j = 0; j < neighbors.length; j++) {
31 s += neighbors[j] + ' ';
32 }
33 s += '\n';
34 }
35 return s;
36 }
37}
테스트 :
1let graph = new Graph();
2let myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];
3for (let i = 0; i < myVertices.length; i++){
4 graph.addVertex(myVertices[i]);
5}
6
7graph.addEdge('A', 'B');
8graph.addEdge('A', 'C');
9graph.addEdge('A', 'D');
10graph.addEdge('C', 'D');
11graph.addEdge('C', 'G');
12graph.addEdge('D', 'G');
13graph.addEdge('D', 'H');
14graph.addEdge('B', 'E');
15graph.addEdge('B', 'F');
16graph.addEdge('E', 'I');
17
18console.log(graph.toString());
19
20/* 출력 결과 */
21A -> B C D
22B -> A E F
23C -> A D G
24D -> A C G H
25E -> B I
26F -> B
27G -> C D
28H -> D
29I -> E