Machine Learning Book Reviews Github

Graph

Graph

  • 구성요소

    • 정점 (Vertex)

    • 간선 (Edge)

  • |v|: 정점의 개수, |e|: 그래프에 포함된 간선의 개수

    • |v| 개의 정점을 갖는 그래프는 최대 |v| (|v|-1) /2 간선이 가능

      • ex) 5개 정점이 있는 그래픠의 최대 간선 수는 5*4/2 = 10 개이다

  • 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이하다.

그래프 유형

  • 무향 그래프 (Undirected Graph)

  • 유향 그래프 (Directed Graph)

  • 가중치 그래프 (Weighted Graph)

  • 사이클 없는 방향 그래프 (DAG: Directed Acyclic Graph)

    • 사이클

      : 시작 정점과 끝 정점이 같은 경로

      • ex)

        • 과정 이수 (선수 과목)

    • 단순 경로

      : 경로 중 한 정점을 최대한 한번만 지나는 경로

인접 정점

인접 (Adjacency)

  • 두 개의 정점에 간선이 존재 (연결됨) 하면, 서로 인접해 있다고 한다.

  • 완전 그래프에 속한 임의의 두 정점들은 모두 인접해있다

그래프 표현

간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

인접 행렬 (Adjacent matrix)

두 정점을 연결하는 간선의 유무를 행렬로 표현

  • |v| x |v| 크기의 2차원 배열을 이용해서 간선 정보를 저장

  • 배열의 배열

  • 행 번호와 열 번호는 그래프의 정점에 대응

  • 두 정점이 인접되어 있으면1, 그렇지 않으면 0으로 표현

  • 무향 그래프

    • i번째 행의 합 = i번째 열의 합 = Vi의 차수

  • 유향 그래프

    • 행 i의 합 = Vi의 진출 차수

    • 열 i의 합 = Vi의 진입 차수

  • 단점

    • 간선이 적더라도 (희소 그래프) V*V 크기의 공간 확보

    • 인접 정점을 찾을 때 인접 정점이 적더라도 V번 연산 필요

인접 리스트 (Adjacent List)

각 정점에 대한 인접 정점들을 순차적으로 표현

  • 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

간선의 배열

  • 간선 (시작 정점, 끝 정점)을 배열에 연속적으로 저장

그래프 순회 (탐색)

비선형구조인 Graph로 구현된 모든 자료 (정점)를 빠짐없이 탐색하는 것을 의미

  • 두 가지 방법

    • 깊이 우선 탐색 (DFS: Depth Fist Search)

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

DFS (깊이 우선 탐색)

  • 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,

    가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여

    결국 모든 정점을 방문하는 순회방법

  • 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 DFS를 반복해야 하므로 후입선출 (LIFO) 구조의 Stack 사용

Stack

  • 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

  • 선형 구조

    • 자료 간의 관계가 1:1의 관계를 갖는다

      • 비선형 구조는 1:N 관계 (트리)

  • 마지막에 삽입한 자료를 가장 먼저 꺼낸다

    • 후입 선출 (LIFO: Last In Fist Out)

BFS (Breadth First Search)

  • 탐색 시작점의 읹접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

  • 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 BFS를 진행해야 하므로 선입선출 (FIFO) 형태의 자료구조인 Queue를 활용함<

Queue

  • Stack과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조

    • Queue의 뒤에서는 삽입만, 앞에서는 삭제만 이루어지는 구조

  • Queue에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다

    • 선입선출 (FIFO: FIst In FIst Out)

  • 기본 연선

    • 삽입

      • enQueue

    • 삭제

      • deQueue

  • 공백상태 및 포화상태 검사:isEmpty(), isFull()

    • 공백상태

      • front =rear

    • 포화상태

      • rear = n-1 (n: 베열의 크기, n-1: 배열의 마지막 index)

상호배타/서로소 집합 (Disjoint-sets)

  • 서로소 or 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들을 말함

    • 교집합이 없다!

  • 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분

    • 이를 대표자(representative) 라고 한다!

  • 상호배타 집합을 표현하는 방법

    • 연결 리스트

    • 트리

  • 상호배타 집합 연산

    • Make-Set(x)

      • 원소 x를 유일한 원소로 하는 집합 생성

    • FInd-Set(x)

      • x가 포함된 집합의 대표자 리턴

    • Union(x,y)

      • x가 포함된 집합과 y가 포함된 집합을 합쳐줌

상호 배타 집합 표현 - 연결 리스트

  • 같은 집합의 원소들은 하나의 연결리스트로 관리

  • 연결리스트의 매 앞의 원소를 집합의 대표 원소로 삼는다

  • 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다

상호배타 집합 표현 - Tree

  • 하나의 집합(a disjoint set)을 하나의 tree로 표현한다

  • 자식 노드가 부모 노드를 가리키며, root node가 대표자가 된다

Union find 예제

"""
서로소 집합
N = 6
union(1,3)
union(2,3)
union(5,6)
print(p)
print(find_set(6))

결과
[0,2,2,1,4,5,5]
"""

def make_set(x):
    p[x] = x

def find_set(x):
    if p[x] == x:
        return x
    else:
        return find_set(p[x])

def union(x,y):
    # x의 대표자, y의 대표자를 찾음
    p[find_set(y)] = find_set(x)

N = 6

p = [0] * (N+1)

for i in range(1,N+1):
    make_set(i)


union(1,3)
union(2,3)
union(5,6)
print(p)
print(find_set(6))


# 문제점
# : 대표자를 찾기 위해 재귀호출 여러번 실행
#   -> 대표자를 바로 찾아가도록 건너 띄어 가야함
#      p[b] <- f

+

연산의 효율을 높이는 방법

  1. Rank 를 이용한 Union

    • 각 node는 자신을 root로 하는 subtree의 높이를 Rank 라는 이름으로 저장한다

    • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다

  2. Path compression

    • Find-Set을 행하는 과정에서 만나는 모든 node들이 직접 root를 가리키도록 포인터를 바꾸어준다

PreviousBacktrackingNextMinimum Spanning Tree

Last updated