그래프 이론

그래프

• 데이터(노드)들을 잘 정리하는(노드간의 관계를) 방법 중 하나
• 데이터들과 그 관계를 보여주는 방법 중 하나
• 서로 연관 있는 노드의 집합
• G = (N, E)
• 네트워크 형태의 관계를 보여주기에 적합

용어

• 노드(정점, 꼭짓점)
• 변(간선, 선)
• 차수(degree) : 나한테 몇개 연결되어 있나
• 루프(loop): 자기자신한테 돌아오는것

그래프의 종류

• 방향/무방향(directed/undirected) 그래프
• 순환/비순환(cyclic/acyclic) 그래프
• 가중/비가중(weighted/unweighted) 그래프

무방향 그래프의 최대 변 개수

• 모든 노드가 연결되어 있는 경우

그래프의 표현 방법

1. 인접 행렬
   • N * N 행렬
     • G[N][N]
     • N: 그래프 G안에 있는 노드수
   • 서로 인접한 노드를 표현
     • i → j로 향하는 변이 있다: G[i][j] = 1
   • G가 가중 그래프라면 실제 가중치 저장
   • 관계 찾는거 O(1)
   • 단점
     • 메모리를 많이 차지함.
2. 인접 리스트

• 각 노드마다 이웃의 리스트를 만듦
• 리스트 N 개
• 장점: 공간 적게 사용
  • O(N + E)
  • 최악 O(N제곱)
  • 삽입/삭제가 빠름.
• 단점:
  • O(1)보다 관계찾는것이 느림.

---

DFS(Depth-first Search, 깊이 우선 탐색)

• 트리에서의 DFS와 달리 그냥 탐색을 해버리면 무한 루프 생성 가능
• 따라서 방문했던 노드를 기억해야 한다.
• 그래프 DFS의 시간 복잡도: O(N + 2E) == O(N + E)
  • 각 노드는 최대 한 번 처리됨 → O(N)
  • 각 변은 최대 두 번 고려됨 → O(2E)

def DFS(node):
    stack = []

    stack.push(node)

    while stack:
        current = stack.pop()

        if visited[current] == True:
            continue
        visited[current] = True

        print(node)

        for e in edge[node]:
            stack.append(e)

BFS(Breadth-First Search, 너비 우선 탐색)

• 마찬가지로 트리에서처럼 탐색 해버리면 무한 루프 생성
• 방문했던 노드 기억
• 시간복잡도: O(N + E)

def BFS(node):
    queue = deque()

    queue.push(node)

    while queue:
        current = queue.popleft()

        if visited[current] == True:
            continue
        visited[current] = True

        print(node)

        for e in edge[node]:
            queue.append(e)

---

MST(최소 신장 트리, Minimum Spanning Tree)

• 광케이블 깔기 문제 예시

• 노드: 아파트 빌딩
• 변 : 광선을 깔 수 있는 경로
• 변의 가중치: 거리 = 설비 가격
• 목표 : 모든 노드를 연결하는 변 찾기, but 비용은 최소

신장 트리(Spanning Tree)

• 어떤 그래프 안에 있는 모든 노드를 연결하는 트리
• 여러 개 있을 수 있음.

MST 알고리즘 개념

• 순환(cycle) : 시작노드와 끝노드가 같은 것

• 컷(cut) : 어떤 그래프를 서로소(disjoint)인 두 하위 조합으로 나누는 행위
• 두 그래프를 두 그룹으로 분리
• 컷-세트(cut-set) : 두 그룹을 연결하는 변들의 집합

• 컷 세트에 가중치가 다른 여러 그래프가 있다면 MST에 포함되는 것은 가장 가중치가 작은 변
• 알고리즘 순서

1. 그래프에 있는 노드 중 한 변 확인
2. 이 변에 MST에 들어가야 하는 지 검사
   1. 이 때 cut property 사용
   2. 들어가야 하면 MST에 추가, 아니면 무시
3. MST 의 모든 변을 찾지 못했다면 1로 돌아감

어떤 알고리즘과 비슷한가?

크루스칼 알고리즘

1. 그래프의 각 노드마다 그 노드만 포함하는 트리 만듦
2. 모든 변을 가중치의 오름차순으로 정렬 → S배열
3. S가 비거나 MST가 완성될 때까지 다음 과정을 반복
   1. S에서 가중치가 가장 적은 변을 제거해서 고려
   2. 이변이 두 트리를 연결하는지 검사
      1. 그렇다면 MST에 추가
      2. 아니라면 버림
         1. 1. 1. 1. 1. 1. 1. 1. 1.