자료구조 - 그래프

 

정의

그래프(graph)는 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조이다. 지하철 노선도나 전기회로 같이 다양한 객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 수 있는 논리적 도구이다. (선형 자료구조, 트리도 그래프로 표현할 수 있다.)

 

그래프는 정점과 간선의 집합으로 구성되는데, 정점은 노드(node), 간선은 링크(link)라고 한다. 수학적으로 그래프는 G = (V, E)와 같이 표시하는데, V(G)는 정점들의 집합, E(G)는 간선들의 집합을 의미한다. 정점은 객체(object)를 의미하고, 간선은 이러한 객체들 간의 관계를 의미하는데, 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.

 

 

 

 

시각적인 형태가 그래프의 정의는 아니다. 아래의 두 그래프는 서로 다르게 보이지만 동일한 그래프를 나타낸다. 같은 객체들을 가지고, 객체들 간의 관계도 정확히 일치하기 때문이다. 즉, 그래프는 오직 정점과 간선의 집합이며, 시각적 표현은 이해를 돕는 역할이다.

---

 

그래프의 종류

-   무방향 그래프 (undirected graph)

: 간선에 방향이 표시되지 않은 그래프. 하나의 간선은 양방향으로 갈수 있는 길을 의미하기 때문에 (A, B)와 (B, A)는 동일한 간선이다.  다음 그림은 무방향 그래프의 예이다.

 

V(G1) = {A, B, C, D}   E(G1) = {(A, B), {A, C), (A, D), (B, C), (C, D)}

 

  

 

V(G2) = {A, B, C, D}   E(G2) = {(A, B), (A, C)}

 

 

 

-  방향 그래프 (directed graph)

: 간선에 방향성이 존재하는 그래프. 간선은 화살표로 표시되는데, 일방통해 도로와 같이 한쪽 방향으로만 갈 수 있다.  따라서 <A, B>와 <B, A>는 서로 다른 간선이다. 다음 그림은 방향 그래프의 예이다.

V(G3) = {A, B, C}   E(G3) = {<A, B>, <B, A>, <B, C>}

 

 

-  가중치 그래프 (weighted graph): 간선에 비용이나 가중치가 할당된 그래프를 말한다. 네트워크라고도 한다. 간선이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있어 보다 복잡한 관계를 표현할 수 있다. 도시와 도시를 연결하는 도로의 길이나, 이동시간, 통신망의 사용료 등을 추가로 표현할 수 있어 응용 분야가 광범위 하다. 

 

 

-  부분 그래프 (subgraph)

: 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프를 G의 부분 그래프라 한다.

---

 

그래프 용어

-  인접 정점 (adjacent vertex)

: 간선에 의해 직접 연결된 정점

 

-  정점의 차수 (degree) 

: 정점에 연결된 간선의 수. 모든 정점의 차수를 합하면 간선 수의 2배가 되는데, 하나의 간선의 두 개의 정점에 인접하기 때문이다. 

방향 그래프는 정점의 차수가 두 가지로 나뉘는데, 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수(out-degree)라고 한다.

 

-  경로 (path)

: 간선을 따라 갈 수 있는 길을 말하며, 정점의 나열로 표시된다. 경로를 구성하는데 사용된 간선의 수를 경로의 길이라고 한다.

 

-  단순 경로(simple path)와 사이클(cycle)

: 경로 중에서 반복되는 간선이 없는 경우를 단순 경로라 한다. 그릭고 단순 경로의 시작 정점과 종료 정점이 같다면 사이클이라 한다. 

 

- 연결 그래프 (connected graph)

: 모든 정점 사이에 경로가 존재하는 그래프. 따로 떨어진 정점이 없이 모든 정점들이 연결되어 있는데, 그렇지 않은 그래프는 비연결 그래프라고 한다. 

 

- 트리 (tree)

: 사이클을 가지지 않는 연결 그래프. 그래프의 임의의 두 정점을 연결하는 경로는 오직 하나 뿐이다. 

 

