그래프 개념

트리의 일종이긴 한데, 아주 특수한

용어

• Vertex = 노드
• Arc = 브랜치
• In-degree, out-degree (다른 vertex에서 오거나 나가는 거)
  - 방향 그래프 는 인디그리, 아웃디그리가 같음
  

그래프

• 방향 그래프 / 무방향 그래프
• 즉, 트리는 root가 있고 in-degree가 1개인 그래프

구현하기

이차원배열로 나타내면 간단하지만 공간복잡도 높음. 시간복잡도는 O(1)
Vertex의 제곱에 해당하는 공간 차지



배열이나 연결리스트로 구현하면 공간복잡도 낮은 대신 시간복잡도 높음 O(n)
vertext 개수와 arc 개수의 합에 해당하는 공간만 차지

• Arc는 양방향일 때 서로 다른 value, capa 가질 수 있음

class Graph {
    constructor() {
        vertices = [];
        matrix = [];
    }

    insertVertex(name) {
        // name 겹치는지 중복검사
        this.vertices.push(new Vertex(name));
        this.matrix.push([]); // Arc 넣을 때 이차원 배열 에러 안나게끔
    }
    #searchVertex(name) {
        for (let i = 0; i < this.vertices.length; i++) {
            if (this.vertices[i].name === name) {
                return i;
            }
        }
        return null;
    }
    insertArc(from, to, value, capacity) {
        const fromV = this.#searchVertex(from);
        const toV = this.#searchVertex(to);
        if (fromV === null || toV === null) {
            throw '찾는 버택스가 없습니다'; // 둘 중 하나라도 없으면 연결 불가능하니까
        }
        this.matrix[fromV][toV] = new Arc(value, capacity);
    }
}

class Vertex {
    constructor(name) {
        this.name = name;
    }
}
class Arc {
    constructor(value, capacity) {
        this.value = value;
        this.capacity = capacity;
    }
}

const g = new Graph();
g.insertVertex('a');
g.insertVertex('b');
g.insertVertex('c');
g.insertArc('a', 'b', 3);
g.insertArc('a', 'c', 2);
g.insertArc('c', 'a', 4);
g.insertArc('b', 'c', 1);
g;