[Python] 그래프 기초

쉽지 않다.. 그래프 너란녀석..

 

 

그래프는 노드(또는 정점; Vertex)과 간선(Edge)을 포함한 비선형 자료구조
G = (V, E)

쾨니히스베르크의 다리 문제

그래프 이론은 오일러가 쾨니히스베르크의 다리 문제 에 대한 논문을 작성함으로 시작된 것으로 여겨진다. 이후 다양한 학자들에 의해 그래프 이론이 연구되었고, 구스타프 키르히호프로부터 키르히호프 회로 법칙을 출판하였고, 이는 네트워크 이론의 시초가 되었다.

관련 용어

• 정점 (vertex) : 노드(node)와 혼용하여 사용하며, 데이터가 저장되는 그래프의 기본 요소. 점
• 간선 (edge) : link라고도 하며, 보통 무방향 그래프에서 정점간의 관계(연결)을 말함
• 아크 (arc) : 방향성이 있는 방향그래프에서 사용하는 두 정점 사이의 연결을 의미
• 경로 (path) : 한 정점에서 시작해 연속된 간선을 통해 다른 정점으로 이어지는 순서 있는 정점의 집합
• 순환 (cycle) : 시작 정점과 끝 정점이 동일한 경로
• 차수 (degree) : 한 정점에 연결된 간선의 개수. 방향 그래프에서는 In-degree, Out-degree로 구분
• 인접 리스트 (Adjacency List) : 각 정점에 대해 연결된 정점들의 목록을 Linked List로 저장하는 그래프 표현 방식
• 인접 행렬 (Adjacency Matrix) : 모든 정점 쌍에 대해 간선을 2차원 배열로 표현하는 방식
• 트리 (Tree) : 트리 또한 그래프의 한 종류. root 에서 아래로 흐르는 방향그래프이지만, 편의상 방향은 생략하여 구조를 도식화함

vertex

정의

그래프 G = (V, E) 에서는 V는 정점들의 집합이며, 각 정점(vertex)은 그래프의 가장 기본이 되는 구성 요소.

이는 순수하게 추상적인개념으로, 단순히 “점”으로 생각할 수 있음.
이 자체는 내부 구조를 갖지 않으며, 오직 다른 정점과 연결을 통해 관계를 형성함

세부 속성 및 부가 정보

• 라벨 / 이름 : 정점을 구분하기 위한 식별자 역할. “A”, “B”, “C” 혹은 1, 2, 3 등으로 표시
• 가중치 : 정점 자체에 비용이나 점수, 중요도 같은 가중치를 부여할 수 있음.
  어떤 네트워크에서는 정점이 처리능력이나 리소스를 나타낼 수 있음
• 좌표 : 물리적 네트워크나 지리 정보 시스템(GIS) 에서는 각 정점에 (x,y) 좌표가 부여되어, 정점 간 실제 거리를 계산

응용 예

• 교통 네트워크 : 도시나 지점을 정점으로 보고 도로(Edge)로 연결
• 소셜 네트워크 : 사람이나 조직을 정점으로 보고 이들 간의 관계를 에지로 표현

node

정의

자료구조나 프로그램 내에서 vertex의 구체적 표현

메모리 상 실제로 존재하는 객체(object)로, 데이터와 다른 노드와 연결해주는 링크(pointer, reference)를 포함

구현 예시

class Node:
    def __init__(self, value):
        self.value = value        # 정점(또는 vertex)의 값. 예를 들어, 'A'나 1 등.
        self.adjacent = []        # 인접 노드 목록. 이 리스트는 이 노드와 연결된 다른 노드들을 저장함.

값 외에도, 그래프의 인접 정보 (연결된 node 또는 edge 정보)를 함께 보유

C, JAVA에서는 struct 또는 class로 node 구현하며 pointer를 사용하여 동적으로 연결

속성

