[파이썬(Python)] 그래프(Graph)

 

2개 이상의 데이터의 관계를 표현하는 데 효과적인 자료구조입니다. 

노드(node, 정점)와 에지(edge, 간선)으로 구성되며, 방향이 있는 그래프와 방향이 없는 그래프로 구분됩니다.

 

그래프로 다음과 같은 탐색 알고리즘을 사용할 수 있습니다. 이번 포스트에서는 그래프와 관련된 알고리즘은 가볍게 다루겠습니다.

 

깊이 우선 탐색(DFS; Depth First Search)

시작 정점에서 한 방향으로만 탐색하다가 더 이상 갈 곳이 없으면 왔던 경로를 되돌아가며, 다른 노드와 연결된 노드 중 가장 마지막에 만났던 노드로 돌아가서 다른 방향으로 탐색을 시작합니다.

 

너비 우선 탐색(BFS; Breadth First Search)

시작 정점에서 갈 수 있는 모든 정점을 탐색한 후, 인접 정점에서 같은 방식으로 계속 탐색해나갑니다.

 

신장 트리

어떤 그래프의 부분 그래프로, 모든 정점이 적어도 한 번은 연결되어 있는 트리입니다. 트리 형태이므로 순환은 허용하지 않습니다.

 

최소 비용 신장 트리

무방향 그래프의 간선 마다 가중치가 있을 때 그 가중치의 합이 가장 작은 신장 트리를 최소 비용 신장 트리라고 합니다. 이를 찾아내기 위한 방법으로 Prim 방법과 Kruskal 방법이 있습니다. 이에 대해서는 추후 따로 다룰 예정입니다.

 

---

 

그래프 표현 방법

 

Adjacency List(연결리스트를 이용한 인접 리스트)

각 노드와 연결된 노드를 연결 리스트로 표현합니다. 노드에 저장된 인접 노드의 순서는 중요하지 않습니다.

Adjacency Matrix(순차 자료구조를 이용한 인접 행렬)

연결되었으면 1, 그렇지 않으면 0으로 연결 관계를 표현합니다.

---

 

그래프의 ADT

 

• Object: 정점 집합 V와 V에 속하는 u, v로 구성된 에지 집합 E로 구성된 튜플 G = (V, E)
• Operation
  • G.is_empty() -> Boolean
  • G.add_vertex() -> Integer
  • G.delete_vertex(v)
  • G.add_edge(u, v)
  • G.delete_edge(u, v)
  • G.adj(v) -> array : 정점 v에 인접한 정점 집합을 동적 배열로 반환

 

---

 

그래프 구현

코드 출처: 파이썬으로 배우는 자료구조 핵심 원리

 

class Graph:
    def __init__(self, vertex_num = None):
        # 인접 리스트
        self.adj_list = []
        self.vtx_num = 0
        # 정점이 있으면 True, 없으면 False
        # 정점이 삭제되어도 실제로 데이터를 지우지 않고, vtx_arr 배열 내 해당 데이터의 값을 False 처리해서 비활성화
        self.vtx_arr = []

        if vertex_num:
            self.vtx_num = vertex_num
            self.vtx_arr = [True for _ in range(self.vtx_num)]

            self.adj_list = [[] for _ in range(self.vtx_num)]

    def is_empty(self):
        if self.vtx_num == 0:
            return True
        return False
    
    # 정점 추가
    def add_vertex(self):
        for i in range(len(self.vtx_arr)):
            # vtx_arr[i] 값이 False면 삭제된 정점
            if self.vtx_arr[i] == False:
                self.vtx_num += 1
                self.vtx_arr[i] = True
                return i
        self.adj_list.append([])
        self.vtx_num += 1
        self.vtx_arr.append(True)
        return self.vtx_num - 1
    
    def delete_vertex(self, v):
        if v >= self.vtx_num:
            raise Exception(f"There is no vertex of {v}")
        # 정점 v가 있으면
        if self.vtx_arr[v]:
            # 정점 v의 인접 정점 집합을 초기화
            self.adj_list[v] = []
            self.vtx_num -= 1
            self.vtx_arr[v] = False

            for adj in self.adj_list:
                for vertex in adj:
                    if vertex == v:
                        adj.remove(vertex)

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def delete_edge(self, u, v):
        self.adj_list[u].remove(v)
        self.adj_list[v].remove(u)

    def adj(self, v):
        return self.adj_list[v]

 

 

---

 

 

Reference

그림으로 정리한 알고리즘과 자료구조 - 조민호
파이썬으로 배우는 자료구조 핵심 원리