그래프(Graph)란?

그래프의 기본 컨셉

노드 간 연결될 수 있다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있다.
트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프 형성이 가능하기 때문에 다른 범위의 개념으로 필요한 자료구조이다.
- 예를 들어, 오브젝트간의 관계를 표현할 때 유용하다.(SNS, 도로상의 차량 검색, 운송 시스템)

그래프는 기본적으로 위 그림처럼 노드 또는 정점(vert)과 간선(edge)으로 연결되어있다.

그래프와 트리의 특징

그래프는 노드간의 관계, 트리는 노드간의 계층을 표현한다.
그래프와 트리는 서로 다른 개념이다.
- 트리에는 그래프에는 없는 계층 개념이 있다.

그래프의 유형

그래프의 특성은 방향성(directed) 또는 무방향성(undirected)이다.
그래프가 한쪽 방향으로 설명될 수 있으면 directed 그래프가 가장 적합하다.

방향성 그래프는 보는 것처럼 순서가 있으므로 마지막 노드(리프, leaf)가 있다.
위 그림에서는 ‘F’가 리프노드이다.

위처럼 방향성 그래프는 양방향(bidirectional)이 될 수도 있다.
- 예를 들어 모든 도로가 일방 통행이기 때문에 도로 지도는 방향이 지정되지만, 대부분의 거리는 양방향 도로로 구성된다.
관계의 목적이 상호 교환이라면, 무방향 그래프가 가장 적합하다.
교환 관계는 항상 상호이므로 무방향 그래프가 여기에서 가장 의미가 있다.

위처럼 무방향성은 방향(화살표)이 따로 지정되어 있지 않다.
간선으로 연결된 노드들끼리는 서로 인접(adjacent)해 있다고 하며, 이웃(neighbor)이라고 지칭한다.

순환 및 비순환 그래프(Cyclic & Acyclic Graphs)

순환(루프)을 형성할 수 있는 경우(방문한 노드에 다시 방문) 그래프는 순환 그래프이다.
- 아래 이미지에서 B에서 시작한 다음 가장자리를 따라 C, E, D로 이동한 다음 B(이미 방문한 노드)로 돌아갈 수 있다.

무방향 그래프는 항상 동일한 노드에 재방문할 수 있으므로 순환 그래프이다.
순환을 형성할 수 없는 경우(모서리를 따라 이미 방문한 노드에 방문할 수 없는 경우) 비순환 그래프라고 한다.

가중 그래프(Weighted Graphs)

가중 그래프는 각 엣지(edge)의 가중치에 할당된 특정값을 호출한다.
가중치는 서로 다른 그래프에서 서로 다른 데이터를 나타낸다.
예를 들어, 도로 구간을 나타내는 그래프에서 가중치는 도로의 길이를 나타낼 수 있다.
그래프에서 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다.
- 가중치는 모든 경로 비교 시, 어떤 경로를 선택할 지에 사용된다.

순회는 그래프에 연결된 노드를 탐색한다.
중요한 것은 아직 방문하지 않은 노드의 순회 순서이다.
순회개념은 향후 배우게 되는 DFS, BFS와 같은 순회 알고리즘과 연관되어 있다.

DAGs(Directed Acyclic Graphs)

방향성 비순환 그래프(DAG)는 순환되지 않고 특정한 단방향 그래프이다.
즉, 아래 그림처럼 edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬할 수 있다.

그래프의 활용

그래프를 나타내는 두가지 방법은 인접 리스트(adjacency lists)와 인접 행렬(adjacency)이다.
그래프를 구현할 때 저장할 데이터 유형과 그래프에서 실행해야하는 작업을 이해하는 것이 중요하다.
아래 그림은 인접 행렬과 인접 리스트를 사용하여 그래프를 표현하는 방법의 예이다.
- 각 유형을 사용할 때, verts C와 D 사이의 관계를 어떻게 표현하는 지가 중요하다.

인접 리스트(Adjacency List)

인접 리스트에서 그래프는 전체 노드 목록을 저장한다.

# 위 그림에 대해 딕셔너리를 사용한 인접리스트 예시
# 노드가 키가 되고, 인접노드가 값이 되는 딕셔너리이다.
# 가장자리 노드들은 set으로 구현되어 있다.

class Graph:
    def __init__(self):
        self.vertices = {
                            "A": {"B"},      # 여기서 {"B"}가 set의 형태이다.
                            "B": {"C", "D"}, # {"B" : {}}의 형태는 딕셔너리
                            "C": {"E"},      # 즉, 딕셔너리 안에 set이 있는 것이다.
                            "D": {"F", "G"},
                            "E": {"C"},
                            "F": {"C"},
                            "G": {"A", "F"}
                        }

정점(vertices)은 O(1) 상수 시간에 각 간선(edge)에 접근할 수 있다.
- edge가 set에 포함되어 있기 때문에 O(1) 상수 시간에 edge가 있는 지 확인할 수 있다.
- 예를 들어, A가 G set에 포함되어 있다는 뜻이다.

인접 행렬(Adjacency Matrix)

위 그림을 소스코드로 작성하기 전, 0과 1로 구성되는 행렬 부분(노드간 연결)이 어떤 부분인지 그림으로 그리면 아래와 같다.
- 행 노드와 연결되는 열 노드에 대해 1 값이 된다.

# 리스트로 구현한 인접행렬
# 아래 코드처럼 위의 간선 가중치는 1이다.

