그래프 & 백트래킹

그래프

그래프 기본

• 그래프는 아이템들과 이들 사이의 연결 관계를 표현한다
• 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 구조
  • V : 정점의 개수, E : 그래프에 포함된 간선의 개수
  • V 개의 정점을 가지는 그래프는 최대 V / 2 간선이 가능
• 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이하다

그래프 유형

• 무향 그래프(Undirected Graph)
• 유향 그래프(Directed Graph)
• 가중치 그래프(Weight Graph)
• 사이클 없는 방향 그래프(DAG)
• 완전 그래프
  • 정점들에 대해 가능한 모든 간선들을 가진 그래프
• 부분 그래프
  • 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프
• 인접
  • 두 개의 정점에 간선이 존재하면 서로 인접해 있다고 한다.
  • 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다

그래프 경로

• 경로란 간선들을 순서대로 나열한 것
  • 간선들 : (0,2), (2,4), (4,6)
  • 정점들 : 0 - 2 - 4 - 6
• 경로 중 한 정점을 최대한 한번만 지나는 경로를 단순경로라 한다
• 시작한 정점에서 끝나는 경로를 사이클이라고 한다

그래프의 표현

• 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정
• 인접행렬
  • V * V 크기의 2차원 배열을 이용해서 간선 정보를 저장
  • 배열의 배열
• 인접리스트
  • 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
• 간선의 배열
  • 간선을 배열에 연속적으로 저장

인접행렬

• V * V로 정방행렬 표현
  갈수 없다면 0, 있다면 1로 저장
• 장점
  • 노드간의 연결정보를 한방에 확인가능
  • 간선이 많을 수록 유리
  • 행렬곱을 이용해서 탐색이 쉽게 가능하다
• 단점
  • 노드 수가 커지면 메모리가 낭비된다
  • 연결이 안된 것도 저장
• 특징
  • 양방향 그래프는 중앙 우하단 대각선 기준으로 대칭

인접리스트

• 각 정점에 대한 인접 정점들을 순차적으로 표현
• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장
• V 개의 노드가 갈 수 있는 정보만 저장
• 장점
  • 메모리 사용량이 적다
  • 탐색할 때 갈 수 있는 곳만 확인하기 때문에 시간적으로 효율
• 단점
  • 특정 노드 간 연결 여부를 확인하는데 시간이 걸린다

그래프 순회

• 그래프 순회는 비선형 구조인 그래프로 표현된 모든 자료를 빠짐없이 탐색하는 것을 의미한다.

DFS

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

def Dfs(start_v):
    stack = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in stack:
            stack.append(v)
            for w in graph_list[v]:
                stack.append(w)
    return stack

BFS

• 너비 우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색 한후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출형태의 자료구조인 큐를 활용함

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

Union-Find(Disjoint set)

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.
• 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.
• 배타 집합을 표현하는 방법
  • 연결 리스트
  • 트리
• 상호배타 집합 연산
  • Make - Set(x)
  • Find - Set(x)
  • Union(x,y)
• 연결리스트
  • 같은 집합의 원소들은 하나의 연결리스트로 관리한다
  • 연결 리스트의 맨 앞의 원소를 집합의 대표 원소르 삼는다
  • 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다
• 트리
  • 하나의 집합을 하나의 트로리 표현한다
  • 자식노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다
• Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
• Find_SEt(x) : x를 포함하는 집합을 찾는 연산
• Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산

• 연산의 효율을 높이는 방법
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank라는 이름으로 저장한다
    • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 낮은 집합을 rank가 높은 집합에 붙인다
  • Path compression
    • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다