그래프

지니씨·2021년 10월 2일

BFS DFS 그래프 알고리즘 자료구조

자료구조&알고리즘

목록 보기

4/10

정의

정점(V)과 간선(E)으로 이루어진 자료구조

경로

정점 A에서 B로 가는 간선의 연속된 집합

사이클

시작점과 끝점이 동일한 경로

단순경로(단순사이클)

경로(사이클)에서 같은 정렬을 두 번 이상 방문하지 않는 경로(사이클)

가중치

간선을 사용할 때 드는 비용

차수(degree)

하나의 정점에 연결되 있는 간선의 수
간선에 방향이 있는 경우 in-degree 와 out-degree 를 나눠서 생각

방향 없는 그래프

양방향 그래프
그래프를 자료구조로 저장할 때는 방향 있는 그래프와 같이 간선 2개로 저장

저장

방향이 있는 경우 방향도 같이 저장해줘야 함, 간선 2개로 나누어 저장
그래프 저장의 목적
- 하나의 정점과 연결된 간선을 빠르게 찾기 위함 (시간)
- 전체 공간의 수를 적게 만들어야 함 (공간)

1. 인접행렬

정점x정점 이차 배열에 간선의 유(1)/무(0) 또는 간선의 가중치를 저장
한 정점과 연결된 모든 정점을 찾는데 걸리는 시간 O(V)
공간 V제곱

2. 인접리스트

정점 일차 배열에 각 정점과 연결된 정점들로 이루어진 배열을 값으로 가짐
한 정점과 연결된 모든 정점을 찾는데 걸리는 시간 O(차수)
공간 E

탐색

한 정점에서 시작해 연결된 모든 정점을 한 번씩 방문하는 과정
다익스트라 알고리즘: 최단 거리 찾는 알고리즘

1. 깊이 우선 탐색(DFS)

Stack 사용, 재귀함수

구현

정점과 각 정점에 연결된 정점을 저장하여 그래프 구정, 각 정점의 방문 여부를 기록할 check 배열
임의의 한 정점에서 탐색 시작
다음 과정 재귀 호출
- 방문한 정점의 check 값을 true로 변경
- 방문한 정점과 인접한 정점들 중 아직 방문하지 않은(check 값이 false) 정점을 기준으로 탐색 과정 재귀 호출

const search = (graph, node, check, order) => {
  check[node] = true;
  order.push(node);

  for (let i = 0; i < graph[node].length; i++) {
    const next = graph[node][i];
    if (check[next] === false) {
      search(graph, next, check, order);
    }
  }
};

const dfs = (graph, start) => {
  const check = Array(graph.length).fill(false);
  const order = [];

  search(graph, start, check, order);

  return order;
};

2. 너비 우선 탐색(BFS)

Queue 사용

구현

정점과 각 정점에 연결된 정점을 저장하여 그래프 구성, 각 정점의 방문 여부를 기록할 check 배열
임의의 한 정점에서 탐색을 시작, 해당 정점을 큐에 추가하고 check 배열 값을 true로 설정
큐가 빌 때까지 다음 과정 반복
- 큐의 가장 앞에 있는 정점을 꺼냄
- 꺼낸 정점과 인접한 정점들 중 아직 방문하지 않은(check 값이 false) 정점을 큐에 추가하고, 해당 정점의 check 값을 true로 변경

const bfs = (graph, start) => {
  const queue = [];
  const check = Array(graph.length).fill(false);
  const order = []; // 방문 순서
  check[start] = true;
  queue.push(start);

  while (queue.length > 0) {
      const x = queue.shift();
      order.push(x);
      for (let i = 0; i < graph[x].length; i++) {
          const y = graph[x][i];
          if (check[y] === false) {
              check[y] = true;
              queue.push(y);
          }
      }
  }
  
  return order;
};