그래프는 현실 세계에서 상호 관계를 나타내는 자료 구조로서 매우 중요합니다. 이러한 그래프를 컴퓨터 프로그램에서 표현하는 방법은 여러 가지가 있습니다. 그 중에서도 주로 사용되는 방법으로는 인접 행렬과 인접 리스트가 있습니다.
인접 행렬 (Adjacency Matrix)
인접 행렬은 각 노드간의 연결 관계를 2차원 배열로 나타내는 방법입니다. 배열의 크기는 그래프의 노드 수에 따라 결정됩니다. 각 원소는 두 노드 사이의 연결 여부를 나타냅니다.
class AdjacencyMatrix:
def __init__(self, num_nodes):
self.num_nodes = num_nodes
self.matrix = [[0] * num_nodes for _ in range(num_nodes)]
def add_edge(self, u, v):
if 0 <= u < self.num_nodes and 0 <= v < self.num_nodes:
self.matrix[u][v] = 1
self.matrix[v][u] = 1
def remove_edge(self, u, v):
if 0 <= u < self.num_nodes and 0 <= v < self.num_nodes:
self.matrix[u][v] = 0
self.matrix[v][u] = 0
위 예제에서 AdjacencyMatrix 클래스는 add_edge 메서드를 통해 두 노드를 연결하고, remove_edge 메서드를 통해 두 노드의 연결을 제거할 수 있습니다.
인접 리스트 (Adjacency List)
인접 리스트는 각 노드마다 인접한 노드들을 연결 리스트로 나타내는 방법입니다. 각 노드를 표현하는 객체를 이용하여 인접한 노드들을 관리합니다.
class Node:
def __init__(self, value):
self.value = value
self.neighbors = []
def add_neighbor(self, node):
if node not in self.neighbors:
self.neighbors.append(node)
def remove_neighbor(self, node):
if node in self.neighbors:
self.neighbors.remove(node)
class AdjacencyList:
def __init__(self):
self.nodes = {}
def add_node(self, value):
node = Node(value)
self.nodes[value] = node
def add_edge(self, u, v):
if u in self.nodes and v in self.nodes:
self.nodes[u].add_neighbor(self.nodes[v])
self.nodes[v].add_neighbor(self.nodes[u])
def remove_edge(self, u, v):
if u in self.nodes and v in self.nodes:
self.nodes[u].remove_neighbor(self.nodes[v])
self.nodes[v].remove_neighbor(self.nodes[u])
위 예제에서 Node 클래스는 각 노드의 값을 저장하고 인접한 노드들을 관리하는 역할을 합니다. AdjacencyList 클래스는 add_node 메서드를 통해 노드를 추가하고, add_edge 메서드를 통해 두 노드를 연결하며, remove_edge 메서드를 통해 두 노드의 연결을 제거할 수 있습니다.
결론
그래프의 표현 방법은 문제의 성질과 알고리즘의 요구에 따라 다르게 선택되어야 합니다. 인접 행렬은 특정 노드와 다른 모든 노드의 연결 여부를 빠르게 확인할 수 있지만, 공간 복잡도가 높아질 수 있습니다. 반면 인접 리스트는 노드 사이의 관계를 효율적으로 관리할 수 있지만, 연결 여부를 확인하는 데에는 시간이 좀 더 걸립니다. 이러한 특성을 고려하여 그래프 표현 방법을 선택해야 합니다.