그래프는 현실 세계의 다양한 상황을 나타내고 분석하기 위한 중요한 도구입니다. 이 글에서는 그래프의 개념과 기본 용어에 대해 알아보겠습니다.

그래프란 무엇인가요?

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 추상적인 개념입니다. 정점은 그래프에서의 위치를 나타내며, 간선은 정점들을 연결하는 선입니다. 그래프는 다양한 형태와 종류가 있으며, 현실 세계의 다양한 문제를 그래프로 표현할 수 있습니다.

그래프의 기본 용어

• 정점(Vertex): 그래프에서의 위치를 나타내는 개체입니다. 보통은 숫자나 알파벳으로 표현되며, 고유한 식별자를 가지고 있습니다.
• 간선(Edge): 정점을 연결하는 선으로, 그래프에서 가장 중요한 요소 중 하나입니다. 간선은 두 정점 사이의 관계를 나타냅니다.
• 인접 정점(Adjacent Vertex): 한 간선으로 연결된 정점들을 의미합니다. 예를 들어, 정점 A와 B가 한 간선으로 연결되어 있다면, A와 B는 인접 정점입니다.
• 차수(Degree): 한 정점에 연결된 간선의 개수를 의미합니다. 입력 차수와 출력 차수가 있으며, 입력 차수는 해당 정점으로 들어오는 간선의 개수를, 출력 차수는 해당 정점에서 나가는 간선의 개수를 나타냅니다.
• 경로(Path): 그래프 상에서 한 정점에서 다른 정점으로 이동하는데 사용되는 간선들의 순서입니다.
• 사이클(Cycle): 경로의 시작 정점과 종료 정점이 동일한 경우를 말합니다. 그래프에서 사이클이 있는 경우, 일부 알고리즘의 동작을 예측하기 어려울 수 있습니다.

그래프의 종류

그래프는 방향성과 사이클의 유무에 따라 다양한 종류로 나눌 수 있습니다. 가장 일반적인 그래프 종류는 다음과 같습니다.

• 무방향 그래프(Undirected Graph): 간선에 방향성이 없는 그래프입니다. 즉, 한 정점에서 다른 정점으로 양방향으로 이동할 수 있습니다.
• 방향 그래프(Directed Graph): 간선에 방향성이 있는 그래프입니다. 한 정점에서 다른 정점으로 이동할 때, 방향이 정해져 있습니다.
• 가중치 그래프(Weighted Graph): 간선에 가중치가 있는 그래프입니다. 간선의 길이, 비용, 가중치 등을 나타내는 값이 존재합니다.
• 순환 그래프(Cyclic Graph): 사이클이 있는 그래프입니다. 즉, 한 정점에서 출발하여 여러 간선을 거쳐 다시 같은 정점으로 돌아올 수 있습니다.

# 간단한 무방향 그래프 예제

class Graph:
    def __init__(self):
        self.vertices = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        if v1 in self.vertices and v2 in self.vertices:
            self.vertices[v1].append(v2)
            self.vertices[v2].append(v1)
    
    def get_adjacent_vertices(self, vertex):
        if vertex in self.vertices:
            return self.vertices[vertex]

# 그래프 초기화
g = Graph()
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_vertex('D')

# 간선 추가
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
g.add_edge('D', 'A')

# 인접 정점 확인
adjacent_vertices = g.get_adjacent_vertices('A')
print(adjacent_vertices)  # ['B', 'D']

위 예제는 Python으로 구현된 간단한 무방향 그래프입니다.

이제 그래프의 개념과 기본 용어에 대해 알게되었습니다. 그래프는 다양한 문제를 해결하기 위한 강력한 도구로 활용될 수 있으며, 알고리즘과 데이터 구조에서 핵심적인 역할을 수행합니다. 다음 글에서는 그래프 알고리즘에 대해 자세히 알아보겠습니다.