- 완전 그래프 (complete graph)

: 모든 정점 간에 간선이 존재하는 그래프. 무방향 완전 그래프의 정점 수를 n개라면, 하나의 정점은 n - 1개의 다른 정점으로 연결되므로 간선의 수는 n * (n - 1) / 2가 된다. (n = 4라면 간선의 수는 6개이다.)

 

---

 

그래프의 추상 자료형

 

데이터 : 정점과 간선의 집합
연산
  -  isEmpty() : 그래프가 공백인지 확인
  -  countVertex() : 정점의 수 반환
  -  countEdge() : 간선의 수 반환
  -  getEdge(u, v) : 정점 u에서 정점 v로 연결된 간선 반환
  -  degree(v) : 정점 v의 차수 반환
  -  adjacent(v) : 정점 v에 인접한 모든 정점의 집합 반환
  -  insertVertex(v) : 그래프에 정점 v 삽입
  -  insertEdge(u, v) : 그래프에 간선 (u, v) 삽입
  -  deleteVertex(v) : 그래프의 정점 v 삭제
  -  deleteEdge(u, v) : 그래프의 간선 (u, v) 삭제

 

만약 방향 그래프라면 차수를 반환하는 degree 연산에 degree(v, out)과 같이 진입차수와 진출차수를 구분하는 매개변수가 추가되어야 한다.

 

하나의 정점이 삭제되면 그와 연결된 모든 간선들도 함께 삭제되어야 한다.

간선이 삭제되더라도 정점에는 변화가 없다. 간선은 2개의 정점을 이용해 표현하기 때문에 삽입을 위해서는 그래프에 반드시 두 정점이 정의되어 있어야 한다.

 

---

그래프의 표현

-  인접 행렬을 이용한 표현

그래프에서 정점들의 연결 관계를 행렬을 사용하여 표현한 것을 인접 행렬(adjacency matrix)이라 한다. 그래프 G의 정점의 개수가 n이라면 n * n의 행렬(2차원 배열 구조) M이 필요하다. M의 각 원소들은 행과 열에 해당하는 정점간의 간선 정보를 나타낸다. 

 

무방향 그래프

방향 그래프

두 정점 사이에 간선이 없으면 0 또는 None을 갖도록 하고, 간선이 있으면 1을 갖는다. 가중치 그래프라면 간선이 있는 성분을 그 가중치 값으로 표현한다. (자체 간선(자신에서 출발해서 자신으로 들어오는 간선)을 허용하지 않으므로 행렬의 대각선 성분은 0으로 표시)

 

무방향 그래프의 인접 행렬은 대칭 행렬이 되고, 방향 그래프는 일반적으로 대칭이 아니다.

 

 

그래프의 정점 데이터는 파이썬의 리스트를 사용하면 간단히 표현된다. 2차원 배열 구조(리스트의 리스트)로 표현한다. 인접 행렬의 각 요소들은 정점간의 간선이 존재하는 경우 1을 그렇지 않은 경우 0을 갖는다.

 

2차원 배열 구조로 표현

 

 

가중치 그래프라면 행렬 요소에 가중치를 표시하면 된다. 구분을 위해 간선이 없는 경우 None으로 처리한다.

 

가중치 그래프 표현

 

- 인접 리스트를 이용한 표현

인접 리스트(adjacency list)는 그래프의 각 정점과 연결된 인접 정점들을 각각의 리스트로 표현한 방법이다. 각 정점은 인접 리스트를 이용해 자신과 간선으로 직접 연결된 인접 정점들을 관리한다. 이때 리스트로는 연결된 구조를 사용할 수도 있고 배열 구조인 파이썬의 리스트를 사용할 수도 있다.

 

예를 들어, 연결된 구조를 사용한다면 그래프는 각각의 인접 리스트를 가리키는 헤더 포인터의 배열을 갖는다. 이제 정점의 번호만 알면 그 정점의 연결 리스트를 이용해 인접 정점들에 쉽게 접근할 수 있다.

 

무방향 그래프

 