• 데이터 필드: 정점에 대한 구체적 정보를 저장함. (예: 이름, 가중치, 좌표 등)
• 포인터/링크: 다른 노드와의 연결을 위한 참조. 연결 리스트, 트리, 그래프에서 중요한 역할을 함
• 추가 정보: 방문 여부, 깊이, 부모 노드 정보 등 알고리즘 실행 중 필요한 임시 데이터를 저장할 수도 있음

응용 예

• 각 vertex를 node 객체로 구현. node는 인접 node(또는 연결 edge에 대한 정보를 포함한 구조체)를 리스트나 배열로 관리

edge

정의

두 정점(vertex) 사이의 관계나 연결을 나타내는 추상적 선

일반적으로 e = (u, v) 또는 e = {u, v}와 같이 표현

방향성이 없는 경우, 단순히 두 정점간의 연결성을 나타냄

속성

• 무방향(Undirected Edge)으로, 두 정점 간 상호 관계가 대칭적임. u에서 v로 가는 것 과, v에서 u로 가는 것이 동일하게 취급
• 가중치(Weighted Edge) : edge에 특정 값(거리, 비용, 시간 등)을 부여할 수 있음. 가중치가 부여된 edge는 최단 경로, 최소 신장트리 등 알고리즘에 사용
• 표현
  • edge는 두 vertex의 식별자, node 객체의 참조를 저장하는 튜플이나 객체로 구현할 수 있음
  • 예를 들어, 인접 리스트 방식에서는 u에 대해 adj[u] = [(v, weight), … ] 와 같이 저장

응용 예

• 도로망 : 도시 사이의 도로를 에지로 나타내고, 도로의 길이나 통행 시간 등 가중치를 부여
• 네트워크 : 컴퓨터나 서버 간 연결을 에지로 표현하고, 대역폭이나 지연시간 등의 가중치를 포함

arc

정의

방향 그래프(Directed Graph)에서 사용. 한 방향으로 연결된 edge를 의미
일반적으로 (u, v)의 형태로 표현되며, 이는 정점 u에서 v로 단방향 연결을 나타냄

속성

• 방향성 : (u, v)와 (v, u)는 다른 연결임. 방향성이 있는 모델을 구현 시 활용
• 가중치 : (u, v, weight)와 같이 전송 비용이나 시간, 신뢰도 등을 나타낼 수 있음
• 구현 : 각 정점 u에 대해, 나가는 arc를 목록(리스트, 배열 등)으로 관리

class DirectedGraph:
def __init__(self):
    # 인접 리스트를 딕셔너리 형태로 저장함.
    # 키(key)는 정점(u)이고, 값(value)은 u에서 출발하는 아크들의 리스트임.
    # 각 아크는 (v, weight) 튜플로, 정점 u에서 정점 v로 가는 에지의 가중치를 나타냄.
    self.adj = {}

    def add_arc(self, u, v, weight=1):
        """
        정점 u에서 v로 가는 유향 에지(arc)를 추가함.
        가중치는 기본값 1을 사용함.
        만약 u나 v가 아직 그래프에 없다면, 먼저 정점으로 추가함.
        """
        # u와 v를 그래프에 추가(이미 존재하면 add_vertex는 아무 작업 안 함)
        self.add_vertex(u)
        self.add_vertex(v)
        # u의 인접 리스트에 (v, weight) 튜플을 추가하여, u에서 v로 가는 아크를 기록함.
        self.adj[u].append((v, weight))

응용 예

• 웹 그래프 : 웹 페이지 간 하이퍼링크는 보통 방향성이 있어, 한 페이지에서 다른 페이지로 연결되는 것을 arc로 표현
• 소셜 네트워크 : follower 관계는 유향성이 있어, 한 사용자가 다른 사용자를 팔로우 하는 것을 표현 할 수 있음

그래프형 자료구조의 장점

