class Graph {
    constructor() {
        this.vertices = [];
        this.edges = [];
        this.numberOfEdges = 0;
    }

    addVertex(vertex) {
        this.vertices.push(vertex);
        this.edges[vertex] = [];
        // 만약 edges[0]에 1, 3이 들어가있으면 0과 1, 0과 3을 연결하는 edge가 있는 것.
    }

    removeVertex(vertex) {
        const index = this.vertices.indexOf(vertex);

        if(index >= 0) {
            // 일단 vertex 목록에서 지워준다.
            this.vertices.splice(index, 1); 
        }

        while(this.edges[vertex].length) {
            // 지우려는 vertex와 연결된 edge들도 전부 지워줘야 함.
            const adjacentVertex = this.edges[vertex].pop();
            this.removeEdge(adjacentVertex, vertex);
        }
    }

    addEdge(vertex1, vertex2) {
        this.edges[vertex1].push(vertex2);
        this.edges[vertex2].push(vertex1);
        this.numberOfEdges++;
    }

    removeEdge(vertex1, vertex2) {
        // 첫 번째 점의 edges 목록에서 두 번째 점을 지우기 위해 index를 찾아준다.
        // 없으면 -1을 리턴한다.
        const index1 = this.edges[vertex1] ? this.edges[vertex1].indexOf(vertex2) : -1;
        const index2 = this.edges[vertex2] ? this.edges[vertex2].indexOf(vertex1) : -1;

        if(index1 >= 0) {
            this.edges[vertex1].splice(index1, 1);
            this.numberOfEdges--;
            // numberOfEdges는 한 번만 감소.
            // 실제로 edge는 하나만 지워지는거니깐.
        }

        if(index2 >= 0) {
            this.edges[vertex2].splice(index2, 1);
        }
    }

    size() {
        return this.vertices.length;
    }

    relations() {
        return this.numberOfEdges;
    }

    print() {
        console.log(this.vertices.map(vertex => {
            return `${vertex} => ${this.edges[vertex].join(', ').trim()}`;
        }, this).join('\n'));
    }
}

/* Depth First Search */
/* BFS와 흡사하지만, 큐 대신 스택을 사용한다. */
function dfs(matrix, root) {
    let node;
    const visited = new Array(matrix.length).fill(0);

    // stack에다가 시작 노드를 추가해준다.
    const stack = [root];

    // 시작 노드의 visited value를 'visited'로 표시.
    visited[root] = 1;

    // stack이 비게 되면 멈춤.
    while(stack.length > 0) {
        // stack에서 맨 위에 있는 노드를 하나 pop
        node = stack.pop();
        console.log(node);

        // pop한 노드에 인접한 모든 노드들을 검사한다.
        for(let i = 0; i < visited.length; i++) {

            // 인접한 모든 노드들 중, 연결되어 있는데 아직 방문하지 않은 노드가 있다면 
            // 방문 표시를 하고 stack에다가 집어넣는다.
            // 이렇게 stack에다 쌓으면, 일단 한 쪽으로 끝까지 진행하게 되기때문에
            // 가장 깊은 곳까지 먼저 들어갔다가, 다른 곳을 본다는 의미에서 깊이 우선 탐색.
            if(matrix[node][i] == 1 && visited[i] == 0) {
                // Visit node
                visited[i] = 1;
                // Push the element in the stack
                stack.push(i);
            }
        }
    }
}

const matrix = [
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [1, 0, 0, 1],
    [0, 0, 0, 1]
];

dfs(matrix, 0);

function bfs(graph, root) {
    const nodesDistances = {};

    for(let i = 0; i < graph.length; i++) {
        nodesDistances[i] = Infinity;
        // 모든 거리를 infinity로 설정하고 시작.
        // Infinity는 시작 노드에서 도달할 수 없음을 나타낸다.
    }

    nodesDistances[root] = 0;
    // 시작 노드의 시작 노드로부터 거리는 0이다.

    const queue = [root];
    // 방문해야 할 노드들을 담을 큐.
    let current; 
    // 현재 방문중인 노드를 담는 변수.

    while(queue.length != 0) {
        // 방문해야 할 노드들이 더 이상 없을 때까지 반복
        current = queue.shift();
        // 큐에서 방문할 노드를 꺼내면서 loop를 시작.
        // 맨 처음에는 root 노드를 꺼냄.

        const curConnected = graph[current];
        // 현재 노드와 다른 모든 노드들의 관계를 가져온다.
        // 그래프의 각 index에는 그 노드와 어떤 노드들이 연결되어있는지를 나타내는 배열이 들어가있다는 것을 기억하자.
        const neighborIdx = [];
        // 현재 노드와 연결되어있는 노드들을 담을 배열.
        let idx = curConnected.indexOf(1);
        // 현재 노드와 다른 노드들의 관계를 나타내는 배열에서 처음으로 나타나는 1을 찾는다. 
        // 해당 배열에서 1은 연결되어있다는 것을 의미함.
        // 만약 1을 발견하지 못하면, indexOf 메소드는 -1을 반환한다.
        
        while(idx != -1) {
            neighborIdx.push(idx);
            // idx가 -1이 아니라는 건 1을 발견했다는 뜻이므로, 그 index를 neighborIdx 배열에다 저장.
            idx = curConnected.indexOf(1, idx + 1);
            // 처음 발견된 1의 다음 index부터 또 1을 탐색.
            // 연결된 또 다른 노드를 찾아간다는 뜻.
        }
        // 여기까지 하면, 현재 노드와 연결된 모든 노드들이 neighborIdx에 저장됨.
        
        // 이제 그 노드들을 돌며 distance를 구할 차례.
        for(let j = 0; j < neighborIdx.length; j++) {
            if(nodesDistances[neighborIdx[j]] == Infinity) {
                // Infinity면 아직 distance를 설정해주지 않았다는 뜻.
                nodesDistances[neighborIdx[j]] = nodesDistances[current] + 1;
                // 바로 이웃한 노드들이기 때문에 현재 노드의 distance에서 1을 더해주면 된다.
                queue.push(neighborIdx[j]);
                // 이제 그 이웃 노드들의 이웃들을 또 방문하기 위해, 이웃 노드들을 queue에 넣어준다.
            }
        }
    }
    return nodesDistances;
}

const graph = [
    [0, 1, 1, 1, 0],
    [0, 0, 1, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0]
];
console.log(bfs(graph, 1));