알고리즘 이론: 그래프(BFS, DFS)

윤뿔소·2022년 11월 28일

Algorithm / Design

목록 보기

12/15

그래프

여러개의 점(노드)들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다(트리완 달리 양방향 데이터 흐름을 가질 수 있음)
즉, 그래프가 일정하고 단방향 구조를 띈다면 트리, 스택/큐와 비슷하다.
컴공에선 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 띄는 구조를 뜻함.

적용 예시

아래 사진은 그래프를 이용한 SNS 친구 관계도를 그린 것임또 그 외 그래프 예시는 네비게이션 최적경로, 사이트 연결맵, 추천 엔진 등이 있다.

구조

직접적인 관계가 있는 경우 두 점 사이를 바로 이어주는 선이 있음.
간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐.
하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)이라고 함.

표현 방식

인접 행렬

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다!

서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태

A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표
가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장.
두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
- 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용

내비게이션 예제

거리를 입력한 내비게이션 그래프를 인접 행렬로 표현
A의 진출차수는 1개 : A —> C
[0][2] === 1
B의 진출차수는 2개 : B —> A, B —> C
[1][0] === 1
[1][2] === 1
C의 진출차수는 1개 : C —> A
[2][0] === 1

인접 리스트

각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현, 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 가짐

⭐️메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지

참고

B는 A와 C로 이어지는 간선이 두 개가 있는데, 왜 A가 C보다 먼저? 이 순서는 중요한가?

보통은 중요하지 않다. 그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.

우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적. 따라서 보통은 중요하지 않다. (언제나 예외는 존재.)

용어

참고용임

정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다. 간선 자체가 정보가 생겼다는 의미!
비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다. SNS의 팔로워, 팔로잉에 따라 불리언 상태가 정해지는 것으로 예시를 둘 수 있음!
무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 실제 지도처럼 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.

예시

포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 (길 찾기) 등
- 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있음

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다. 이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 합니다. 대전에 살고 있는 친구 C도 B의 결혼식에 참석한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동하려고 합니다.

위의 예제를 분석해보면

정점: 서울, 대전, 부산
간선: 서울—대전, 대전—부산, 부산—서울

이다. 즉, 이 간선은 내비게이션에서 이동할 수 있음을 나타냄,

비연결 그래프: 차로 가지 못하는 지역이 생긴다면(토론토)? 정점 사이에 어떠한 간선도 추가 X! 래프에선 이런 경우를 관계가 없다고 표현, 비연결 그래프
비가중치 그래프: 각 도시가 얼마나 떨어져 있는지는 알 수 없음, 추가적인 정보를 파악할 수 없는, 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 이런 그래프를 비가중치 그래프라 명명
- 내비게이션이라면 거리를 표시해야하니 가중치로 바꿔보자!
- 이런식으로! - 간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

실제 내비게이션은 간선에 거리를 표기한 가중치 그래프가 확장되어, 수백만 개의 정점(주소)과 간선이 추가되어야 비로소 내비게이션에서 쓰는 자료구조와 유사

⭐️그래프를 이용한 알고리즘

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적, 최단 경로나 최소 환승 등 하나의 목적에도 여러 가지 방법, 정점 탐색 방법에도 여러 가지
가장 대표적인 두 가지 방법, BFS와 DFS를 알아보자!

이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다!
⭐️사용할 때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야한다!

BFS(Breadth-First Search)

너비 우선 탐색, 찾고자하는 목표에서 정점부터 탐색, ⭐️주로 두 정점 사이의 최단 경로를 찾을 때 사용

DFS(Depth-First Search)

깊이 우선 탐색, 하나의 경로를 끝까지 탐색한 후, 목표가 아니라면 다음 경로로 넘어가 탐색, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색

참고

