[알고리즘 공부] 그래프

---

참고

그래프란

---

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

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

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

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

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

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

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

---

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

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

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

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

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

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

인접행렬 생성하기

---

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

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

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

• 코드

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;
}

• 입출력 예시

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]
 * ]
 */