• 순서나 계층 구조에 제한 없이 다양한 관계를 표현할 수 있음
• 실제 문제해결에 유용하며, BFS, DFS, 최단 경로, 위상정렬 등 표준 알고리즘에 적용 가능(경로 찾기, 네트워크 분석, 데이터 클러스터링, 기계 학습 등)
• 복잡한 관계를 단순하고 직관적으로 모델링 할 수 있어 이해분석 용이

그래프형 자료구조의 단점

• 크거나 복잡도가 높은 그래프의 경우, 생성 및 조작에 많은 리소스가 필요할 수 있음
• 설계와 구현이 까다로워 오류가 발생하기 쉽고, 디버깅이 어려움
• 큰 그래프는 시각화와 그를 통한 분석이 어려움

인접 리스트 (Adjacency List)

그래프의 각 정점(vertex)에 대해 그 정점과 직접 연결된(인접한) 정점들의 목록(리스트 또는 배열)을 저장하는 방식. Linked List 로 표현. 즉 정점의 개수 만큼 인접 리스트가 존재.

그래프 (G = (V,E))에서 각 정점(u ∈ V)에 대해, u와 연결된 정점들의 집합 Adj(u)를 저장

장점

• 메모리 효율 : 인접 행렬에 비해 저장공간을 훨씬 적게 사용, 존재하는 간선만 관리하면 됨
• 유연한 구조 : 각 정점의 인접 정보를 동적으로 저장. 정점마다 연결된 에지의 수가 다를 때 효율적
• 순회 효율 : 노드와 연결되어있는 간선을 탐색하는 시간이 매우 빠름

단점

• 두 정점을 연결하는 특정 간선을 찾거나, 정점의 차수를 알기 위해서는 인접 리스트를 탐색해야 하므로, 그 차수만큼 시간이 필요함
• 인접 리스트 자체는 간단하지만, 그래프를 완전탐색 또는 행렬 연산이 필요한 경우는 추가 작업이 필요해 구현이 복잡

구현

# i, j 노드의 간선을 추가, 각 리스트에서 서로를 추가
def add_edge(adj, i, j):
        adj[i].append(j)
        adj[j].append(i)


# i, j 간선을 제거, 각 리스트에서 서로를 삭제
def remove_edge(adj, i, j):
    if j in adj[i]:
        adj[i].remove(j)
    if i in adj[j]:
        adj[j].remove(i)

