그래프 구현

그래프 (Graph) 관련 용어

• 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함
• 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함)
• 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드)
• 참고 용어
  • 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수
  • 진출 차수 (Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수
  • 경로 길이 (Path Length): 경로를 구성하기 위해 사용된 간선의 수
  • 단순 경로 (Simple Path): 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로 ( [집 -> 지하철 -> 회사 -> 지하철 -> ...]처럼 중간에 가리키는 간선이 중복될 경우 단순 경로 x, [집 -> 지하철 -> 회사 -> 버스 -> 집]처럼 처음과 끝이 중복되는 건 단순 경로임)
  • 사이클 (Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우 [집 -> 지하철 -> 회사 -> 버스 -> 집]

인접 리스트

간선이 많지 않고 퍼져있는 그래프에 적절(노드(정점)의 개수가 아주 많지만 서로 다 연결이 되어있지 않은 경우)

공간을 적게 차지한다.

모든 간선을 순회하는 속도가 빠르다.

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
    }
    addEdge(vertex1, 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) {
        while (this.adjacencyList[vertex].length) {
            const adjacentVertex = this.adjacencyList[vertex].pop();
            this.removeEdge(vertex, adjacentVertex);
        }
        delete this.adjacencyList[vertex]
    }
}

 

인접 행렬

특정 간선을 확인해야 할 때 빠르다.