방향 그래프

 

무방향 그래프에 간선 (u, v)를 추가해 보자. 정점 u의 연결 리스트에 v 노드를 추가해야 한다. 정점 v의 연결 리스트에도 u를 추가해야 하기 때문에 연결 리스트에 실제로 만들어지는 노드의 수는 간선의 수의 2배이다. (순서는 중요하지 않다.)

방향 그래프에서는 인접 리스트의 노드의 수는 그래프의 간선의 수와 같다. 

 

 

 

인접 리스트는 연결 리스트로 표현할 수도 있지만, 파이썬의 리스트를 사용하는 것이 가장 간단하다. 

 

 

리스트를 인덱스로 나타내면 연결 관계를 한눈에 파악하기 쉽지 않다. 파이썬은 다음과 같이 정점 정보를 리스트에 직접 표시할 수 있다.

 

 

정점과 인접 리스트를 한꺼번에 표시할 수도 있다. 가장 간단한 방법은 정점과 그 정점의 인접리스트를 튜플(or 리스트)로 묶어 하나로 처리하는 것이다. 하나의 변수 graph를 통해 모든 정보를 알 수 있다.

 

예를 들어, graph[2][0]은 정점 C의 객체이고, graph[2][1]은 정점 C의 인접 리스트이다. 정점 C의 첫 번째 인접 정점은 graph[2][1][0]을 통해 알 수 있다.

 

 

그래프는 선형 자료구조가 아니기 때문에 집합이나 딕셔너리로 표현할 수도 있다. 딕셔너리는 각 정점에 각각의 인접 리스트를 대응(mapping)시키는 것이다. 정점의 이름을 key로, 정점의 인접 리스트를 value로 하는 엔트리로 구성된다.

 

 

- 인접 행렬과 인접 리스트의 복잡도 비교

정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프에서 주요 연산에 대한 인접 행렬과 인접 리스트의 복잡도를 비교해보자.

 

인접 행렬	인접 리스트
항상 n^2개의 메모리 공간이 필요. 정점에 비해 간선의 수가 매우 많은 조밀 그래프(dense graph)에서 효과적	n개의 연결 리스트가 필요하고 2e개의 노드가 필요. 즉 n + 2e개의 메모리 공간 필요. 희소 그래프(sparse graph)에서 효과적

 

 

---

 

그래프의 탐색

그래프의 탐색은 가장 기본적인 연산으로 하나의 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업이다. 실제로 많은 그래프 문제들이 단순히 정점들의 탐색만으로 해결된다.

예를 들어. 전자회로에서도 어떤 두 단자가 서로 연결되어 있는지를 판단하는 것은 그래프 탐색만으로 가능하다. 기본적인 그래프 탐색 방법에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 두 가지가 있다.

 

 

(아래의 알고리즘에선 인접리스트(딕셔너리, 집합 사용)를 사용해 그래프를 표현한다.)

 

 

- 깊이 우선 탐색

: 깊이 우선 탐색은 스택을 이용한 미로 탐색과 유사하다. 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색하는 방법으로 출구를 찾는 방법이다.

 

탐색 과정에 이미 방문한 정점을 관리하는 집합(또는 리스트)이 필요하다. 이를 visited라 하면, 처음에는 visited가 공집합이어야 한다. 탐색이 시작되면 시작 정점에서부터 임의의 인접한 정점으로 탐색을 진행하는데, 이때 한번 방문한 정점은 반드시 visited에 넣어야 한다. 한 정점에서의 탐색은 그 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점으로만 가능하다. 만약 더 이상 방문하지 않은 인접 정점이 없으면 가장 마지막에 만났던 정점으로 되돌아간다. 거기서 다시 아직 방문하지 않은 인접 정점을 찾아 다시 동일한 방법의 탐색을 진행한다. (스택을 사용하여 구현할 수 있지만, 순환의 형태로 구현하는 것이 더 직관적이다.)

 

 

 

