그래프

MountionRiver·2025년 7월 23일

JavaScript 코딩테스트

그래프 개념

노드와 간선ㅇ리 용한 비선형 데이터 구조. 보통 데이터 간의 관계를 표현하는데 사용

그래프 용어 정리

노드: 데이터를 표현하는 점
간선: 노드 간의 관계나 연결을 표현하는 선
가중치: 간선 위에 표현된 값으로, 연결의 '비용'이나 '거리' 등을 나타냄

그래프의 특징과 종류

흐름을 표현하는 방향성

간선은 방향을 가질 수도 있고, 없을 수도 있다. 방향이 있을 경우 방향 그래프, 방향이 없을경우 무방향 그래프이다. 방향이 있을 경우 서로 반대를 가르키는 간선이 있을수도 있다.

흐름의 정도를 표현하는 가중치

데이터는 흐름 방향 뿐만 아니라 양도 중요 할 수 있다. 그런 정도를 간선에 표현할 때 가중치라고 함. 가중치가 있는 그래프를 가중치 그래프라고 함.

시작과 끝의 연결 여부를 보는 순환

순환은 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는것. 순환이 존재하면 순환그래프라고 하고, 순환이 존재하지 않을 경우 비 순환 그래프

그래프 구현

구현할때 데이터를 담고있는 노드 , 노드를 잇는 간선 , 간선의 방향, 간선의 가중치 네가지를 고려하며 구현 방식에는 인접 행렬과 인접 리스트 두가지 방식이 있습니다.

인전 행렬 그래프 표현

인접행렬은 2차원 배열을 활용하여 구현하는 경우가 많음.
노드 : 배열의 인덱스
간선 : 노드 간 연결 여부 값
가중치 : 배열의 값

// 예시 코드
const graph = [
  // 0  1  2
  [ 0, 4, 7 ], // 0번 노드
  [ 4, 0, 5 ], // 1번 노드
  [ 7, 5, 0 ]  // 2번 노드
 // graph[0][1] === 4 → 0과 1 사이 간선 가중치 4
 // graph[1][2] === 5 → 1과 2 사이 간선 가중치 5
];

인접 리스트 그래프 표현

인접 리스트를 그래프로 표현하려면 노드를 정의하고 값, 가중치,다음 노드를 묶어서 관리

동작 방식
1. 노드 갯수만큼 배열을 준비
2. 배열의 인덱스는 각 시작 노드를 의미하며, 배열의 값에는 다음 노드를 연결

// 노드를 정의하고 값(인덱스) , 가중치, 다음 노드를 묶어서 관리(
// 간선 노드를 나타내는 클래스
class EdgeNode {
  constructor(vertex, weight, next = null) {
    this.vertex = vertex; // 도착 노드 번호
    this.weight = weight; // 간선의 가중치 (거리, 비용 등)
    this.next = next;     // 다음 간선을 가리키는 포인터 (연결 리스트 구조)
  }
}

// 인접 리스트 방식 그래프 클래스
class Graph {
  constructor(n) {
    // 노드 수만큼 인접 리스트 배열 생성
    // 인덱스 1부터 사용하기 위해 크기를 n + 1로 설정
    this.adjList = Array.from({ length: n + 1 }, () => null);
  }

  // 간선 추가 함수: from → to 방향의 간선 추가
  addEdge(from, to, weight) {
    // 새 간선 노드를 만든 후, 기존 간선들 앞에 붙임 (head insert 방식)
    const newNode = new EdgeNode(to, weight, this.adjList[from]);
    // 해당 from 노드의 연결 리스트 갱신
    this.adjList[from] = newNode;
  }

  // 그래프 전체 출력 함수 (디버깅용)
  printGraph() {
    // 1번 노드부터 마지막 노드까지 순회
    for (let i = 1; i < this.adjList.length; i++) {
      let line = `${i} -> `; // 출력 줄 시작
      let current = this.adjList[i]; // 현재 노드에서 출발하는 간선들

      // 연결 리스트 순회
      while (current) {
        // 도착 노드와 가중치를 출력 문자열에 추가
        line += `[${current.vertex}, ${current.weight}] -> `;
        current = current.next; // 다음 간선으로 이동
      }

      line += 'NULL'; // 끝 표시
      console.log(line); // 한 줄 출력
    }
  }
}

// 1. 노드의 갯수만큼 배열을 준비 
const graph = new Graph(4);

// 이미지 기준 간선 추가 (from, to, weight)
graph.addEdge(1, 2, 3);
graph.addEdge(2, 1, 6);
graph.addEdge(2, 3, 5);
graph.addEdge(3, 2, 1);
graph.addEdge(3, 4, 13);
graph.addEdge(4, 1, 42);
graph.addEdge(4, 4, 9);

// 그래프 출력
graph.printGraph();

인접 행렬과 인접 리스트의 장단점

인접 행렬의 장단점

장점 :
- 시간 복잡도가 O(1)로 매우좋다.
- 구현 난이도가 인접리스트에 비해 낮다.
단점:
- 노드수에 비해 간선 수가 적은 경우(희소 그래프)의 경우 최악의 경우 N*N 크기의 인접 행렬을 필요로 하나 대부분 사용하지 않으므로 비효율 적이다.
- 노드들의 값 차이가 매우 큰 그래프를 표혈 할 경우 가장 큰 노드값을 기준으로 인접 행렬의 크기를 잡아야 하기 때문에 메모리 낭비가 발생한다.

