그래프의 기본 개념, 표현 방법

그래프는 노드(Vertex)와 노드 간의 연결을 나타내는 간선(Edge)로 이루어진 자료 구조입니다. 그래프는 일반적으로 G = (V, E)로 표기하며, 여기서:

• V: 그래프의 정점(노드)들의 집합
• E: 정점 간의 연결 관계를 나타내는 간선들의 집합

그래프는 각기 다른 특징에 따라 여러 유형으로 분류될 수 있습니다:

• 무방향 그래프: 간선에 방향이 없는 그래프, 즉 (A, B)가 있다면 (B, A)도 존재하는 그래프입니다.
• 방향 그래프: 간선에 방향이 있어, 특정 방향으로만 이동 가능한 그래프입니다. 예를 들어 (A, B)가 있더라도 (B, A)는 존재하지 않을 수 있습니다.
• 가중치 그래프: 간선에 가중치가 부여된 그래프로, 간선마다 특정한 비용이나 거리가 존재합니다.
• 연결 그래프: 모든 정점이 간선으로 연결된 그래프입니다.

그래프는 이러한 특성을 활용하여 복잡한 연결 구조를 표현할 수 있으며, 다양한 문제 해결에 적용됩니다.

그래프는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 표현하는 두 가지 주요 방법이 있습니다. 각 표현 방식은 그래프의 특성과 용도에 따라 선택됩니다.

Python 코드 예제:
# 인접 행렬로 그래프 표현
n = 4  # 노드 개수
graph = [[0] * n for _ in range(n)]  # n x n 2차원 배열

# 간선 추가 예시 (무방향 그래프)
graph[0][1] = 1
graph[1][0] = 1
graph[1][2] = 1
graph[2][1] = 1
print(graph)
                

설명: 인접 행렬은 모든 정점 간의 관계를 빠르게 확인할 수 있으나, 메모리 사용량이 많아질 수 있습니다. 따라서 정점이 많고 간선이 적은 경우에는 비효율적일 수 있습니다.

Python 코드 예제:
# 인접 리스트로 그래프 표현
graph = [[] for _ in range(n)]

# 간선 추가 예시 (무방향 그래프)
graph[0].append(1)
graph[1].append(0)
graph[1].append(2)
graph[2].append(1)
print(graph)
                

설명: 인접 리스트는 필요한 간선만 저장하므로 메모리 효율성이 높으며, 노드 간 연결을 쉽게 관리할 수 있습니다. 특히, 희소 그래프(Sparse Graph)에서 효율적입니다.

그래프 이론에서 자주 사용되는 용어들을 이해하면, 그래프의 특성을 보다 쉽게 파악할 수 있습니다.

• 차수(Degree): 한 정점에 연결된 간선의 수로, 무방향 그래프에서는 차수가 연결된 간선의 수와 동일합니다.
• 경로(Path): 한 정점에서 다른 정점으로 이동하는 길로, 정점과 간선의 연속적인 연결로 이루어집니다.
• 사이클(Cycle): 경로 중에서 처음 정점과 끝 정점이 같은 경우를 말합니다.
• 연결 요소(Connected Component): 그래프에서 서로 연결된 정점들의 집합으로, 연결 요소는 그래프의 특성을 나타내는 중요한 요소입니다.

이 용어들을 통해 그래프의 기본 구조와 특성을 이해할 수 있으며, 이를 활용하여 다양한 알고리즘을 설계할 수 있습니다.