A에서 시작하여 B, D, C, E, G, H순으로 순환 호출을 진행하는데, H에서 더 이상 가지 않은 인접 정점이 없으면 순환 함수가 반환되고 이전의 갈림길로 되돌아간다. D에서 아직 방문하지 않은 인접 정점이 있으므로 F로 다시 탐색을 진행한다. 이제 F에서도 더 이상 방문하지 않은 정점이 없으므로 D, B, A 순으로 되돌아가서 탐색이 완료된다.

 

매개변수로 그래프, 시작 정점, 그리고 visited를 사용하는데, 디폴트 인수를 사용해 dfs가 처음 호출되면(인수가 없이 호출함) 공백상태의 방문정점 집합 visited를 생성하도록 했다.

 

def dfs(graph, start, visited=set()): # 처음 호출할 때 visited 공집합
    if start not in visited: # start가 방문하지 않은 정점이면 
        visited.add(start) # start를 방문한 노드 집합에 추가
        print(start, end='') # start를 방문했다고 출력
        nbr = graph[start] - visited # nbr : 차집합 연산 이용
        for v in nbr: # v ∈ {인접정점} - {방문정점}
            dfs(graph, v, visited) # v에 대해 dfs를 순환적으로 호출

 

코드에서 graph[start]는 정점 start의 정점 start의 인접 정점집합을 나타낸다. 아직 방문하지 않은 인접 정점 집합(nbr)을 구하기 위해 집합 클래스에서 제공하는 차집합(graph[start] - visited) 연산을 이용했다.

 

깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프가 인접리스트로 표현되어 있다면 O(n + e)이고, 인접 행렬오 표시되어 있다면 O(n^2)이다. 이는 희소 그래프인 경우 깊이 우선 탐색은 인접 리스트의 사용이 인접행렬 사용보다 시간적으로 유리함을 보여준다.

 

 

- 너비 우선 탐색

너비 우선 탐색(BFS)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 잇는 정점을 나중에 방문하는 순회 방법이다. 가까운 거리에 있는 정점들을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 자료구조로 큐를 사용한다. 정점들이 방문될 때마다 큐에 인접 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 맨 앞에서 정점을 꺼내 그 정점과 인접한 정점들을 차례대로 방문한다. 초기 상태의 큐에는 시작 정점만이 저장되어 있고, 너비우선 탐색 과정은 큐가 공백 상태가 될 때까지 계속된다.

 

 

(파이썬의 collections 모듈을 사용하여 구현한다. 이 모듈은 내장 자료형인 튜플이나 딕셔너리에 대한 확장 데이터 구조들을 제공하는데, 전단과 후단에서 삽입/삭제를 할 수 있는 deque 클래스를 제공한다. deque는 전단과 후단이 아닌 왼쪽 오른쪽 개념을 사용한다.)

 

import collections

def bfs(graph, start):
    visited = set([start]) # 맨 처음에는 start만 방문한 정점임
    queue = collections.deque([start]) # 컬렉션의 덱 객체 생성(큐로 사용)
    while queue: # 공백이 아닐 때까지
        vertex = queue.popleft() # 큐에서 하나의 정점 vertext를 빼냄
        print(vertex, end='') # vertext는 방문했음을 출력
        nbr = graph[vertex] - visited # nbr : 차집합 연산 이용
        for v in nbr: # v ∈ {인접정점} - {방문정점}
            visited.add(v) # v는 방문했음
            queue.append(v) # v를 큐에 삽입

 

너비 우선 탐색은 그래프가 인접 리스트로 표현되어 있으면 전체 수행시간이 O(n + e)이며, 인접행렬로 표현되어 있는 경우는 O(n^2) 시간이 걸린다. 너비우선 탐색도 깊이우선 탐색과 같이 희소 그래프를 사용할 경우 인접리스트를 사용하는 것이 효율적이다.

 

---

 

 

연결 성분 검사

연결 성분 (connected component)이란 최대로 연결된 부분 그래프를 말한다. 예를 들어 다음의 그래프에는 2개의 연결된 부분 그래프, 즉 2개의 연결 성분이 있다.

 

 

