그래프 (Graph)

출처 : https://towardsdatascience.com/10-graph-algorithms-visually-explained-e57faa1336f3

 

그래프 구조를 다루고 문제를 해결하기 위한 다양한 알고리즘으로 그래프의 형태, 방향, 가중치 등에 따라 다양한 종류로 분류

 

• 깊이 우선 탐색 (Depth-First Search, DFS)
  그래프를 탐색할 때 깊이를 우선으로 하여 노드를 방문
  스택 또는 재귀를 사용하여 구현하며, 주로 연결 요소의 탐색에 사용
  
  
• 너비 우선 탐색 (Breadth-First Search, BFS)
  그래프를 탐색할 때 너비를 우선으로 하여 노드를 방문
  큐를 사용하여 구현하며, 최단 경로, 트리의 레벨 순회 등에 활용
  
  
• 최단 경로 알고리즘
  그래프에서 두 노드 간의 최단 경로를 찾음
  다익스트라 알고리즘과 벨만-포드 알고리즘
  
  
• 최소 신장 트리 (Minimum Spanning Tree, MST)
  그래프에서 모든 노드를 포함하면서 간선의 가중치 합이 최소인 트리를 찾음
  프림 알고리즘과 크루스칼 알고리즘
  
  
• 위상 정렬 (Topological Sorting)
  방향 그래프에서 순서를 지키면서 모든 노드를 방문하는 순서를 찾음
  작업의 우선순위 결정에 사용
  
  
• 최대 유량 (Maximum Flow)
  네트워크 플로우 문제에서 최대 유량을 찾음
  포드-풀커슨 알고리즘과 에드몬즈-카프 알고리즘
  
  
• 그래프 컷 (Graph Cut)
  그래프에서 최소 컷을 찾거나 그래프를 분할
  네트워크 연결 및 클러스터링에 사용
  
  
• 트리 알고리즘
  트리 구조에서의 특수한 알고리즘으로, LCA (Lowest Common Ancestor) 등이 있음