[자료구조 with javascript] Graph 그래프 탐색 개념 정리(인접행렬)

Graph란?

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.

간접적인 관계라면 몇 개의 점과 선에 걸쳐 있다.

하나의 점을 그래프에서는 정점(vertex)이라고 표현하고,

하나의 선은 간선(edge) 이라고 한다.

 

즉, 정점과 간선으로 이루어진 자료구조의 일종

무방향 그래프와  방향그래프

간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다.

 

무방향 그래프의 간선은 간선을 통해서 양방향으로 갈 수 있는 그래프를 말한다.

예를 들면 우리가 차를 타고 서울에서 부산으로 갈 수 있고, 부산에서 서울로 올수 있다. 

정점 A와 B를 연결하는 간선은 (A, b)와 같이 정점의 쌍으로 표현한다. (A, B) = (B, A)

 

방향 그래프는 간선에 방향성이 존재하는 그래프로 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있다.

예를 들어 일방통행 길을 생각해보면 거꾸로 갈 수는 없다.

정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B> ≠ <B, A>

 

출처: https://sites.google.com/a/cs.christuniversity.in/discrete-mathematics-lectures/graphs/directed-and-undirected-graph

인접행렬 생성하기

방향이 있는 간선과 방향이 없는 간선들의 목록들을 받아 2차원 배열의 인접행렬을 반환하는 함수를 작성하기

undrected 일 경우는 양방향 즉, 간선이 존재하는 경우

directed 일 경우는 단방향 즉, 간선이 존재하지 않는 경우이다.

 

입출력 예시

let result = createMatrix([
	[0, 3, "directed"],
	[0, 2, "undirected"],
	[1, 3, "directed"],
	[2, 1, "directed"],
]);

console.log(result);
/**
 * [
 *  [0, 0, 1, 1],
 *  [0, 0, 0, 1],
 *  [1, 1, 0, 0],
 *  [0, 0, 0, 0]
 * ]
 */

코드 구현

function createMatrix(edges) {
	let matrix = [];    //만들어야하는 배열 생성
  let maxLength = 0;	// edges안의 숫자만으로 가장 큰 수를 찾아야한다.
  let lengths = [];     // maxlength를 위해 필요

  for(let i=0; i< edges.length; i++){    //반복문으로 각 배열에 접근하여,
    lengths.push(...edges[i].slice(0,2));  //slice로 1번째 인덱스까지 lengths에 넣어준다.
  }

  maxLength = Math.max(...lengths);   //넣어준 수에서 가장 큰수를 가져온다.
  // spread를 쓴 이유는 lengths는 배열이기 때문

    for(let i=0; i<= maxLength; i++){ 
    //반복문을 돌며 matrix안에 maxLength의 길이 만큼 배열을 만들고 그만큼 0으로 채운다.
      matrix.push(new Array(maxLength+1).fill(0))  
    }

  for(let edge of edges){ // edges에 각 배열에 접근하여, 
    matrix[edge[0]][edge[1]] = 1 //1을 넣어준다.

    if(edge[2]=== "undirected"){   //언디렉티드일 경우
      matrix[edge[1]][edge[0]] =1;  // 반대로도 넣어준다.
    }
  }

return matrix
}

 

 

인접행렬 길찾기

주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 하기

 

입출력 예시

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	3
);
console.log(result); // true

코드 구현

function getDirections(matrix, from, to) {
  //인접행렬 길찾기;

  //길을 하나 만들건데,, 방문했는지에 길입니다.
  let path = new Array(matrix.length).fill(false);
 // path = [false, false, false, false ]
 
  let location = [from]  // [0] 길이는 1;
  path[from] = true;
 // [true, false, false, false ]

  while(location.length > 0){   //길이가 0이 될때까지
      // 현재위치의 변수
      let now = location.shift()   // 2
      //base case 
      if(now === to) return true   //to = 2

      for(let i =0 ; i< matrix.length; i++){
        // 두가지 조건이 설입되어야한다.
        // 1번 path[i] ===false이고 2번 matrix[now][i] === 1
          if( matrix[now][i] ===1 && !path[i]){
            path[i] ===true;
            location.push(i)
          }
        }
      }
        return false 
  }