그래프 알고리즘

• 그래프는 정점(노드)와 간선(엣지)로 이루어진 자료구조로 정점 간의 관계를 나타내는 자료구조

• 트리는 그래프의 일종으로, 사이클이 존재하지 않는 방향 그래프다.

그래프 용어

• 정점(Vertex) : 노드(node), 데이터가 저장되는 곳
• 간선(Edge) : 정점간의 관계
• 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점 수
• 진출 차수(Out Degree) : 방향 그래프에서 한 정점에 외부로 향하는 간선의 수
• 진입 차수(In Degree) : 방향 그래프에서 외부 정점에서 들어오는 간선의 수
• 단순 경로(Simple Path) : 경로 중 반복되는 정점이 없는 경우
• 경로 길이(Path Length) : 경로를 구성하는데 사용된 간선의 수
• 루프(Loop) : 그래프의 한 노드에서 자기 자식으로 이어지는 간선이 있을 때 그 간선을 루프라 함.

그래프 종류

• 무방향 그래프(Non-Directed Graph) : 두 정점을 연결하는 간선에 방향이 없는 그래프

• 방향 그래프(Directed Graph) : 두 정점을 연결하는 간선에 방향이 존재하는 그래프. 간선의 방향으로만 이동 가능

• 가중치 그래프 (Weighted Graph) : 두 정점을 이동할 때 비용이 드는 그래프

최소 스패닝 트리 Minimum Spanning Tree

• Spanning Tree : 그래프 G의 모든 vertex가 사이클 없이 연결된 형로, 최소 연결 부분 그래프

• 그래프 G의 spanning tree 중 edge weight 합이 최소인 spanning tree
  • 통신망, 도로망 등에서 구축 비용과 전송 시간 등을 최소로 구축하려는 경우 사용
• 구현 방법
  • Kruskal MST 알고리즘
    • Greedy 방법 이용해서 구현
  • Prim MST 알고리즘
    • 신장트리 집합을 단계적으로 확장해가는 방법

그래프 구현

1. 인접 행렬

• 정방 행렬을 사용

• 두 노드가 간선을 가지면 1 또는 0으로 표시

• 장점 : 구현이 간단함, 조회 시간복잡도 O(1)

• 단점 : 무조건 2차원 배열이 필요하므로 필요 이상의 공간을 낭비한다.

  -> Dense Graph 표현할 때 적절한 방법

2. 인접 리스트

• 연결 리스트 사용

• 장점 : 필요한 만큼의 공간만 사용할 수 있다. 정점들의 연결정보 탐색 시 시간복잡도 O(N)
• 단점 : 두 정점이 간선을 가지는지 확인하려면 인접 행렬보다 시간이 더 소요됨.

그래프 탐색

1. 너비 우선 탐색 (BFS)

• 현재 정점과 연결된 정점들에 대해 우선적으로 넓게 탐색하는 방법
• 큐를 이용하여 구현
• 시간복잡도 : O(V+E)
  • Vertex 개수 + Edge 개수

2. 깊이 우선 탐색 (DFS)

• 현재 정점에서 갈 수 있는 만큼 최대한 깊이 가고, 더 갈 곳이 없다면 이전 정점으로 돌아가는 방식이다.
• 스택을 이용하거나, 재귀호출을 통해 구현
• 여기서 한 노드에서 제일 마지막까지 탐색을 마치고 다시 돌아오는 과정을 백트래킹이라고 한다.
• 시간 복잡도 : O(V+E)

3. 다익스트라(Dijkstra)

• 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

• 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택하는 방법.
  • 매번 가장 적은 비용을 가진 노드를 하나씩 꺼낸 다음 그 노드를 거쳐가는 비용, 즉 가장 적은 비용을 하나씩 선택하는 로직으로 구성
• 힙 자료구조를 사용해 구현
• 시간 복잡도
  • 인접행렬 O($V^2$)
  • 인접리스트 O((V+E)logV)
• 공간 복잡도
  • 인접행렬 O($V^2$)
  • 인접 리스트 O(V+E)

4. 플로이드 와샬(Floyd Washall)

• 전체 노드를 연결하는 최단 경로 구하는 알고리즘.
• 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 다이나믹 프로그래밍 유형이 속함.
• 애초에 거쳐가는 정점을 하나씩 다 설정을 하여 직접 확인하는 방법, 즉 거쳐가는 정점을 기준으로 최단 거리를 구하도록 구성
• 시간 복잡도 : O($V^3$)
• 공간 복잡도 : O($V^2$)

질문

다익스트라 vs 최소 스패닝 트리

• 다익스트라 : 한 노드에서 다른 노드까지 가장 작은 가중치를 가지는 경로
• 최소 스패닝 트리 : 각 노드들의 가중치가 가장 작은 상태로 모든 vertex(node)를 연결하는 경로