인접 리스트의 장단점

장점 :
- 연결된 노드만 저장하므로 메모리의 효율이 높다.
- 동적으로 간선 추가/ 삭제가 유연하다.
단점:
- 시간 복잡도가 O(N)으로 상대적으로 더 걸릴 수 있다.
- 구현 난이도가 인접 행렬에 비해 상대적으로 높다.
```
좋아! 너가 쓴 내용은 아주 잘 정리되어 있어.
```
비어 있는 인접 리스트의 장단점 부분을 자연스럽고 정확하게 채워줄게:

그래프 탐색

그래프의 경로를 탐색 할 경우 크게 두가지로 나누어진다.

깊이 우선탐색: 탐색할 노드가 없을때 까지 내려간 뒤 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않으 노드 방문
너비 우선탐색: 현재위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어간다.

깊이 우선 탐색

한 노드를 방문한 후, 해당 노드의 자식 노드를 끝까지 탐색한 뒤 다시 되돌아오는 방식이다.

가장 중요한 핵심은 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있느지 확인한다 이다.

스택을 활용한 깊이 우선 탐색

진행 순서
1. 시작노드를 정하고, 스택에 시작노드를 푸시한다
2. 스택에서 노드를 pop 한다.
3. pop한 노드의 방문여부를 확인하고, 방문하지 않았다면 방문처리 한다.
4. 방문한 노드와 인접 노드를 확인하고, 방문하지 않은 노드를 스택에 푸시한다.
5. 스택이 비었는지 확인하고. 스택이 비어있다면 전부 방문한 것이므로 종료

재귀 함수를 활용한 깊이 우선 탐색

가장 많이 사용하는 DFS 방식
방문한 노드는 기록하고, 재귀로 다음 노드 방문

너비 우선 탐색

시작노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘 거리는 노드간의 차수이며 가중치와는 다르다.

큐를 활용한 너비 우선 탐색

시작노드를 정하고 큐에 시작노드를 푸시한다.
큐에서 노드를 팝한다.
팝한 노드와 인접 노드를 확인하고 그중에 아직 방문하지 안흔 노드를 큐에 푸시하며 방문처리한다.
큐가 비었는지 확인하고. 큐가 비어있다면 전부 방문한 것이므로 종료

깊이 우선 탐색과 너비 우선 탐색 비교

깊이 우선탐색은 깊게 탐색후 되돌아 오는 것, 너비 우선 탐색은 시작노드에서 인접한 노드부터 방문하는 특성 두 알고리즘은 용도가 다르다.

깊이 탐색한 다음 되돌아오는 깊이 우선 탐색

깊이 우선 탐색은 백트랙킹 알고리즘을 구현할때나 사이클 감지시 활용

최단 경로를 보장하는 너비 우선 탐색

너비 우선 탬색은 최단 경로나 네트워크 분석 문제를 풀때 활용

그래프 최단 경로 구하기

최단 경로를 구하는 대표적인 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘을 차례로 알아 보자.

다익스트라 알고리즘

시작 노드를 설정하고, 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련합니다.
- 1-1. 최소 비용을 저장할 공간은 모두 매우 큰 값(INF) 으로 초기화한다.
  여기서 INF는 무한대(infinite)를 의미한다.
  직전 노드를 저장할 공간도 INF로 초기화한다.
- 1-2. 시작 노드의 최소 비용은 0, 직전 노드는 자기 자신으로 설정한다.
해당 노드를 통해 방문할 수 있는 노드 중, 아직 방문하지 않은 노드 중에서 현재까지 구한 최소 비용이 가장 적은 노드를 선택한다.
- 2-1. 해당 노드를 거쳐 각 노드까지 가는 새로운 최소 비용과 기존 최소 비용을 비교하여, 더 작은 값을 각 노드의 최소 비용으로 갱신한다.
- 2-2. 이때 직전 노드도 함께 갱신한다.
이 과정을 노드의 개수 - 1번 반복한다.

벨만 포드 알고리즘

시작 노드를 설정한 다음,
시작 노드의 최소 비용은 0, 나머지 노드의 비용은 모두 INF(무한대) 로 초기화한다.
이후 최소 비용을 갱신할 때 직전 노드도 함께 갱신한다.
노드 개수 - 1 만큼 아래 연산을 반복한다.
- 2-1. 모든 간선을 하나씩 확인하며,
  현재까지 구한 최소 비용보다 더 적은 비용으로 도달할 수 있는 노드가 있다면
  그 노드의 최소 비용을 갱신한다.
  이때 갱신이 일어났다면 직전 노드 정보도 함께 갱신한다.
위의 2-1 과정을 마지막으로 한 번 더 수행하여,
만약 여전히 최소 비용이 갱신된다면 음의 사이클(순환)이 존재하는 것이다.

MountionRiver

이전 포스트

ts 책 스터디(타입 활용하기)

다음 포스트

그래프