[자료구조 Basic] - 그래프 알아보기

그래프

출처: <파이썬 알고리즘 인터뷰> p384, 책만, 2020

그래프 개념 확인 

정의

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

 

용어

• 정점(vertex) : 그래프에서의 점은 정점(vertext)라 하며, 위치의 개념을 가지고 있다.
• 간선(edge) : 그래프의 점들을 이어주고 있는 선은 간선(edge)라 하며, 정점들간의 관계를 표현한다.
• 인접 (adjacency) : 두 정점이 간선으로 이어져 있다면, 두 정점은 인접하다.
• 차수 (degree) : 하나의 정점에 연결되어 있는 간선의 수
  진입차수(in-degree) : 하나의 정점에 들어오는 간선의 수 , 진출차수(out-degree) : 하나의 정점에서 나가는 간선의 수

실제사례 

지하철노선도
: 지하철 노선도는  대표적인 그래프라고 할 수 있다. 
지하철의 각 역들은 정점(vertex)가 되고 역과 역사이를 이어주는 노선은 간선(edge)이라고 할 수 있다.
또한 해당 역에서 갈 수 있는 역들은 인접(adjacency)한 역이며, 환승가능한 역을 포함하여 갈 수 있는 모든 역의 수를 차수(degree)라고 할 수 있다.

출처: 홍성필 교수님 저서

그래프의 종류 

• 무방향 그래프 (Undirected Graph)
  : 간선을 통해 양방향으로 이동 가능
   :정점 A와 정점 B를 연결하는 간선을 (A, B) (B, A)로 표현가능
  
  
• 방향 그래프  (Directed Graph)
    : 간선에 방향성이 존재하는 그래프
    : A -> B 로 갈 수 있는 간선은 (A, B)로 표시한다.
  
  
• 가중치 그래프
    : 간선을 아동하는데 비용이나 가중치가 할당된 그래프
    : 네트워크 라고도 한다.

그래프의 표현 방식

인접행렬

출처:  https://sarah950716.tistory.com/12

• 인접행렬은 그래프를 N x N의 2차원 배열의 모습으로 표현하는 방식이다. (N은 정점의 개수)
  : 두 개의 정점이 이어져 있다면 1, 이어져 있지 않다면 0 의 값을 가지도록 한다.
  : 그래프에 간선이 많이 존재하는 그래프의 경우 주로 사용
  
  
• 장점
  : 한 눈에 두 정점사이의 관계가 있는지 빠르게 파악하기 용이하다.
  : 행(또는 열)의 합을 통해 정점의 차수를 O(N)으로 알 수 있다.
• 단점
  : 특정 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야만 한다.

인접리스트

출처: https://sarah950716.tistory.com/12

• 인접리스트는 그래프를 표현하는 가장 일반적인 방법으로, 각 정점에 인접한 정점들을 리스트로 표시한 방식이다. 
  
  
• 장점 :
  : 특정 노드에 인접한 노드를 쉽게 찾을 수 있다.
  : 인접 행렬에 비해 인접하지 않은 요소는 저장하지 않으므로 메모리 효율성이 좋다.
• 단점
   : 노드가 연결되어있는 지 확인하기 위해서는 인접리스트를 모두 확인하여야만 한다.

그래프 코드로 구현해보기

1) 그림을 보고 인접행렬 만들기

다음과 같은 그래프를 인접행렬로 만드려면
1) 2차원 배열 만들기 ( nxn, n=4 )
const matrix = new Array(4).fill(0).map((row) => new Array(4).fill(0))

2) 시작정점, 도착정점, 방향성을 고려하여 2차원 배열의 값 넣기
matrix[0][2] = 1; matrix[0][3] = 1
matrix[2][1] = 1;  matrix[1][3] = 1

 

 

 

2) 인접행렬과 관련한 문제 풀어보기
Q. 인접행렬 길찾기
<인접행렬과 시작정점, 도착정점이 주어졌을 때, 시작정점에서 도착정점으로 가는 길의 존재여부를 반환해야하는 문제>

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);
console.log(result) // true
// 정점 0에서 1로, 1에서 2로 간선이 존재하기 때문에 true 반환


//풀이
// 현재 정점에서 갈 수 있는 정점들을 모두 queue에 넣고
// queue에서 방문지점을 하나씩 꺼내어 목적지와 검사하는 방법으로
// 도달여부를 생각해볼 수 있다.
// + 방문한 지점을 다시 돌아가면 안되기 때문에 방문여부(isVisited)를 체크하여 처리한다.
 
function getDirections(matrix, from, to) {
  // queue는 방문할 곳이 들어있는 배열을 의미한다. 처음 시작점을 넣어준다.
  const queue = [from];
  
  // 방문여부를 표시하기 위해 정점의 개수만큼 배열을 생성하여 준다.
  const isVisited = new Array(matrix.length).fill(false);

  // 방문하였을 경우 true, 첫 출발 정점을 true로 바꾸어준다
  isVisited[from] = true

  // queue(방문할 곳)의 사이즈가 0이 될 때까지 반복한다.
  while (queue.length > 0) {
    // queue에서 정점을 하나 빼서 now에 할당한다.
    const now = queue.shift();
    // now가 목적지인지 검사하고, 목적지라면 true를 반환합니다.
    if (now === to) return true;

    // 목적지가 아니라면 현재 위치에서 갈 수 있는 정점들을 확인한다.
    for (let next = 0; next < matrix[now].length; next++) {
      // 만약, 현재 정점과 연결되어있으면서 방문하지 않았다면,
      if (matrix[now][next] && !isVisited[next]){
        // queue에 next를 넣어 방문할 수 있도록 한다.
        queue.push(next);
        // 방문여부를 표시한다.
        isVisited[next] = true
      }
    }
  }
  // queue(방문할 곳)가 모두 순회하였다면 더 이상 갈 수 없으므로 false를 반환한다.
  return false;
}

 

 

 

출처:
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
https://bamdule.tistory.com/68