그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조입니다. 각 정점은 객체로 나타낼 수 있으며, 객체들 간의 관계는 간선으로 나타낼 수 있습니다. 이러한 그래프는 현실에서 네트워크, 경로, 관계 등을 모델링 하는데 사용됩니다.

그래프를 표현하는 방법에는 연결 리스트를 활용한 ‘인접 리스트’와 배열을 활용한 ‘인접 행렬’이 있습니다. 아래에 그래프에 관한 개념들을 추가적으로 정리하려고 합니다.



  1. 무방향 방향
  2. 가중 그래프
  3. 사이클 비사이클
  4. 경로 순회
  5. 그래프 알고리즘




무방향 방향

무방향 그래프는 방향이 없는 그래프를 말합니다. 수식으로는 G=(V,E)로 표현하고 두 정점이 연결되었음 나타내는 (A,B)와 (B,A)는 동일한 간선으로 취급합니다.

방향 그래프는 G=<V,E>로 표현하고 두 정점이 연결되었음을 나타날 때, (A,B)와 (B,A)는 동일하지 않는 간선으로 취급합니다. 따라서 무방향 그래프의 최대 간선 수는 V=n 일 때 n(n-1)/2 이고, 방향 그래프의 최대 간선 수는 n(n-1) 입니다.


가중 그래프

가중 그래프는 간선에 가중치가 부여된 그래프를 말합니다. 이 그래프는 네트워크, 계획 등을 표현하는 데 사용됩니다. 가중 그래프는 객체들 간의 관계를 표현하고, 각 간선에는 가중치(비용 또는 거리)가 할당되어 있습니다.

가중 그래프는 여러 응용 분야에서 활용됩니다. 예를 들어, 우선순위 큐를 사용하여 최단 경로(최소 비용 경로)를 찾는데 사용되는 다익스트라 알고리즘 등의 경로 탐색 알고리즘에서 주로 사용됩니다. 또한, 라우팅 프로토콜에서도 네트워크에서 데이터를 전송하는 경로를 결정하는 데 가중 그래프가 사용됩니다.

뿐만 아니라 프로젝트 관리에서도 가중 그래프가 활용될 수 있습니다. 프로젝트의 작업들을 정점으로, 작업 간의 의존 관계를 가중치로 나타내어 시간 또는 비용 등을 최소화하여 프로젝트를 효율적으로 관리하는 데 활용됩니다.


순환 비순환

한 정점에서 시작해서 다시 같은 정점으로 돌아오는 경로가 있는 그래프를 순환 그래프라고 합니다. 사이클이 있는 그래프라고 말하기도 합니다. 사이클이 없는 그래프를 비순환 그래프라고 말하며, 트리는 그래프의 한 형태로 비순환 그래프입니다.

탐색 알고리즘인 DFS와 BFS을 통해, 사이클이 있는지 혹은 없는지 확인할 수 있습니다.


  • 신장 트리

    신장 트리는 모든 정점을 한 번만 연결된 그래프를 말합니다. 그리고 최소 신장 트리(MST)는 가중치를 가지는 가중 그래프에서 모든 정점을 한 번만 연결하는 신장 트리 중 간선의 가중치 합이 가장 작은 신장 트리를 말합니다.

    가중 그래프에서 최소 신장 트리를 만들 때, 최소 신장 알고리즘인 프림, 크루스칼, 솔린 알고리즘 등이 사용됩니다.

    추가적으로, 신장 트리는 비순환 그래프는 맞지만 비순환 그래프는 신장 트리가 아닙니다. 예시로는 동 떨어진 섬인 정점(연결되지 않은 서브 그래프)을 가지는 비순환 그래프를 생각해보면 됩니다.


경로 순회

그래프의 한 정점에서 이어진 변을 따라 또 다른 정점으로 이동할 때, 지나간 변을 반복해서 통과하지 않을 경우에 지나온 정점들을 순서대로 나열한 것을 경로(단순경로, 정점을 중복 방문x -> 기본경로)라고 하고, 이때 한 정점에서 출발하여 다시 출발한 정점으로 돌아오는 경로를 순회라고 합니다.

  • 오일러 경로와 순회

    각 연결선을 단 한 번씩만 통과하는 경로 or 순회를 말합니다. 홀수 차수의 개수가 0 또는 2인 경우 오일러 경로를 가지고, 특히 홀수 차수가 0 개일 때는 오일러 순회도 가집니다.

  • 해밀턴 경로와 순회

    그래프에서 모든 정점을 오직 한 번씩만 지나는 경로 or 순회를 말합니다.


그래프 알고리즘

