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를 가리키도록 포인터를 바꾸어준다