(1) 그래프?

그래프란 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현한 자료구조로, 정점(Vertex)과 정점들을 연견하는 간선(Edge)로 구성된다. 일반적으로 정점은 원으로 표현하고, 간선은 화살표나 직선으료 표현한다.

그래프를 수학적으로 표현하면, 그래프 G에 대하여 G = (V,E)라고 표현한다.

여기서 V는 정점의 부분 집합, E는 간선의 부분 집합을 의미한다.

(2) 용어

• 인접(adjacent): 두 정점 Vi와 Vj가 연결되어 간선 (Vi, Vj)가 있을때 정점 Vi와 Vj가 인접되어 있다고 한다.
• 부속(incident): 두 정점 Vi와 Vj 사이 간선 (Vi, Vj)가 있을때 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속 되어 있다고 한다.
• 차수(degree): 정점에 부속되어있는 간선의 수. 방향그래프에서는 정점에 부속된 간선의 방향에 따라서 진입차수(in-degree)와 진출 차수(out-degree) 가 생긴다.
• 경로(path): 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것.
• 경로를 구성하는 간선의 수는 경로 길이(Path length) 라고 하는데 모두 다른 정점으로 구성된 경로를 단순 경로(simple path) 라고 한다(예:A-B-C)
• 사이클(cycle): 예를 들어 경로 A-B-C는 단순 경로지만, 경로 A-B-D-C-B-C-A는 단순경로가 아니다. 단순 경로중에서 경로의 시작 정점과 마지막 정점이 같은 경로를 사이클 이라고 한다.
• 무방향 그래프: 정점 Vi와 Vj가 연결되어 있으면 두 정점간 쌍방 통행이 가능한 그래프. (Vi, Vj) = (Vj, Vi)
• 방향 그래프: 연결에 방향성이 있어서, Vi에서 Vj로 연결되었다고 Vj에서 Vi로 연결되어있는 것은 아니다. (Vi, Vj) != (Vj, Vi)
• 가중 그래프: 간선에 가중치를 가지고 있는 그래프

(3) 구현

class Graph {

    constructor(_size = 5) {
        this.size = _size;
        this.vertices = new Array(_size);
        this.initializeMatrix();
    }

    initializeMatrix() {
        this.matrix = new Array(this.size);
        for (let i = 0; i < this.size; i ++) {
            this.matrix[i] = new Array(this.size);
            for (let j = 0; j < this.size; j ++) {
                this.matrix[i][j] = 0;
            }
        }
    }

    increaseMatrixSize() {
        const tempVertices = new Array(this.size + 1);
        const tempMatrix = [];
        for (let i = 0; i < this.size + 1; i++) {
            if (i < this.size) {
                tempVertices[i] = this.vertices[i];
            }
            tempMatrix[i] = new Array(this.size + 1);
            for (let j = 0; j < this.size + 1; j++) {
                if (i <= this.size - 1 && j <= this.size - 1) {
                    tempMatrix[i][j] = this.matrix[i][j];
                } else {
                    tempMatrix[i][j] = 0;
                }
            }
        }
        this.matrix = tempMatrix;
        this.vertices = tempVertices;
        this.size ++;
    }

    decreaseMatrixSize() {
        // TODO
    }

    addVertex(v) {
        if (v <= this.size && !this.vertices[v - 1]) {
            this.vertices[v - 1] = v;
        } else {
            if (v <= this.size + 1) {
                this.increaseMatrixSize();
                this.vertices[v - 1] = v;
            }
        }
    }

    addEdge(u, v, weight = 1) {
        u --; // 배열의 인덱스를 의미해야 하기 때문에 정점에서 1을 뺴준다
        v --; // 배열의 인덱스를 의미해야 하기 때문에 정점에서 1을 뺴준다
        if(this.vertices[u] && this.vertices[v]) {
            this.matrix[u][v] = weight;
            this.matrix[v][u] = weight;
        }
    }

    removeVertex(v) {
        v--;
        if (this.vertices[v]) {
            delete this.vertices[v];
            for (let i = 0; i < this.size; i++) {
                this.matrix[v][i] = 0; // 간선 초기화
            }
            for (let j = 0; j < this.size; j++) {
                this.matrix[j][v] = 0; // 간선 초기화
            }
        }
    }

    /**
     *
     * @param v {Number} 머리
     * @param u {Number} 꼬리
     */
    removeEdge(v, u) {
        v--;
        u--;
        if (this.matrix[v][u] !== 0 && this.matrix[u][v] !== 0) {
            this.matrix[v][u] = 0;
            this.matrix[u][v] = 0;
        } else {
            console.log('간선이 존재하지 않음');
        }
    }

    /**
     * 정점을 인자로 받아 인접한 정점의 배열을 반환하는 함수
     * @param v {Number} 정점
     * @returns {Array} 정점의 배열
     */
    adjacent(v) {
        v--;
        const adjacent = [];
        for (let i = 0; i < this.size; i ++) {
            if (this.matrix[v][i] > 0) {
                adjacent.push(i + 1);
            }
        }
        return adjacent;
    }

    /**
     * 정점 v에서 시작하는 깊이 우선 탐색(DFS)
     * @param v {Number} 정점
     * @constructor
     */
    DFS(v) {
        const stack = [];
        const visited = [];
        let cursor = null;
        if (this.vertices.indexOf(v) > -1) {
            stack.push(v);
            cursor = v;
        }
        while (stack.length > 0) {
            visited.push(cursor);
            const adjacent = this.adjacent(cursor);
            for (let i = 0; i < adjacent.length; i ++) {
                if (visited.indexOf(adjacent[i]) === -1) {
                    cursor = adjacent[i];
                    break;
                }
            }
            stack.pop();
            // push next

            // TODO
        }
    }

    /**
     * 정점 v에서 시작하는 너비 우선 탐색(BFS)
     * @param v {Number} 정점
     * @constructor
     */
    BFS(v) {
        const queue = [];
        const visited = [];

        if (this.vertices.indexOf(v) > -1) {
            queue.push(v);
        }

        while (queue.length > 0) {
            const cursor = queue.shift();
            visited.push(cursor);
            for (let i = 0; i < this.size; i++) {
                if (this.matrix[cursor - 1][i] === 1 && // 인접하면서,
                    visited.indexOf(i + 1) === -1 && // 방문된 적이 없고,
                    queue.indexOf(i + 1) === -1) { // 큐에 들어있지 않은 정점을,
                    queue.push(i + 1); // 큐에 추가한다.
                }
            }
        }
        console.log(visited);
    }
}


const graph = new Graph(5);

graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);

graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 5);
graph.addEdge(4, 5);

graph.addVertex(6);

graph.BFS(2);