def display_adj_list(adj):
        for i in range(len(adj)):
                print(f"{i} : ", end="")
                for j in adj[i] : 
                        print(j, end = " "_
                print()

# 초기값 설정. 4개의 노드, 간선 없음
V = 4
adj = [[] for _ in range(V)]

# 간선 추가
add_edge(adj, 0, 1)
add_edge(adj, 0, 2)
add_edge(adj, 1, 2)
add_edge(adj, 2, 3)

print("인접 리스트: ")
display_adj_list(adj)

remove_edge(adj, 1, 2) # 1-2 사이의 간선 제거

print("\n간선 (1, 2) 제거 후 인접 리스트:")
display_adj_list(adj)

출력

인접 리스트:
0: 1 2
1: 0 2
2: 0 1 3
3: 2

간선 (1, 2) 제거 후 인접 리스트:
0: 1 2
1: 0
2: 0 3
3: 2

인접 행렬 (Adjacency Matrix)

그래프의 정점(노드)를 2차원 배열로 만든 것. 직접 연결이 되어있으면 1, 아니면 0을 넣어서 배열을 완성시킴

장점

• 빠른 접근 : 두 정점 u, v 사이의 연결 여부를 O(1) 시간에 확인
• 구조적 단순성 : 2차원 배열로 표현하여 구현이 직관적, 분석시에도 이해가 용이

단점

• 메모리 사용 : 모든 정점 쌍에 대해 값을 저장하므로, 공간을 많이 차지. 정점 수가 많을 경우 O($V^2$)의 공간이 필요. 특히 간선이 적은 그래프에서는 많은 메모리 낭비가 발생
• 정점 추가 / 삭제 어려움 : 배열 크기 변경 작업이 비효율적이어서, 동적 그래프에서는 관리가 어려움

구현

# 간선을 생성하는 함수. 그래프가 구현되는 행렬(매트릭스)과 연결시킬 노드값 두개를 넣어줌
def add_edge(mat, i, j):

    # 무방향 그래프로, 양 노드에 (row, col)동일하게 간선을 2차원 배열로 구현
    mat[i][j] = 1  # 연결된 노드들은 0에서 1로 표현
    mat[j][i] = 1  

# 간선을 제거하는 함수 (무방향 그래프)
def remove_edge(mat, i, j):
    """
    정점 i와 j 사이의 에지를 제거.
    무방향 그래프이므로, mat[i][j]와 mat[j][i]를 모두 0으로 설정.
    """
    mat[i][j] = 0  # i에서 j 연결 제거
    mat[j][i] = 0  # j에서 i 연결 제거

def display_matrix(mat):
    for row in mat:
        print(" ".join(map(str, row)))  

if __name__ == "__main__":
    V = 4  # 노드의 수
    mat = [[0] * V for _ in range(V)]  # 노드의 수 만큼 2차원 배열 생성, 기본값 0(연결 없음)

    # 그래프에 간선을 추가
    add_edge(mat, 0, 1) # 노드 0과 1을 연결
    add_edge(mat, 0, 2) # 노드 0과 2를 연결
    add_edge(mat, 1, 2) # 노드 1과 2를 연결
    add_edge(mat, 2, 3) # 노드 2와 3을 연결

    # 구현된 인접 행렬을 출력
    print("인접 행렬:")
    display_matrix(mat)

    remove_edge(mat, 1, 2)

    # 1-2의 간선을 제거 후 출력
    print("\n간선 (1, 2) 제거 후 인접 행렬:")
    display_matrix(mat)

출력

인접 행렬:
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

간선 (1, 2) 제거 후 인접 행렬:
0 0 1 0  # 1의 노드에서 2의 노드로 연결된 간선 삭제
0 0 1 0  # 2의 노드에서 1의 노드로 연결된 간선 삭제
1 1 0 1
0 0 1 0

인접 행렬과 인접 리스트의 비교

• 간선(edge) 추가 : O(1)으로 동일
• 간선 삭제 : 인접행렬 O(1) > 인접리스트 O(n)
• 초기설정 : 인접리스트 O(n) > 인접행렬 O($n^2$)

그래프의 종류

1. 무방향 그래프(Undirected graph) : 방향성이 없고 (u, v) == (v, u) 모두 동일한 그래프
2. 방향 그래프(Directed graph) : 정점 간 방향성을 가진 그래프 (u, v) ≠ (v, u)
   

   

3. Connected graph
4. Disconnected graph : 최소 하나 이상의 정점이 연결되지 않아 다른 노드로 도달할 수 없는 그래프
   

   

5. 정규 그래프(Regular graph) : 모든 정점이 차수(degree)가 동일한 그래프
6. 완전 그래프(Complete graph) : 모든 정점이 서로 다른 정점끼리 연결된 그래프
   

   

7. Cycle graph : 각자의 차수를 최소 2개 가지고 있어, 순환을 하는 그래프
8. 순환 그래프(Cyclic graph) : 최소 하나의 순환을 가지고 있는 그래프
   

   

9. 방향 무순환 그래프 (DAG; Directed Acyclic graph) : 방향성을 가지고 있지만, 순환하지 않는 그래프
10. 이분 그래프(Bipartite graph) : 정점의 집합을 둘로 분할하여, 같은 그룹의 정점끼리는 간선으로 이어지지 않은 그래프
    

    

11. 가중치 그래프(Weighted graph) : 간선에 비용(cost) 또는 가중치(weight)가 할당된 그래프. G = (V, E, w) 같이 표현한다. w가 간선의 강도, 비용 또는 길이이다.