그래프

그래프의 표현

엣지 리스트(edge list)

• 엣지 리스트는 엣지를 중심으로 그래프를 표현.
• 배열에 출발 노드, 도착 노드를 저장하여 엣지를 표현.
• 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분. arr[2][N]
• 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 표현.
• 엣지 리스트는 구현하기 쉽지만, 특정 노드와 관련되어 있는 엣지를 탐색하기 어려움.
• 벨만 포드 혹은 크루스칼 알고리즘에 사용하며, 노드 중심 알고리즘에는 잘 사용하지 않음.

인접 행렬(adjacency matrix)

• 2차원 배열을 자료구조로 이용하여 그래프를 표현.
• 엣지 리스트와 다르게 노드 중심으로 그래프를 표현.
• 가중치가 없을땐 1에서 2를 향하는 엣지를 인접 행렬은 1행2열에 1을 저장하는 방식으로 표현.
• 가중치가 있을땐 2에서 5로 향하는 엣지의 가중치를 2행5열에 기록.
• 인접 행렬을 이용한 그래프는 구현이 쉬움.
• 두 노드를 연결하는 엣지의 여부와 가중치값은 배열에 직접 접근하면 바로 확인할 수 있는 것이 장점.
• 노드와 관련되어 있는 엣지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 엣지가 적을 때는 공간 효율성이 떨어짐.
• 노드 개수가 많은 경우 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있음.( 노드가 3만만개 이상일 경우 java heap space error 발생)

인접 리스트(adjacency list)

• ArrayList로 그래프를 표현.
• ArrayList를 담는 배열 ArrayList[N] 선언.
• 노드1과 연결된 2,3 노드는 ArrayList[1]에 [2,3]을 연결하는 방식으로 표현.
• 출발지가 배열의 인덱스, 도착지가 배열의 값.
• 가중치가 있을 경우 Node(도착 노드, 가중치) 클래스를 선언하여 ArrayList에 추가.

유니온 파인드(union-find)

• 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과
  두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘.
• union 연산: 각 노드가 속한 집합을 1개로 합치는 연산.
• find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산.

구현 방법

• 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것.
• 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드.
• 각 노드가 모두 대표 노드 이므로 배열은 자신의 인덱스 값으로 초기화.

• 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산 수행.
• find 연산을 통해 자신이 속한 집합의 대표 노드를 연결.

위상 정렬(topology sort)

• 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘.
• 시간 복잡도: O(V + E) V : 노드, E : 엣지
• 위상 정렬에서는 항상 유일한 값으로 정렬되지 않음.

핵심 이론

1. 진입 차수(in-degree)는 자기 자신을 가리키는 엣지의 개수. 인접 리스트에 저장할때, 진입 차수 배열 ++.
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의
   진입 차수를 1씩 뺌.
3. 계속해서 다음 노드를 선택하여 반복. 0인 노드들이 여러개가 있기 때문에 위상 정렬이 늘 같은 정렬 결과를 보장하지 않음.

다익스트라(dijkstra)

• 그래프에서 최단 거리를 구하는 알고리즘.
• 엣지는 모두 양수.
• 시간 복잡도: O(ElongV)
• 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이 아니라 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현함.

핵심 이론

1. 인접 리스트로 그래프 구현하기. 배열의 자료형은 (노드, 가중치).
2. 최단 거리 배열 초기화하기. 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화.
3. 값이 가장 작은 노드 고르기. 최단 거리 배열에서 현재 값이 가장 작은 노드.
4. 최단 거리 배열 업데이트 하기. 선택된 노드에 연결된 엣지의 값을 바탕으로 다른 노드의 값을 업데이트. 한번 선택된 노드는
   다시 선택되지 않도록 확인. Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값)
5. 과정 3~4를 반복해 최단 거리 배열 완성하기.

벨만-포드(bellman-ford-moore)

• 그래프에서 최단 거리를 구하는 알고리즘.
• 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색.
• 음수 가중치 엣지가 있어도 수행할 수 있음.
• 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음.
• 시간 복잡도: O(VE)

핵심 이론

1. 엣지 리스트로 그래프를 구현하고 최단 경로 배열 초기화.
2. 모든 엣지를 확인해 정답 배열 업데이트.
3. 음수 사이클 유무 확인. 모든 엣지를 한 번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인. 만약 업데이트되는
   노드가 있다면 음수 사이클이 있다는 뜻이 되고, 2단계에서 도출한 정답 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 됨.
   음수 사이클이 존재하면 이 사이클을 무한하게 돌수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없음.

플로이드-위셜(floyd-warshall)

• 그래프에서 최단 거리를 구하는 알고리즘
• 음수 가중치 엣지가 있어도 가능.
• 동적 계획법의 원리를 이용해 접근.
• 시간 복잡도: O(V^3)
• 모든 노드 간의 최단 거리를 확인해주기 때문에 시간 복잡도가 빠르지 않은 편.
• 문제에서는 노드의 개수 범위가 적게 나타나는것이 특징.

핵심 이론

• A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면
  그것을 이루는 부분 경로 역시 최단 경로.
• 즉 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다는 의미.
• D[S][E] = Math.min(D[S][E],D[S][K]+D[K][E])

1. D[S][E] 를 S -> E 까지의 최단 거리를 저장하는 배열이라 정의. S==E 는 0, 나머지는 무한대로 초기화.
2. 최단 거리 배열에 그래프 저장. 출발 노드 S, 도착 노드 E, 엣지의 가중치를 W라고 했을 때 D[S][E]=W.(인접 행렬)
3. 기존의 점화식을 3중for문의 형태로 반복하면서 배열의 값을 업데이트.

    for 경유지 K에 관해(1~N) //N = 노드의 개수
        for 출발 노드 S에 관해(1~N)
            for 도착 노드 E에 관해(1~N)
            D[S][E] = Math.min(D[S][E],D[S][K]+D[K][E])

최소 신장 트리(minimum spanning tree)

• 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리.
• 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
• N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 개수는 항상 N-1 개다.

핵심 이론

1. 엣지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기.
2. 그래프 데이터를 가중치 기준으로 정렬하기.
3. 가중치가 낮은 엣지부터 연결 시도하기. 연결했을 때 사이클 형성 유무를 find 연산을 이용해 확인한 후 사이클이 형성되지 않을 때만 union 연산을 이용해 연결.
4. 과정 3 반복하기
5. 총 엣지비용 출력하기.