[Algorithm] Javascript 인접 행렬(Adjacency Matrix) 생성하기

How to implement adjacency matrix in Javascript?

 

 

인접행렬 생성하기

 

문제

입력값으로 방향에 관한 정보와 정점에 관한 정보를 담은 2차원 배열을 받는다. 이를 토대로 인접행렬을 반환하라.

 

입력값으로 주어지는 2차원 배열은 3가지 정보를 가지고 있다.

• 0 번째 요소 : 간선의 시작 정점
• 1 번째 요소 : 간선의 도착 정점
• 2 번째 요소 : 방향("directed" OR "undirected)

 

 

소스 코드 구현

 

 

① 인접 행렬을 구하는 과정은 주어진 입력값 중 가장 큰 수를 구하는 것에서 시작한다.

② max 값을 토대로 인접행렬을 담을 2차원 배열을 생성한다.

③ 방향성에 따라서 간선의 정보를 인접행렬에 좌표를 찍는다.

 

function createAdjacencyMatrix(edges) {

    // 입력값 중 가장 큰 수를 구한다.
    let max = 0;
    for(let i=0; i<edges.length; i++){
        for(let j=0; j<2; j++){
            if(edges[i][j] > max) max=edges[i][j];
        }
    }


    // 비어있는 배열을 생성한다.
    // new Array()의 경우 주소를 참조하기 때문에 반드시 0으로 채워줘야한다.
    const adjacncyMatrix = new Array(max+1).fill(0).map((item)=>new Array(max+1).fill(0));
    
    // 인접행렬 내 좌표를 찍는다.
    for(let item of edges){
        const [from, to, direction] = item;

        if(direction === "directed"){
            adjacncyMatrix[from][to] = 1;
        }else if(direction === "undirected"){
            adjacncyMatrix[from][to] =adjacncyMatrix[to][from] = 1;
        }
        

    }

    return adjacncyMatrix;

}

 

 

 

[Algorithm] Javascript Graph 자료구조 인접행렬(Adjacency Matrix) 구현하기

 

[Algorithm] Javascript Graph 자료구조 인접 리스트(Adjacency List) 구현하기