그래프의 종류와 표현방식

그래프의 종류

1. 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프입니다.
2. 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프입니다.
3. 가중치 그래프 (Weighted Graph): 간선에 가중치가 부여된 그래프입니다.
4. 비가중치 그래프 (Unweighted Graph): 모든 간선의 가중치가 동일한 그래프입니다.
5. 사이클 그래프 (Cyclic Graph): 하나 이상의 사이클을 가진 그래프입니다.
6. 비사이클 그래프 (Acyclic Graph): 사이클이 없는 그래프입니다. 트리(Tree)는 이에 속합니다.
7. 이분 그래프 (Bipartite Graph): 꼭짓점 집합을 두 개의 독립된 집합으로 분할할 수 있는 그래프입니다.
8. 완전 그래프 (Complete Graph): 모든 노드 쌍에 간선이 존재하는 그래프입니다.

그래프의 표현 방식

1. 인접 행렬 (Adjacency Matrix)

   • 2차원 배열을 사용합니다.
   • matrix[i][j]가 1이면 노드 i와 노드 j 사이에 간선이 있다는 의미입니다.
   • 공간 복잡도: (O(V^2))

   # Python 예제
   graph = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]

2. 인접 리스트 (Adjacency List)

   • 각 노드에 연결된 노드의 리스트를 저장합니다.
   • 공간 복잡도: (O(V + E))

   # Python 예제
   graph = {0: [1], 1: [0, 2], 2: [1]}

3. 간선 리스트 (Edge List)

   • 모든 간선을 하나의 리스트로 표현합니다.
   • 공간 복잡도: (O(E))

   # Python 예제
   edge_list = [(0, 1), (1, 2)]

4. 객체와 포인터 (Objects and Pointers)

   • 객체 지향 언어에서 각 노드를 객체로 표현하고, 이웃 노드를 포인터나 참조로 연결할 수 있습니다.

각 표현 방식은 그래프의 종류나 알고리즘의 요구사항에 따라 적합할 수 있습니다. 예를 들어, 인접 행렬은 완전 그래프나 노드 간의 연결 상태를 빠르게 확인해야 할 때 유용하며, 인접 리스트는 공간을 효율적으로 사용해야 하거나 간선의 수가 노드의 수에 비해 적을 때 유용합니다.