『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

그래프 기본

그래프란?

• 노드와 에지로 구성된 집합이다.
  • 노드: 데이터를 표현하는 단위
  • 에지: 노드를 연결하는 선
• Tree도 그래프의 일종이다.
• 그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩 테스트에 자주 등장한다.

그래프 관련 알고리즘

• 유니온 파인드 (Union-Find)
  • 그래프 외에서도 사용된다.
  • 그래프의 사이클이 생성되는지 판별하는 알고리즘이다.
• 위상 정렬 (Topological sort)
  • 사이클이 없는 방향이 있는 그래프일 때, 그래프의 각 노드들을 선형으로 정리하는 알고리즘이다.
  • 정렬 결과가 꼭 1개인 것은 아니다.
• 다익스트라 (Dijkstra)
  • 최단 거리 알고리즘
  • 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘이다.
  • 단, 음수 간선이 있으면 안 된다.
• 벨만-포드 (Bellman-Ford)
  • 최단 거리 알고리즘
  • 시작점에서 다른 모든 노드로 가는 최단거리를 구하는 알고리즘이다.
  • 음수 간선이 있어도 된다.
  • 음수 사이클이 있는지를 판별하는 문제에서 자주 쓰인다.
• 플로이드-워셜 (Floyd-Warshall)
  • 최단 거리 알고리즘
  • 주어진 노드들 중 임의의 노드와 다른 노드 사이에서의 최단거리를 구하는 알고리즘이다.
  • 시작점이 없다.
  • 다익스트라와 벨만-포드 알고리즘에 비해 시간 복잡도가 좋지 않다.
• 최소 신장 트리 (MST)
  • 최소의 가중치 합으로 모든 노드를 연결할 수 있도록 해주는 알고리즘이다.
  • 최소 신장 트리에서는 사이클이 나올 수가 없으므로, 유니온 파인드 알고리즘이 필요하다.

그래프의 표현

그래프를 구현하는 방법은 총 3가지가 있다.

에지 리스트

• 에지 리스트(edge list)는 에지를 중심으로 그래프를 표현한다.
• 에지 리스트는 다음과 같이 사용한다.
  • 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현
  • 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현
• 노드는 여러 자료형을 사용할 수 있다.
• 에지 리스트는 구현하기 쉽다.
• 벨만 포드나 크루스칼(MST) 알고리즘에 사용한다.
  • 이 둘은 에지 기준의 알고리즘이다.

가중치 없는 그래프 표현하기

• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.
• 다음과 같이 그래프의 노드들이 방향을 가지고 있다고 하자.

  • 1 → 2 → 5

  • 1 → 3 → 4 → 5

  • 2→ 4

    Integer[][] A = new Integer[2][N];
    
    // A[0][0] = 1, A[1][0] = 2
    // A[0][1] = 1, A[1][1] = 3
    // A[0][2] = 3, A[1][2] = 4
    // A[0][3] = 2, A[1][3] = 4
    // A[0][4] = 2, A[1][4] = 5
    // A[0][5] = 4, A[1][5] = 5

  • 만약 방향이 없는 그래프라면 $[1, 2]$와 $[2, 1]$은 같은 표현이다.

가중치 있는 그래프 표현하기

• 가중치가 있는 그래프는 행을 3개로 늘려 3번째 행에 가중치를 저장하면 된다.
• 다음과 같이 그래프의 노드들이 방향을 가지고 있다고 하자.

  • 1 → 2 (가중치 8)

  • 2 → 5 (가중치 15)

  • 1 → 3 (가중치 3)

  • 3 → 4 (가중치 13)

  • 4 → 5 (가중치 2)

  • 2 → 4 (가중치 4)

    Integer[][] A = new Integer[3][N];
    
    // A[0][0] = 1, A[1][0] = 2, A[2][0] = 8
    // A[0][1] = 1, A[1][1] = 3, A[2][1] = 3
    // A[0][2] = 3, A[1][2] = 4, A[2][2] = 13
    // A[0][3] = 2, A[1][3] = 4, A[2][3] = 4
    // A[0][4] = 2, A[1][4] = 5, A[2][4] = 15
    // A[0][5] = 4, A[1][5] = 5, A[2][5] = 2

  • 만약 방향이 없는 그래프라면 $[1, 2]$와 $[2, 1]$은 같은 표현이다.

주의

• 에지 리스트로 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다.
  • 만약 노드 2와 관련 있는 노드를 찾고 싶어서 배열을 탐색한다면, 배열을 정렬하거나 전체를 뒤지며 노드가 2인 것을 찾아야 한다.
• 따라서 노드 중심 알고리즘에는 잘 사용하지 않는다.

인접 행렬

• 인접 행렬(adjacency matrix)은 2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
• 에지 리스트와 다르게 노드 중심으로 그래프를 표현한다.

  Integer[][] A = new Integer[N][N];

가중치가 없는 그래프 표현하기

• 1에서 2를 향하는 에지를 1행 2열에 1을 저장하는 방식으로 표현한다.
• 여기서 1을 저장하는 것은 유무(있고 없음)의 구분값이다.

가중치가 있는 그래프 표현하기

• 1에서 2를 향하는 에지에 8이라는 가중치가 있을 때, 1행 2열에 8을 저장하는 방식으로 표현한다.
• 즉, 가중치를 저장한다.
• 인접 행렬을 이용한 그래프 구현은 쉽고, 두 노드를 연결하는 에지의 여부와 가중치값을 배열에 직접 접근하면 바로 확인할 수 있다는 장점이 있다.

주의

• 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다.
• 노드 개수가 많은 경우 2차원 배열 선언 자체를 할 수 없는 결함이 있다.
  • 예를 들어 노드가 3만 개가 넘으면 Java heap space 에러가 발생한다.
• 따라서 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단해야 한다.

인접 리스트

• 인접 리스트(adjacency list)는 ArrayList로 그래프를 표현한다.
• 노드 개수만큼 ArrayList를 선언하며, 자료형은 경우에 맞게 사용한다.
• 그래프를 구현하는 다른 방법에 비해 구현이 복잡한 편이지만, 다음과 같은 이유로 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호한다.
  • 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나다.
  • 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러가 발생하지 않는다.

가중치 없는 그래프 표현하기

• N번 노드와 연결되어 있는 노드를 배열의 위치 N에 연결된 노드 개수만큼 배열을 연결하는 방식으로 표현한다.
• 다음과 같이 ArrayList의 배열로 선언한다.

  • 배열의 하나 하나가 모두 노드이다.

  • 노드 1에서 2와 3으로 가는 그래프가 있다면 다음과 같다.

    ArrayList<Integer>[] A = new ArrayList[5];
    A[1].add(2);
    A[1].add(3);

가중치 있는 그래프 표현하기

• 가중치가 있는 경우, 자료형을 클래스로 사용한다.
• 다음은 (도착 노드, 가중치)를 갖는 Node 클래스를 선언하여 ArrayList에 사용한다.

  class Node {
  	int E;
  	int V;
  	
  	Node(int E, V) {
  		this.E = E;
  		this.V = V;
  	}
  }
  
  ArrayList<Node> A = new ArrayList[N];
  A[3].add(new Node(4, 3));

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런