대표적인 그래프 알고리즘으로 탐색 알고리즘인 DFS, BFS가 있습니다. 그리고 우선순위 큐를 이용한 최단 경로 알고리즘이 있고, 최소 신장 알고리즘(프림, 크루스칼, 솔린) 등이 있습니다. 이 뿐만 아니라 다양한 알고리즘이 사용됩니다.

  • 프림 알고리즘

    프림 알고리즘은 임의의 시작 정점으로부터 출발하여 해당 정점에 연결된 간선 중에서 가중치가 가장 작은 간선부터 선택하여 다음 정점으로 확장해가는 방식으로 최소 신장 트리를 구하는 알고리즘입니다. 프림 알고리즘을 구현하는 방법은 다음과 같습니다.

    1. 시작 정점에 연결된 모든 정점과 간선을 최소 힙(우선순위 큐)에 삽입합니다.

    2. 최소 힙에서 가중치가 가장 적은 간선의 정점을 추출합니다. 만약 해당 정점이 이미 방문한 정점이라면 건너뛰고, 그렇지 않다면 해당 정점에 연결된 모든 간선과 정점을 최소 힙에 삽입합니다.

    3. 모든 정점을 방문할 때까지 2번의 과정을 반복하여 최소 신장 트리를 구성합니다. 이때, 시간 복잡도는 O(ElogV) 입니다.


  • 크루스칼 알고리즘

    크루스칼 알고리즘은 모든 간선을 가중치 순으로 정렬하고 가장 작은 가중치의 간선부터 차례대로 선택하여 모든 정점을 방문할 때까지 반복하여 최소 신장 트리를 구성하는 알고리즘입니다. 구현 방식은 다음과 같습니다.

    1. 간선과 정점의 정보를 리스트에 담고, 해당 리스트를 오름차순으로 정렬합니다.

    2. 리스트를 첫 인덱스부터 순회하면서 Union-Find 알고리즘을 사용하여 각 정점의 그룹을 확인하고, 싸이클이 형성되지 않는 경우에만 연결을 수행합니다.

    3. 모든 정점을 방문했다면 반복문을 종료해도 됩니다. 시간 복잡도는 O(ElogE) 입니다.


  • 다익스트라 알고리즘

    다익스트라 알고리즘은 주어진 그래프에서 한 정점을 시작으로 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 구현 방식은 다음과 같습니다.

    1. 출발 정점을 기준으로 초기화를 진행합니다. 출발 정점의 최단 거리를 0으로 설정하고, 다른 모든 정점의 최단 거리를 무한대로 설정합니다.

    2. 우선순위 큐를 사용하여 아직 방문하지 않은 정점들을 저장합니다. 초기에는 출발 정점만 큐에 넣습니다.

    3. 우선순위 큐에서 가장 최단 거리의 정점을 선택하여 방문합니다. (중복 검사를 피하기 위해 선택된 정점의 거리가 기록된 거리보다 크다면 건너뜁니다. 예시) 1->5 비용이 5이고 1->3->5 비용이 6이라면 건너뜁니다. 방문한 정점 처리로도 중복 검사를 피할 수 있습니다. 단 방문한 정점 처리로 중복 검사를 할 경우, 음의 가중치가 있을 경우에는 처리할 수 없습니다. 예시) 1->5 비용이 5이고 1->3->5 비용이 4일 수 있음 3->5로 가는 가중치가 음수일 경우)

    4. 선택된 정점에 연결된 모든 인접 정점들의 최단 거리를 갱신합니다. 현재까지의 최단 거리와 선택된 정점을 거쳐 가는 경로의 거리를 비교하여 더 짧은 거리로 업데이트합니다.

    5. 모든 정점을 방문하고 갱신이 완료될 때까지 3번과 4번의 과정을 반복합니다.


  • 벨만포드 알고리즘

    다익스트라 알고리즘과 똑같이 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘입니다. 차이점은 벨만포드 알고리즘은 간선의 가중치가 음수이면서 음수 가중치 사이클을 형성할 가능성이 있는 상황에도 사용 가능하다는 점입니다. 그에 따라 동작 방식도 차이가 있습니다. 벨만포드의 경우 매 정점을 방문할 때마다 모든 간선을 순회합니다. 따라서, 시간 복잡도는 O(VE)가 됩니다.

    1. 출발 정점을 0으로 초기화하고, 다른 정점의 거리를 무한대로 설정합니다.

    2. 출발 정점을 기준으로 총 vertices번 순회합니다. 그리고, 매 정점마다 모든 간선을 비교하면서 최단 거리를 갱신합니다.

    3. 2번을 반복하다 마지막 vertices 번째에 한 번더 갱신되는지 확인합니다. 만약 갱신된다면 음수 가중치 사이클이 존재하는 것으로 최단 거리를 정의할 수 없습니다.(음수 가중치 순환은 그래프에서 한 정점에서 시작해서 같은 정점으로 돌아오는 간선들의 합이 음수인 순환을 의미합니다.)


  • 위상 정렬

    위상 정렬은 방향 그래프에서 정점의 선후 관계를 표현한 정렬 방법입니다.

    • kahn알고리즘: 진입 차수(In-Degree)를 기반으로 처리합니다.

      1. 모든 정점의 진입 차수를 계산합니다.
      2. 진입 차수가 0인 정점을 큐에 삽입합니다.
      3. 큐에서 정점을 하나씩 꺼내며 연결된 간선을 제거하고, 연결된 정점의 진입 차수를 1 감소시킵니다.
      4. 진입 차수가 0이 된 정점을 큐에 추가하는 과정을 반복합니다.

    • DFS: 후위 순회(Post-Order Traversal)의 역순을 활용하는 방식입니다

      1. 임의의 한 정점에서 DFS를 수행합니다.
      2. 인접 정점을 모두 방문하고 나서, 현재 정점을 스택에 추가합니다.
      3. 방문하지 않은 모든 정점에 대해서 1번과 2번을 반복합니다.
      4. 스택에 있는 정점을 하나씩 꺼내면 위상 정렬 순서가 됩니다.


  • 강한 연결 요소(SCC)

    강한 연결 요소(SCC)는 그래프 내에서 서로 도달 가능한 정점들의 집합입니다. 타잔 알고리즘을 이용하여 구현현합니다.

    1. DFS를 통해 각 정점을 방문하며, 방문 순서와 최소 도달 가능한 부모 정점을 기록합니다.
    2. 현재 정점이 최소 도달 가능한 부모일 경우, 해당 정점부터 스택에 쌓인 정점들을 SCC로 분리합니다.


  • 최소 공통 조상(LCA)

    최소 공통 조상은 두 정점 간 공통 조상 중 가장 가까운 조상을 찾는 알고리즘입니다. 트리를 기반으로 하며, DP를 활용합니다.

    1. DFS를 통해 각 정점의 깊이와 부모를 기록합니다.
    2. 희소 배열(Sparse Table)을 구축하여 각 정점의 2^k번째 조상을 저장합니다.
    3. 두 정점의 깊이를 맞춘 후, 공통 조상을 탐색합니다.


  • 단절점과 단절선

    단절점은 제거 시 그래프가 두 개 이상의 부분 그래프로 나뉘는 정점입니다. 단절선은 제거 시 그래프가 나뉘는 간선입니다.

    1. DFS를 통해 각 정점의 방문 순서와 최소 도달 가능 순서를 기록합니다.
    2. 현재 정점의 순서가 연결된 그래프의 최소 순서보다 작거나 같으면 단절점, 작다면 단절선으로 판단합니다.


  • 플로이드-워셜 알고리즘

    플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 거리를 계산하는 알고리즘입니다.

    1. 인접 행렬을 초기화합니다. 없는 간선은 무한대로 설정합니다.
    2. 중간 정점을 하나씩 선택하며, 두 정점 간 최단 거리를 갱신합니다.


  • 이분 매칭

    이분 매칭은 이분 그래프에서 최대 매칭을 찾는 알고리즘입니다. 작업 스케줄링과 네트워크 연결 문제 등에 활용됩니다.

    1. 정점 집합 중 하나에서 시작하여 DFS로 매칭을 시도합니다.
    2. 현재 정점에서 연결된 간선을 따라가며 매칭되지 않은 정점을 찾습니다.
    3. 매칭된 정점의 연결을 재구성하여 더 큰 매칭을 만듭니다.
    4. 모든 정점에 대해 과정을 반복합니다.
    • 이분 그래프: 이분 그래프는 정점 집합이 두 그룹으로 나눠질 수 있는 그래프입니다. 같은 그룹의 정점 간에 간선이 존재하지 않습니다.


  • 네트워크 플로우

    네트워크 플로우는 그래프에서 최대 유량을 구하는 알고리즘입니다.

    • Ford-Fulkerson 알고리즘

      1. 초기 유량을 0으로 설정합니다.
      2. 증가 경로를 찾습니다. 증가 경로는 현재 흐를 수 있는 추가 유량(여유 용량)이 존재하는 경로입니다.
      3. 찾은 증가 경로를 따라 가능한 유량을 계산하여 경로의 모든 간선에 유량을 갱신합니다. 이때, 유량의 대칭성도 고려합니다.
      4. 더 이상 증가 경로를 찾을 수 없으면 종료합니다.
      • 여유 용량: 간선의 용량 - 현재 유량.
      • 유량의 대칭성: flow(u→v) = -flow(v→u).