연결 성분을 찾기 위해서 DFS나 BFS를 이용할 수 있다. 여기선 DFS를 사용하자. 먼저 그래프의 임의의 정점을 선택하고, DFS를 통해 연결되어 있는 모든 정점들을 출력한다. 더 이상 연결된 정점이 없으면 그래프에서 아직 방문되지 않은 다른 정점을 선택에 동일한 과정을 되풀이한다. 이 과정을 그래프의 모든 정점이 방문될 때까지 반복하면 모든 연결 성분들을 찾을 수 있다.

 

프로그램에선 연결성분의 검사가 끝나면 전체 연결 성분의 개수와 각 부분 그래프의 정점 리스트를 구해 출력하도록 한다. 주 함수는 다음과 같이 방문하지 않은 정점 vtx에 대해 그래프 탐색 dfs_cc()를 이용하여 vtx와 연결된 모든 정점의 리스트 color를 만들고 이를 부분 그래프 리스트 colorList에 추가한다.

 

def find_connected_component(graph):
    visited = set() # 이미 방문한 정점집합
    colorList = [] # 부분 그래프별 정점 리스트
    
    for vtx in graph: # 그래프의 모든 정점들에 대해
        if vtx not in visited: # 방문하지 않은 정점이 있으면
            color = dfs_cc(graph, [], vtx, visited) # 새로운 컬러 리스트
            colorList.append(color) # 컬러리스트 추가
            
    print(f"그래프 연결성분 개수 : {len(colorList)}")
    print(colorList) # 정점리스트들을 출력
    
def dfs_cc(graph, color, vertex, visited):
    if vertex not in visited: # 아직 칠해지지 않은 정점에 대해
        visited.add(vertex) # 이제 방문했음
        color.append(vertex) # 같은 색의 정점 리스트에 추가
        nbr = graph[vertex] - visited # nbr : 차집합 연산 이용
        for v in nbr: # v ∈ {인접정점} - {방문정점}
            dfs_cc(graph, color, v, visited) # 순환호출
    return color # 같은 색의 정점리스트 반환

 

---

 

 

신장 트리

신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 트리의 일종이므로 모든 정점들이 연결되어 있고 사이클이 없어야 하고, 그래프의 n개의 정점을 정확히 (n - 1)개의 간선으로 연결해야 한다. 신장 트리를  찾기 위해 DFS나 BFS를 이용할 수 있다. 같은 그래프에 다양한 신장 트리가 가능하다.

다음은 같은 그래프를 깊이우선과 너비우선으로 탐색한 경우의 신장 트리의 예이다.

 

 

신장 트리는 깊이우선이나 너비우선 탐색 도중에 사용된 간선들만 모으면 된다. 다음은 너비우선 탐색 함수 bfs를 수정해 탐색 도중에 추가되는 간선을 순서대로 출력한 코드와 위의 그래프에 대한 실행 결과이다.

 

import collections

def bfsST(graph, start):
    visited = set([start]) # 맨 처음에는 start만 방문한 정점임
    queue = collections.deque([start]) # 컬렉션의 덱 객체 생성(큐로 사용)
    while queue: # 공백이 아닐 때까지
        v = queue.popleft() # 큐에서 하나의 정점 v를 빼냄
        nbr = graph[start] - visited # nbr = {v의 인접정점} - {방문정점}
        for u in nbr: # 갈 수 있는 모든 인접 정점에 대해
            print("(", v, ",", u, ")", end="") # (v,u)간선 추가
            visited.add(u) # 이제 u는 방문했음
            queue.append(u) # u를 큐에 삽입

 

---

 

 

위상 정렬

방향 그래프에 조재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬(topological sort)이라고 한다.

 

 

예를 들어, 자료구조를 수강하려면 먼저 컴퓨터개론을 수강해야 하고, 인공지능을 수강하려면 자료구조, 알고리즘, 운영체제를 모두 먼저 수강해야 한다. 학위를 취득하려면 모든 교과목들을 순서에 따라 모두 수강해야 한다. 방향 그래프에서 간선 <u, v>가 있다면 "정점 u는 정점 v를 선행한다"고 말한다.

 

