그래프(Graph)

 

 

 

 

그래프(Graph)란?

정점(node 혹은 vertex)과 정점 사이를 잇는 간선(edge)으로 구성된 자료구조이다.

SNS, 네비게이션, 추천 알고리즘 등 실생활에 많이 사용된다. 

 

특징

• 정점들 사이 순서가 있는 경우엔 방향 그래프, 없는 경우엔 무방향 그래프라고 한다. 
• 간선에 가중치(비용 등)가 주어지면 가중 그래프가 된다. 
• 순환 혹은 비순환 구조를 이룬다.
• 노드 간에 2개 이상의 경로도 가능하다. 
• 부모 - 자식 관계라는 개념이 없다. (네트워크 모델)

 

그래프와 트리의 비교

	그래프	트리
관계	그래프 ⊃ 트리
방향성	방향, 무방향 모두 존재	방향만 존재
사이클	순환, 비순환 모두 존재 (자기 순환도 가능)	비순환만 존재
루트 노드	X	O
부모 - 자식	X	O
모델	네트워크 모델	계층 모델
간선의 수	자유 (없을 수도 있음)	N개의 노드를 가진 트리는 항상 N-1개의 간선을 가짐

 

 

구현

→ 컴퓨터 시스템에 그래프를 저장하는 방법은 크게 인접 행렬을 사용하는 방식과 인접 리스트를 사용하는 방식이 있다. 

 

// 인접 행렬
[[0, 1, 0, 0, 1], // 0번과 0번, 0번과 1번 ...
 [1, 0, 1, 0, 0],
 [0, 1, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [1, 0, 0, 1, 0]]

// 인접 리스트
[[1, 4], // 0번 노드의 연결 정보
 [0, 2],
 [1, 3],
 [2, 4],
 [3, 0]] 
 
// 인접 리스트 사용 시, 해시 테이블을 이용할 수도 있다.
{0: [1, 4],
 1: [0, 2],
 2: [1, 3],
 3: [2, 4],
 4: [3, 0]}

 

→ 인접 리스트는 인접 행렬에 비해 더 적은 공간을 차지한다. 그렇다고 인접 리스트가 항상 좋은 방법인 것은 아닌데,

모든 간선을 순회하는 것은 더 빠르지만 특정 간선이 있는지 여부를 확인하는 경우에는 인접 행렬이 더 빠르다. 

 

 

(참고) 인접 행렬과 인접 리스트의 빅오 표기 비교 (출처: https://www.udemy.com/course/best-javascript-data-structures)

 

 

→ 인접 리스트 접근법 (해시 테이블 이용)

class Graph{
    constructor(){
        this.adjacencyList = {};
    }
    // 정점 추가
    addVertex(vertex){
        if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    //간선 추가
     addEdge(v1,v2){
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }
    // 간선 제거
    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){
        while(this.adjacencyList[vertex].length){
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }
}