DFS와 BFS의 장단점은 또 무엇이 있을까요?
그래프가 굉장히 크다면 어떤 탐색 기법을 고려해야 할까요?
반대로, 그래프의 규모가 작고, depth가 얕다면 어떤 탐색 기법을 고려해야 할까요?
참고 사이트1, 참고 사이트2

예제

BFS

BFS는 ⭐️최단 경로를 찾는다면 유용하게 쓰일 알고리즘이다. 일단 간단하게 BFS의 구조를 나타낸 코드를 보자.

BFS는 일반적으로 큐(Queue)를 사용하여 구현된다. 시작 정점을 큐에 삽입하고, 큐에서 정점을 하나씩 꺼내면서 해당 정점과 인접한 정점들을 모두 방문. 이때, 이미 방문한 정점을 다시 방문하지 않도록 체크하는 것이 중요!

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const vertex = queue.shift();
    if (!visited.has(vertex)) {
      visited.add(vertex);
      console.log(vertex);

      const neighbors = graph[vertex];
      for (const neighbor of neighbors) {
        queue.push(neighbor);
      }
    }
  }
}

bfs(graph, 'A');

이 예시에서는 graph 객체를 인접 리스트로 표현했다. bfs 함수는 graph와 시작 정점 start를 입력으로 받아, BFS를 수행하여 그래프의 모든 정점을 탐색한다. 함수 내부에서는 visited 집합과 queue 배열을 초기화한 후, 시작 정점을 queue에 삽입한다. 이후에는 queue에서 정점을 하나씩 꺼내어 해당 정점이 방문된 적이 없다면 방문 처리하고, 해당 정점과 인접한 정점을 모두 queue에 삽입. 이렇게 BFS를 반복하면서 그래프의 모든 정점을 탐색할 수 있다.

정점과 간선의 정보, shortestPath

문제
다음은 정점과 간선의 정보가 주어졌을 때, 특정 노드에서 다른 모든 노드까지의 최단 경로의 길이를 구하는 문제입니다.

위 입력에서 첫 번째 줄은 정점과 간선의 개수를 나타냅니다. 이어지는 각 줄은 간선의 정보를 나타냅니다. 예를 들어, 1 2는 1번 노드와 2번 노드 사이에 간선이 있다는 것을 나타냅니다. 이 때, 1번 노드에서부터 다른 모든 노드까지의 최단 경로의 길이를 구하는 함수 shortestPath(n, edges, start)을 작성하세요.

function shortestPath(n, edges, start) {
  // 인접 리스트 초기화
  const adjList = new Array(n + 1).fill().map(() => []);

  // 간선 정보를 바탕으로 인접 리스트 구성
  for (const [u, v] of edges) {
    adjList[u].push(v);
    adjList[v].push(u);
  }

  // 방문 여부를 나타내는 배열과 거리 정보를 나타내는 배열 초기화
  const visited = new Array(n + 1).fill(false);
  const distances = new Array(n + 1).fill(Infinity);

  // 시작 노드의 거리를 0으로 초기화
  distances[start] = 0;

  // BFS 구현
  const queue = [start];
  while (queue.length > 0) {
    const node = queue.shift();
    visited[node] = true;

    for (const neighbor of adjList[node]) {
      if (!visited[neighbor]) {
        queue.push(neighbor);
        distances[neighbor] = distances[node] + 1;
      }
    }
  }

  // 결과 반환
  return distances.slice(1);
}

인접 리스트(adjacency list)를 초기화
간선 정보를 바탕으로 인접 리스트를 구성
방문 여부를 나타내는 배열과 거리 정보를 나타내는 배열을 초기화
시작 노드의 거리를 0으로 초기화
너비 우선 탐색(BFS) 알고리즘을 이용하여 모든 노드를 탐색하면서 거리 정보를 갱신
각 노드까지의 최단 거리를 반환

결과

const n = 5;
const edges = [
  [1, 2],
  [1, 3],
  [1, 4],
  [2, 4],
  [3, 4],
  [4, 5],
];
const start = 1;

