[알고리즘] 그래프 알고리즘(Graph Algorithm)이란?

그래프 알고리즘

• 네트워크 분석, 경로 찾기, 최적화 문제 등 다양한 문제를 해결할 수 있는 중요한 알고리즘이다.
• 그래프는 노드와 노드를 연결하는 엣지로 구성된 자료구조를 말한다.

그래프 기본 용어 정리

• 정점(Vertex, Node)
  • Vertex 또는 Node 라고 말한다. 
• 간선(Edge, Link)
  • Edge와 Link 두가지 용어를 사용한다.
  • 화살표 표시가 된 것도 있고 그냥 직선으로 표시된 것도 있는데, 둘 다 '간선' 이라고 말한다.
• 가중치
  • 간선 위에 표시된 숫자이다.
  • 가중치가 있는 그래프가 있고 없는 그래프가 있는데, 가중치가 없다면 모두 동일한 가중치를 가진다고 보면 된다.
  • 해당 간선을 타고 이동할 때 필요한 비용 등을 표현하는 것에 사용된다. 

그래프 종류

• 방향 그래프(Directed Graph)
• 무방향 그래프(Undirected Graph)
• 가중치가 있는 그래프(Weighted Undirected Graph)
• 가중치가 있는 유방향 그래프(Weighted Directed Graph)

그래프 구현 방법

• 인접 리스트(Adjacency List)
  • 각 노드에 연결된 모든 노드의 리스트를 저장하는 방식으로, 특정 노드와 인접한 노드들을 바로 알 수 있다.

• 인접 행렬(Adjacency Matrix)
  • 두 노드 사이에 정점이 있는지 없는지를 2차원 배열에 저장한 Matrix 이다.
  • 즉, 노드 x에서 y로 가는 간선이 있다면 adj[x][y]의 값이 1이고, 없다면 0이 된다.
  • 대각선 노드 즉, x와 y 인덱스가 같으면, adj[x][y]은 항상 0이다.

인접 행렬은 노드 간의 연결 여부를 빠르게 확인할 수 있지만, 모든 노드에 대한 관계를 기록하기 때문에 메모리 소비가 크다는 단점이 있다. 

그래프 알고리즘 종류

• 그래프 탐색 알고리즘
  • BFS (Breadth First Search)
  • DFS (Depth First Search)
• 최단 경로 알고리즘
  • 다익스트라 알고리즘 (Dijkstra Algorithm)
  • 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
  • 플로이드 알고리즘 (Floyd Algorithm)
• 그 밖의 그래프 알고리즘
  • 최소 신장 트리 (Minimum Spanning Tree)
    • 크루스칼 (Kruskal) 알고리즘
    • 프림 (Prim) 알고리즘