[Data Structure] Graph

impala·2023년 1월 18일

BFS DFS Graph Spanning Tree data structure

Graph

정의

그래프는 정점(vertex)과 정점사이를 연결하는 간선(edge) 으로 구성된 한정된 자료구조를 의미한다. - wikipedia

개념

연결되어있는 객체간의 관계를 표현할 수 있는 자료구조
노드와 간선으로 이루어진 자료구조
용어
- vertex : node. 데이터가 저장되는 기본 원소
- edge : link. vertex간의 관계를 나타냄
- adjacent vertex : edge에 의해 연결된 정점
- simple path : 동일한 edge를 가지지 않은 경로
- degree : 무방향 그래프에서 한 vertex에 인접한 vertex의 수
- out-degree : 방향 그래프에서 외부에서 오는 edge의 수
- in-degree : 방향 그래프에서 외부로 나가는 edge의 수

종류

Undirected Graph : 무방향 그래프. 간선에 방향성이 없어 양방향으로 갈 수 있다
Directed Graph : 방향 그래프. 간선에 방향성이 존재하는 그래프
Weighted Graph : 가중치 그래프. 간선에 비용이나 가중치가 할당된 그래프(네트워크)
Complete Graph : 완전 그래프. 모든 정점이 서로 연결되어있는 그래프
- 무방향 완전 그래프의 간선의 수 = n * (n-1) / 2
Subgraph : 부분 그래프. 기존 그래프의 일부분
Connected Graph : 연결 그래프. 무방향 그래프에 있는 모든 정점 쌍에대해 항상 경로가 존재하는 경우
- Tree : 사이클을 가지지 않는 연결 그래프
Disconnected Graph : 비연결 그래프. 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
Cycle : 사이클. simple path의 시작점과 종점이 동일한 경우
Acyclic Graph : 비순환 그래프. 사이클이 없는 그래프

특징

네트워크 모델
2개 이상의 경로가 가능하다
self loop뿐만 아니라 loop/circuit모두 가능하다
루트노드, 부모-자식관계라는 개념이 없다

그래프 탐색

graph = {
    'A' : ['B'],
    'B' : ['A', 'C', 'H'],
    ...
}

BFS : 넓이 우선 탐색

정점을 기준으로 간선이 연결되어있는 모든 정점을 차례로 방문함

Queue를 사용하여 구현

from collections import deque

def bfs(graph, root):
    visited = []                        # 방문한 노드를 저장하는 리스트
    queue = deque([root])               # 처음으로 방문할 노드를 큐에 enqueue

    while queue:                        # 큐에 노드가 있으면
        n = queue.popleft()             # 큐의 맨 앞에 있는 노드를 dequeue
        if n not in visited:            # 노드를 아직 방문하지 않았다면 
            visited.append(n)           # 노드를 방문함
            queue.extend(graph[n])      # 방문한 노드와 연결된 노드들을 enqueue
    return visited

DFS : 깊이 우선 탐색

정점을 기준으로 간선이 연결되어 있는 정점 중 하나를 선택해 이동하고, 다시 이동한 정점을 기준으로 인접 정점을 선택

재귀함수나 Stack을 사용하여 구현

# 재귀함수 사용
def dfs(graph, start, visited=[]):
    visited.append(start)               # 노드를 방문

    for n in graph[start]:              # 방문한 노드와 연결된 노드에 대해
        if n not in visited:            # 방문하지 않은 노드가 있으면
            dfs(graph, n, visited)      # 그 노드를 출발노드로 하여 dfs호출
    
    return visited

# Stack 사용
from collections import deque

def dfs(graph, root):
    visited = []                        # 방문한 노드를 저장하는 리스트
    stack = deque([root])               # 처음으로 방문할 노드를 스택에 push

    while stack:                        # 스택에 노드가 있으면
        n = stack.pop()                 # 스택의 맨 위의 노드를 pop
        if n not in visited:            # 노드를 아직 방문하지 않았다면
            visited.append(n)           # 노드를 방문함
            stack.extend(graph[n])      # 방문한 노드와 연결된 노드들을 스택에 push

Spanning Tree

그래프 내 모든 정점이 연결되어 있으면서 사이클이 없는 트리
최소비용 신장트리(MST) 알고리즘 : Kruskal Algorithm, Prim Algorithm

구현

인접 리스트 표현

특정 정점에 인접한 정점을 쉽게 찾을 수 있다
그래프에 존재하는 모든 간선의 수는 O(V+E)에 알 수 있다.
낭비되는 메모리가 적다
두 정점이 연결되어있는지 확인하는 속도가 느리다

간선이 적은 희소 그래프 표현에 유리

graph2 = {'A' : ['B', 'C', 'D'],        #           B
        'B' : ['A', 'C'],               #         /   \
        'C' : ['A', 'B', 'D'],          #       A   -   C
        'D' : ['A', 'C']}               #         \   /
                                        #           D

인접 행렬 표현 : 2차원 배열에 두 정점의 연결정보를 저장
- 두 정점이 연결되어있는지 확인하는 속도가 빠르다(O(1))
- 정점의 차수를 O(V)안에 알 수 있다
- 그래프에 존재하는 모든 간선의 수는 O(V^2)에 알 수 있다
- 특정 정점에 인접한 정점을 찾기 위해서는 그래프 전체를 순회해야 한다
- 인접 리스트 표현보다 낭비되는 메모리가 크다
- 간선이 많은 밀집 그래프 표현에 유리
```
graph = [[0,1,1,1],     #       B
        [1,0,1,0],      #     /   \
        [1,1,0,1],      #   A   -   C
        [1,0,1,0]]      #     \   /
                        #       D
```