const result = shortestPath(n, edges, start);
console.log(result); // [0, 1, 1, 1, 2]

DFS

작 노드에서부터 하나의 경로를 따라 마지막 노드까지 탐색한 후, 다른 경로로 이동하여 탐색을 진행, DFS는 그래프에서 경로를 탐색하거나, 모든 정점을 탐색하는데 사용된다!

일반적으로 스택(Stack)이나 재귀(Recursion)를 사용하여 구현된다. 시작 정점을 스택에 삽입하고, 스택에서 정점을 하나씩 꺼내면서 해당 정점의 인접한 정점 중에서 방문하지 않은 정점을 방문한다. DFS도 이미 방문한 정점을 다시 방문하지 않도록 체크하는 것이 중요!!

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const vertex = stack.pop();
    if (!visited.has(vertex)) {
      visited.add(vertex);
      console.log(vertex);

      const neighbors = graph[vertex];
      for (const neighbor of neighbors) {
        stack.push(neighbor);
      }
    }
  }
}

dfs(graph, 'A');

이 예시에서는 graph 객체를 인접 리스트로 표현했다. dfs 함수는 graph와 시작 정점 start를 입력으로 받아, DFS를 수행하여 그래프의 모든 정점을 탐색한다.
함수 내부에서는 visited 집합과 stack! 배열을 초기화한 후, 시작 정점을 stack!에 삽입한다.
이후에는 stack에서 정점을 하나씩 꺼내어 해당 정점이 방문된 적이 없다면 방문 처리하고, 해당 정점의 인접한 정점을 모두 stack에 삽입한다.

노드의 개수와 간선의 개수, countGroups

문제

다음은 노드의 개수와 간선의 정보가 주어졌을 때, 연결된 노드들의 그룹 수를 구하는 문제입니다.

위 입력에서 첫 번째 줄은 노드의 개수와 간선의 개수를 나타냅니다. 이어지는 각 줄은 간선의 정보를 나타냅니다. 예를 들어, 1 2는 1번 노드와 2번 노드 사이에 간선이 있다는 것을 나타냅니다. 이 때, 연결된 노드들의 그룹 수를 구하는 함수 countGroups(n, edges)을 작성하세요.

function countGroups(n, edges) {
  // 노드 간 연결 정보를 저장하는 그래프
  const graph = new Array(n + 1).fill(null).map(() => []);
  // 노드의 방문 여부를 저장하는 배열
  const visited = new Array(n + 1).fill(false);
  // 연결된 노드 그룹의 수
  let count = 0;

  // 그래프 생성: 간선 정보를 이용해 그래프를 만든다
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  // DFS 탐색 함수
  function dfs(u) {
    visited[u] = true;
    for (const v of graph[u]) {
      if (!visited[v]) {
        dfs(v);
      }
    }
  }

  // 모든 노드를 방문하며 연결된 그룹의 수 계산
  for (let i = 1; i <= n; i++) {
    if (!visited[i]) {
      count++;
      dfs(i);
    }
  }

  return count;
}

countGroups(5, [[1, 2], [2, 3], [3, 4], [4, 5]])가 호출되면 함수가 실행된다.
graph 배열과 visited 배열, count 변수가 초기화
간선 정보를 이용해 graph 배열을 채운다.
- graph[1] = [2], graph[2] = [1, 3], graph[3] = [2, 4], graph[4] = [3, 5], graph[5] = [4]
dfs 함수를 이용해 그룹을 찾는다.
- 방문한 노드는 visited 배열에 표시
모든 노드에 대해서 dfs를 수행한다.
- visited 배열의 값을 확인하여, 방문하지 않은 노드가 있다면 그룹의 개수를 1 증가시키고 dfs를 호출한다.
계산
- false, 끊어진게 있다면 count 증가

윤뿔소

코뿔소처럼 저돌적으로

이전 포스트

알고리즘 이론: 재귀

다음 포스트