[자료구조와 알고리즘] Graph

그래프 ( Graph ) 란?

- 노드 간에 연결될 수 있다는 점을 제외하고는 트리와 비슷하며, 루프를 형성할 수도 있음

- 트리에서는 노드를 탐색하는 경우 제한이 있지만, 그래프는 루프형성이 가능하기 때문에 다른 범위의 개념으로 필요한 자료구조

- 그래프는 기본적으로 Vert ( 노드 또는 정점 ) 와 Edge ( 간선 ) 으로 연결되어 있음

▶ 그래프의 유형

- 그래프의 특성은 방향성 ( Directed ) 또는 무방향성 ( Undirected ) 그래프가 있음

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

- 순환 ( 루프 ) 을 형성할 수 있는 경우 그래프는 순환 그래프임

- 무방향성 ( Undirected ) 그래프는 항상 동일한 노드에 재방문할 수 있으므로 순환 그래프임

- 순환을 형성할 수 없는 경우 비순환 그래프라고 함

■ 가중 그래프 ( Weighted Graphs ) 

- 각 edge의 가중치에 할당된 특정값을 호출함

- 가중치는 서로 다른 그래프에서 서로 다른 데이터를 나타냄

- 그래프에서 경로의 총 가중치가 높을수록 경로이동시간 ( 비용 ) 이 길어짐

■ Directed Acyclic Graphs ( DAGs )

- 방향성 비순환 그래프 ( DAG ) 는 순환되지 않고 특정한 단방향 그래프

- Edge가 순서대로 향하도록 DAG의 노드를 선형 ( 단방향 ) 으로 정렬할 수 있음 

▶ 그래프의 활용

- 그래프를 나타내는 두 가지 방법은 인접리스트 ( Adjacency Lists )과 인접행렬 ( Adjancency Matrices )

■ 인접리스트 ( Adjacency List )

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

- 인접리스트의 단점은 특정 노드간의 연결관계를 확인하기 위해서는 반복문이 활용되어야 하면 O(N) 이상의 시간복잡도가 될 것임

# 인접리스트 구현

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

■ 인접행렬( Adjacency Matrix )

- 인접 행렬은 리스트 안에 리스트가 있는 2차원 배열로 표현

• 0은 관계가 없음을 나타내고 다른 값은 Edge Label 또는 Edge Weight를 나타냄
• 인접행렬의 단점은 노드 값과 해당 인덱스 사이에 연관성이 없다

- 인접행렬의 특징은 구현이 쉽다

# 인접행렬 구현

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 ) : 순서대로 서브트리 ( 왼쪽 -> 오른쪽 ) 를 모두 방문 후 루트를 방문