Graph, Adjacency Matrix, Adjacency List

그래프(Graph)는 데이터의 집합을 정점(Vertex)과 이들 정점을 연결하는 간선(Edge)의 집합으로 표현한 자료구조다. 그래프는 다양한 종류가 있으며, 주요 분류 기준에는 방향성 여부와 가중치 존재 여부가 있다.

무방향 그래프(Undirected Graph)에서 간선은 방향성이 없어, 두 정점을 서로 연결만 시킨다는 의미를 가진다. 예를 들어, 정점 A와 B를 연결하는 간선은 "A에서 B로" 또는 "B에서 A로"의 구분 없이 양방향 모두를 의미한다. 서로간의 연결이 대칭적인 관계, 예를 들어 소셜 네트워크의 친구 관계, 도로망 등에서 사용된다.

 

방향 그래프(Directed Graph)에서 간선은 방향성을 가지며, "A에서 B로" 혹은 그 반대로의 명확한 방향이 존재한다. 이는 간선이 (A, B)로 표시될 때, A에서 B로의 한 방향 연결만을 의미한다. 방향이 중요한 관계를 모델링할 때 사용되며, 예로는 웹 페이지 간의 링크, 트위터의 팔로우 등이 있다.

 

가중치 그래프(Weighted Graph)에서 각 간선에는 가중치가 할당되어 있다. 이 가중치는 거리, 시간, 비용 등 간선을 통해 연결된 두 정점 사이의 관계의 "가중치"를 나타낸다. 가중치는 간선을 따라 이동하는 데 드는 비용이나 거리 등을 표현할 때 사용된다. 예를 들어, 도시 간의 이동 비용, 네트워크 상에서의 데이터 전송 시간 등을 모델링할 때 사용된다.

인접 행렬(Adjacency Matrix)은 그래프를 표현하는 방법 중 하나로, 그래프의 정점들 간의 연결 관계를 행렬로 나타낸 것이다. 이 방식은 그래프의 각 정점을 행렬의 행과 열에 대응시키고, 두 정점 사이에 간선이 존재하면 해당 위치의 행렬 값에 1(또는 가중치 값)을, 없으면 0을 저장한다.

 

V개의 정점을 가진 그래프는 V×V 크기의 행렬로 표현된다. 비방향 그래프의 경우, 인접 행렬은 대칭 행렬이 된다. 가중치가 있는 그래프의 경우, 1 대신 간선의 가중치 값을 행렬에 저장한다. 간선이 없는 경우 일반적으로 매우 큰 값(무한대를 의미하는 값)이나 -1을 사용하여 표현할 수 있다.

 

대각선 요소는 보통 0으로 설정된다, 자기 자신으로의 연결이 없다는 것을 의미한다. 하지만 특별한 경우(예를 들어, 루프를 허용하는 그래프)에는 다른 값을 가질 수도 있다.

 

그래프의 연결 관계를 간단하고 직관적으로 표현할 수 있고, 특정 두 정점 사이의 연결 여부를 O(1) 시간에 확인할 수 있다. 하지만 정점의 수에 따라 필요한 메모리 공간이 제곱으로 증가하기 때문에, 희소 그래프(Sparse Graph)에서는 메모리 낭비가 심할 수 있고, 간선의 수에 비례하지 않고, 정점의 수의 제곱에 비례하여 메모리 공간을 사용한다.

class Graph:
    def __init__(self, size):
        self.adjMatrix = [[0 for _ in range(size)] for _ in range(size)]
        self.size = size
    
    def add_edge(self, v1, v2):
        if v1 == v2:
            print("같은 정점은 연결할 수 없습니다.")
        self.adjMatrix[v1][v2] = 1
        self.adjMatrix[v2][v1] = 1  # 무방향 그래프의 경우

    def remove_edge(self, v1, v2):
        if self.adjMatrix[v1][v2] == 0:
            print("연결된 간선이 없습니다.")
        self.adjMatrix[v1][v2] = 0
        self.adjMatrix[v2][v1] = 0  # 무방향 그래프의 경우
    
    def __str__(self):
        return '\n'.join([' '.join([str(i) for i in row]) for row in self.adjMatrix])

# 그래프 생성 및 간선 추가 예시
graph = Graph(4)  # 4개의 정점을 가진 그래프
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

print(graph)

 

인접 리스트(Adjacency List)는 그래프를 표현하는 자료구조 중 하나로, 각 정점에 인접한 정점들을 연결 리스트로 나열하여 그래프의 연결 관계를 표현한다. 인접 리스트는 각 정점마다 해당 정점으로부터 나가는 간선의 목록을 저장한다. 이 방법은 특히 희소 그래프(Sparse Graph), 즉 정점들 사이의 간선이 상대적으로 적은 그래프를 표현하는 데 효율적이다.

 

각 정점마다 하나의 리스트를 갖고, 해당 리스트에는 그 정점에 인접한 모든 정점들이 포함된다. Python에서는 리스트의 리스트로 구현하거나, 리스트에 연결 리스트 또는 집합을 담아 구현할 수 있다. 가중치가 있는 그래프의 경우, (인접 정점, 가중치) 형태의 튜플을 리스트에 저장함으로써 간선의 가중치 정보를 함께 저장할 수 있다.

 

방향 그래프(Directed Graph)의 경우, 각 리스트에는 해당 정점에서 출발하는 간선의 정보만 저장한다. 비방향 그래프(Undirected Graph)에서는 두 정점 사이의 연결을 양쪽 정점의 리스트에 모두 표현한다.

 

실제로 연결된 간선의 정보만을 저장하기 때문에, 인접 행렬에 비해 메모리 사용이 효율적이다. 특히 간선의 수가 정점의 수보다 많지 않은 희소 그래프에서 유리하고 그래프의 정점이나 간선이 자주 추가되거나 삭제되는 동적인 상황에 유연하게 대응할 수 있다.

 

인접 리스트에서는 특정 두 정점 사이에 간선이 존재하는지 확인하기 위해 해당 정점의 리스트를 순회해야 하므로, 최악의 경우 O(V)의 시간이 소요될 수 있다.(V는 정점의 수)

class Graph:
    def __init__(self, numVertices):
        self.numVertices = numVertices
        self.adjList = [[] for _ in range(numVertices)]
    
    def add_edge(self, src, dest):
        self.adjList[src].append(dest)
        # 비방향 그래프의 경우, 아래 코드를 추가한다.
        # self.adjList[dest].append(src)
    
    def remove_edge(self, src, dest):
        if dest in self.adjList[src]:
            self.adjList[src].remove(dest)
            # 비방향 그래프의 경우, 아래 코드를 추가한다.
            # self.adjList[dest].remove(src)
    
    def print_graph(self):
        for i in range(self.numVertices):
            print(f"Vertex {i}: {self.adjList[i]}")

# 그래프 생성 및 간선 추가 예시
graph = Graph(4)  # 4개의 정점을 가진 그래프
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

graph.print_graph()