그래프 나만의 정리

그래프

• 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현한다.
• 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조
• 선형자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기 용이하다

0. 목차

1. 그래프 유형
2. 그래프 표현
3. 그래프 순회
4. 서로소 집합

1. 그래프 유형

• 무향그래프(Undirected Graph)
  • 방향이 없는 그래프
• 유향 그래프(Directed Graph)
  • 방향이 있는 그래프
• 가중치 그래프(Weighted Graph)
  • 간선에다 가중치를 부여
• 사이클 없는 방향 그래프(DAG, Directed Acyclic Graph)
  • 시작과 끝점이 같은 단순 경로 그래프

2. 그래프 표현

• 인접행렬(Adjacent matrix)
  • v*v 크기의 2차원배열을 이용해서 간선 정보를 저장
• 인접 리스트(Adjacent List)
  • 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
• 간선의 배열

간선을 배열에 연속적으로 저장

(1) 인접행렬

• 두 정점을 연결하는 간선의 유무를 행렬로 표현
• 두 정점이 인접되어 있으면1, 그렇지 않으면 0으로 표현
• 단점은 시간복잡도가 높다.

(2) 인접리스트

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

3. 그래프 순회

• 그래프 순회는 비선형구조인 그래프로 표현된 모든자료(정점)들을 빠짐없이 탐색하는 것을 의미한다.
• 선형 구조일 경우 인접행렬이나, 인접리스트를 통해 탐색가능하지만, 비선형일경우 그래프의 모든 자료를 순회하기 위해 DFS, BFS를 활용한다.

(1) DFS(깊이우선탐색) -> 중요

• 시작 정점의 한 방향으로 갈 수 있는 경로까지 깊이 탐색하면서 더 이상 갈곳이 없을때, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향으로 탐색을 반복한다 ==> 결국 모든 정점을 방문하는 순회방법
• 후입선축 구조의 스택을 사용

(2) BFS(너비우선탐색) -> 중요

• 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 선입 선축구조(FIFO : First In First Out)의 큐를 활용함

4. 서로소 집합(Disjoint-sets)

• 서로소 또는 상호베타집합들을 설 중복 포함된 원소가 없는 집합들이다.
  • {1,2,3,4,5}, 중복이 없는 서로소 집합
  • {1,2,2,3,4,5}, 중복이 있으니 서로소 집합이 아니다.
• 집합에 속한 하나의 특정멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다.
• 상호배타집합을 표현하는 방법
  • 연결 리스트
  • 트리
• 상호배타 집합연산
  • Make-Set(x)
    • 원소 x를 유일한 원소로 하는 집합생성
• Find-Set(x)
  • x가 포함된 대표자를 리턴
• Union(x,y)
  • x가 포함된 집합과 y가 포함된 집합을 합쳐주는것

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

• 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
• 연결리시트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
• 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.

EX)

• Find-Set(e) return a => e가 포함된 집합의 대표는 a
• Find-Set(f) return b => f가 포함된 집합의 대표는 b
• Union(a, b) => U(f(e), f(f))

(2) 상호 배타 집합 표현 - 트리

• 하나의 집합을 하나의 트리로 표현한다
• 자식노드가 부모노드를 가리키면 루트노드가 대표자가 된다.

a, b, c 는 각각트리의 부모노드

(3) 상호배타 집합 슈도코드

# Make-Set : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
Make-Set(x)
    p[x] = x

# Find-Set(x) : x를 포함하는 집합의 대표자를 리턴
Find-Set(x)
    if x == p[x] : return x     
    else:    return Find_Set(p[x])

# Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산
Union(x, y)
    p[Find-Set(y)] = Find-Set(x)    # x가 속한 집합의 대표자를 y가 속한 집합의 대표자를 가리키게함

(4) 문제점

h의 대표를 찾아가는 과정에서 들리는 모든 노드들(e,d)은 h와 대표자가 같다.

그래서 그 노드를 골라내어 바로 대표자와 연결시켜준다

• 연산의 효율을 높이는 방
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크Rank라는 이름으로 저장한다.
    • 두 집합을 합칠때 Rank가 낮은 집합을 Rank가 높은 집합에 붙인다
• Path compression

# p[x] : 노드 x의 부모저장
# rank[x] : 루트 노드가 x인 트리의 랭크 값을 저장

# Make-Set : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
Make-Set(x)
    if p[x] = x
           rank[x] = 0

# Find-Set(x) : x를 포함하는 집합의 대표자를 리턴
Find-Set(x)
    if x != p[x]:
        p[x] = Find_Set(p[x]) # x의 대표자를 찾으면 그 값을 대표자로 갱신하는것     
    return p[x]

# Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산
Union(x, y)
    Link(Find-Set(x), Find-Set(y))
Link(x,y)
    if rank[x] > rank[y]
        p[y] =x
    else:
        p[x] = y
        if rank[x] == rank[y]
            rank[y] +=1