위상 정렬을 위해서는 방향 그래프에 사이클이 존재하지 않아야 한다. 사이클이 있다는 것은 사이클 상의 모든 과목이 선수 과목을 갖게 되기 때문에 어떤 교과목도 수강할 수 없음을 말한다.

 

<A, B, C, D, E, F>, <B, A, C, D, E, F>, <A, C, B, E, D, F> 등은 모두 가능하다. 즉, 가능한 위상 정렬에는 여러 가지가 있다.

<C, A, B, D, E, F>는 위상 순서가 아니다. 왜냐하면 간선 <A, C>가 있으므로 A를 수강한 후 C를 수강해야 하는데 A보다 먼저 C를 수강했기 때문이다.

 

방향 그래프의 위상 정렬 알고리즘을 생각해 보자. 먼저, 진입 차수가 0인 정점을 선택하고, 선택된 정점과 여기에 부착된 모든 간선을 삭제한다(이미 수강했으므로). 이때, 간선이 삭제되므로 삭제되는 간선과 연결된 남아있는 정점들의 진입차수도 변경되어야 한다. 이 과정을 반복하여 모든 정점이 삭제되면 알고리즘이 종료된다. 전체 과정에서 정점이 삭제되는 순서가 위상 순서(topological order)가 된다.

 

만약 진입 차수 0인 정점이 여러 개 있다면 어느 정점을 선택해도 된다. 또한 그래프에 남아 있는 정점들 중에 진입 차수 0인 정점이 없다면 위상 정렬은 불가능하다. 이것은 그래프에 사이클이 존재하는 것을 말한다.

 

위상 정렬 과정의 예 : B-E-A-C-D-F

 

진입 차수가 0인 정점 B를 시작으로 정점 B와 간선을 제거하면, 다음 단계에서 정점 E의 진입 차수가 0이 되고, 후보 정점은 A, E가 된다. 만약 정점 E를 선택하면 다음 단계에서는 오직 정점 A만이 후보가 된다. 다음에 정점 A가 선택되고 정점 C가 진입 차수가 0가 되어 선택 가능하게 된다. 다음에 정점 C, 정점 D, 정점 F를 선택하면 <B, E, A, C, D, F>가 된다.

 

위상 정렬을 구현해 보자

• 인접행렬로 표현한 그래프를 이용한다.
• 각 정점의 진입 차수를 기록해야 한다. 진입차수는 리스트를 이용한다.
• 진입차수가 0인 정점들은 따로 관리하기 위해 리스트 vlist를 사용한다. 처음에는 inDeg에서 진입차수가 0인 정점들을 모두 찾아 vlist에 추가한다.
• vlist가 공백이 아니면 하나의 정점 v를 꺼내 출력하고 v에 인접한 정점들의 inDeg를 1씩 줄인다. 진입차수가 0으로 줄어든 정점은 vlist에 추가한다. 이 과정을 vlist가 공백이 될 때 까지 반복한다.

 

def topological_sort_AM(vertex, graph):
    n = len(vertex)
    inDeg = [0] * n # 정점의 진입차수 저장
    
    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                inDeg[j] += 1 # 진입차수를 1 증가시킴
                
    vlist = [] # 진입차수가 0인 정점 리스트를 만듦
    for i in range(n):
        if inDeg[i] == 0:
            vlist.append(i)
            
    while len(vlist) > 0: # 리스트가 공백이 아닐 때 까지
        v = vlist.pop() # 진입차수가 0인 정점을 하나 꺼냄
        print(vertex[v], end='') # 화면 출력
    
        for u in range(n):
            if v != u and graph[v][u] > 0:
                inDeg[u] -= 1 # 연결된 정점의 진입차수 감소
                if inDeg[u] == 0: # 진입차수가 0이면
                    vlist.append(n) # vlist에 추가