class Graph:
    def __init__(self):
        self.edges = [[0,1,0,0,0,0,0],
                      [0,0,1,1,0,0,0],
                      [0,0,0,0,1,0,0],
                      [0,0,0,0,0,1,1],
                      [0,0,1,0,0,0,0],
                      [0,0,1,0,0,0,0],
                      [1,0,0,0,0,1,0]]

위에서 행렬은 리스트 안에 리스트가 있는 2차원 배열로 표현된다.
- 구현을 통해 기본 제공되는 행렬 간에 간선 가중치(edge weights)를 알 수 있다.
- 0은 관계가 없음을 나타내지만 다른 값은 edge label 또는 edge weight을 나타낸다.
- 인접 행렬의 단점은 노드 값과 해당 인덱스 사이에 연관성이 없다는 것이다.
실제로 인접 리스트와 인접 행렬을 모두 구현하면 정점(Vertex) 및 간선 클래스를 포함하여 더 많은 정보를 파악할 수 있다.

그래프에서의 복잡도

인접 리스트는 리스트의 개념을 활용하고, 인접 행렬은 코드에서 볼 수 있듯이 배열의 개념을 활용한다.
- 인접 행렬의 특징은 구현이 쉽다는 것이다.
- 때문에 인접 행렬의 가장 큰 단점은 특정 노드에 방문한 노드들을 알기 위해서 모든 노드를 확인해야 한다는 점이다.(시간 복잡도 O(N))
- 이러한 단점을 위해 인접 리스트로 표현 방식이 생겼다.
인접 리스트는 실제 연결된 관계만을 저장해주기 때문에 실행 시간에 영향을 적게 준다.
- 인접 리스트의 단점은 특정 노드 간의 연결 관계를 확인하기 위해서는 반복문이 활용되어야 한다는 것이다.(O(N))

인접 리스트 구현

이 코드와 위 인접 리스트 코드의 차이점은 간선에 가중치를 부여할 수 있다는 것이다.

# 인접리스트 구현

class Graph:
    def __init__(self):
        self.vertices = {
                            "A": {"B": 1},          # 가중치 부여
                            "B": {"C": 3, "D": 2},  # 가중치 부여
                            "C": {},
                            "D": {},
                            "E": {"D": 1}           # 가중치 부여
                        }

인접 행렬 구현

행렬의 한 가지 이점은 간선 가중치를 표현하는 것이 쉽다.

# 인접행렬 구현

class Graph:
    def __init__(self):
        self.edges = [[0,1,0,0,0],
                      [0,0,3,2,0],
                      [0,0,0,0,0],
                      [0,0,0,0,0],
                      [0,0,0,1,0]]

순회(Traversal)

순회 기본 개념

순회는 그래프 또는 트리처럼 연결된 구조에서 노드를 한 번씩 탐색하는 개념이다.
순회의 주 목적은 모든 노드 또는 특정 노드를 방문하는 방법을 찾는 것이다.
BST(이진 검색 트리)와 다른 규칙이 적용되며 방향에 따라 탐색 방법이 달라질 수 있다.

그래프와 트리의 순회 구분

그래프의 순회는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 방법이 있다.
- 이 두가지는 탐색 알고리즘이다.
트리의 순회는 전위, 중위, 후위 순회이다.
- 그래프는 루트, 부모, 자식 노드 개념이 없지만 전위, 중위 후위 순회의 순회 개념을 활용하여 DFS, BFS를 구현할 수 있다.

전위 순회(preorder traverse): 루트를 먼저 방문
중위 순회(inorder traverse): 왼쪽 서브 트리를 방문 후 루트 방문
후위 순회(postorder traverse): 순서대로 서브 트리를 모두 방문 후 루트를 방문

위의 트리에 대해 순회를 구현할 것이다.
- 루트는 1개(10)이다.
- 부모 노드는 트리 별 1개씩이니 총 4개이다.(8, 1, 9, 12)

# 수도코드로 배우는 트리순회

# 먼저 순회를 진행하기 위해 트리형태의 노드들을 생성한다.
class node:

  # root -> left -> right 방향대로 노드 생성
  def __init__(self, value, left=None, right=None): 
    value  
    left    
    right  

root_node = node(10,
                 node(8, 
                      node(7),  
                      node(1, 
                           node(3), node(2)
                           )
                      ),
                 node(9, 
                      node(11), 
                      node(12, 
                           node(13)
                           )
                      )
                 )


# 전위 순회 
def pre_order(node):

  print(node.value)       # 루트노드
  pre_order(node.left)    # 왼쪽노드
  pre_order(node.right)   # 오른쪽노드


# 중위 순회
def in_order(node):

  in_order(node.left)    # 왼쪽노드
  print(node.value)      # 루트노드
  in_order(node.right)   # 오른쪽노드


# 후위 순회
def post_order(node):

  post_order(node.left)   # 왼쪽노드
  post_order(node.right)  # 오른쪽노드
  print(node.value)       # 루트노드

[자료구조] 그래프(Graph)란?

그래프(Graph)란?

그래프의 기본 컨셉

그래프와 트리의 특징

그래프의 유형

순환 및 비순환 그래프(Cyclic & Acyclic Graphs)

가중 그래프(Weighted Graphs)

DAGs(Directed Acyclic Graphs)

그래프의 활용

인접 리스트(Adjacency List)

인접 행렬(Adjacency Matrix)

그래프에서의 복잡도

인접 리스트 구현

인접 행렬 구현

순회(Traversal)

순회 기본 개념

그래프와 트리의 순회 구분

참조