[알고리즘] 인접행렬(adjacency matrix) 구현 (JavaScript)

인접행렬(adjacency matrix)  자료구조 설명

- 인접 행렬(Adjacency Matrix) : 서로 다른 정점들이 인접한 상태인지를 2차원 배열로 나타냄

- 두 정점 사이의 관계 유무 확인에 용이하며, 가장 빠른 경로(shortest path)를 찾을 때 주로 사용

- 두 정점이 연결되어 있다면 1 (true), 두 정점이 연결되어 있지 않다면 0 (false)

 

코드 작성 포인트

1. 인접 행렬을 받을 변수 선언 및 할당

  - const matrix = [];

 

2. 버텍스 추가하기

  - matrix의 기존 엘리먼트들에 각각 0을 푸시해서 배열의 길이 늘려주기

  - 새 엘리먼트는 new 키워드와 fill 메소드로 배열을 생성하여 matrix에 push 하기

 

3. 버텍스 사이 간선 추가/삭제

  - 인덱스를 통한 조회 기능으로 엘리먼트를 0 또는 1으로 변환

  - 방향 그래프에서 간선 추가하기 : matrix[from][to] = 1

  - 무방향 그래프에서 간선 추가하기 : matrix[from][to] = 1, matrix[to][from]=1

 

 

인접행렬(adjacency matrix) 구현 코드 (JavaScript)

// 비가중치 방향 그래프의 인접행렬을 구현하기 위한 class 정의
class GraphWithAdjacencyMatrix {
  
  // graph의 constructor를 구현
  constructor() {
    this.matrix = [];
  }
  
  // 버텍스를 추가하는 메소드 구현
  addVertex() {
    const currentLength = this.matrix.length;
    // matrix의 요소인 각 배열 엘리먼트들에게 0을 push 해주기
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    }
    // 0을 요소로 가지는 CurrentLength + 1 길이의 배열을 matrix에 push해줌
    this.matrix.push(new Array(currentLength + 1).fill(0));
  }
  
  
  // vertex를 탐색하기
  // this.matrix에 vertex가 존재한다면 true를 리턴, 반대의 경우라면 false를 리턴
  contains(vertex) {
    return !!this.matrix[vertex];
  }
  // vertex와 vertex를 이어주는 edge를 추가
  addEdge(from, to) {
    // 현재 배열에서 인덱스의 최대값을 변수에 할당
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중 어느 하나라도 undefined라면 리턴
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면 리턴
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 1로 바꿔 Edge 표시
    this.matrix[from][to] = 1;
  }
  
  // from vertex와 to vertex 사이에 edge를 가지고 있는지 판단하는 메소드 구현
  hasEdge(from, to) {
    return !!this.matrix[from][to];
  }
  
  // from vertex와 to vertex가 관련이 없다면 edge를 제거하는 메소드 구현
  removeEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 0으로 바꿔줘서 관련이 없음을 표시
    this.matrix[from][to] = 0;
  }
  
}