Graph

Graph

What is graph?

• 그래프는 (Node, Edge)의 튜플로 표현되며 이때 Node를 Vertex라고도 함
  • Node: 노드
  • Edge: 연결
• Undirected graph: 노드들끼리 방향성이 존재하지 않는 그래프
  
• Directed graph: Edge끼리의 방향성이 존재하는 graph
  
• Tree: Graph의 특이 케이스 중 하나
  

Terminology

• Adjacent node: edge로 연결된 이웃 노드
• Path: node A에서 node B로 갈 때 지나가는 node들의 집합 (순서를 가짐)
• Complete graph: 어떤 node 쌍을 골라도 edge가 존재하는 graph
  • undirected일 경우 연결만 존재하면 됨
    • nC2개의 edge 존재 n * (n-1) / 2
  • Directed일 경우 양방향으로 존재
    • nP2개의 edge 존재 n * (n-1)
• Weighted graph: edge마다 weight 존재해서 중요도를 다르게 부여한 graph
  

Implementation: Adjacency Matrix

• 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• undirected graph에만 사용 가능
• Vertices: Vertex에 해당하는 index를 알려 주는 1차원 배열
• Adjacency Matrix: Vertex끼리의 edge 존재 유무와 weight를 알려 주는 2차원 배열
• Array Based이기 때문에 충분한 크기를 설정해 둬야 함
• Vertices의 index를 정렬해 놓으면 Searching 시간을 줄일 수 있음
  • Sorted인 경우 이진 탐색 O(logN), Unsorted인 경우 완전 탐색 O(N)


• edges[0][5]=800: vertices[0]인 Atlanta와 vertices[5]인 Houston 사이를 이어 주는 800이라는 weight를 가진 path 존재
• python 구현

  		 A
      / \
     B---C
  
     | A | B | C |
  ---|---|---|---|
   A | 0 | 1 | 1 |
  ---|---|---|---|
   B | 1 | 0 | 1 |
  ---|---|---|---|
   C | 1 | 1 | 0 |
  ---|---|---|---|

  INF = 999999999
  graph = [
  	[0, 7, 5],
  	[7, 0, INF],
  	[5, INF, 0]
  ]

  from QueType import *
  from StackType import *
  
  NULL_EDGE = 0
  
  def index_is(vertices, vertex):
      index = 0
  
      while index < len(vertices) and vertex != vertices[index]:
          index += 1
  
      if not index < len(vertices):
          return -1
      else:
          return index
  
  class GraphType:
      def __init__(self, maxV=50):
          self.numVertices = 0
          self.maxVertices = maxV
          self.vertices = [None] * maxV
          self.edges = [[NULL_EDGE] * maxV for _ in range(maxV)]
          self.marks = [None] * maxV
  
      def add_vertex(self, vertex):
          self.vertices[self.numVertices] = vertex
          for index in range(self.numVertices):
              self.edges[self.numVertices][index] = NULL_EDGE
              self.edges[index][self.numVertices] = NULL_EDGE
          self.numVertices += 1
  
      def add_edge(self, fromVertex, toVertex, weight):
          row = index_is(self.vertices, fromVertex)
          col = index_is(self.vertices, toVertex)
          self.edges[row][col] = weight
  
      def weight_is(self, fromVertex, toVertex):
          row = index_is(self.vertices, fromVertex)
          col = index_is(self.vertices, toVertex)
          return self.edges[row][col]
  
      def get_to_vertices(self, vertex, adjVertices):
          fromIndex = index_is(self.vertices, vertex)
          for toIndex in range(self.numVertices):
              if(self.edges[fromIndex][toIndex] != NULL_EDGE):
                  adjVertices.enqueue(self.vertices[toIndex])
  
      def clear_marks(self):
          for index in range(self.numVertices):
              self.marks[index] = False
  
      def is_marked(self, vertex):
          index = index_is(self.vertices, vertex)
          return self.marks[index]
  
      def mark_vertex(self, vertex):
          index = index_is(self.vertices, vertex)
          self.marks[index] = True
  
      def delete_edge(self, fromVertex, toVertex):
          row = index_is(self.vertices, fromVertex)
          col = index_is(self.vertices, toVertex)
          self.edges[row][col] = NULL_EDGE

Implementation: Adjacency List

• 리스트로 그래프의 연결 관계를 표현하는 방식
• undirected graph, directed graph 모두 적용 가능
• Vertices: Vertex에 해당하는 index를 알려 주는 1차원 배열
• Vertex list: Vertex 마다 edge로 연결된 다른 노드들을 Linked list로 표현
  • 해당 노드에서 뻗어나가는 edge만
  • adjacent node의 연결


• edges[0][5]=800: vertices[0]인 Atlanta에서 vertices[5]인 Houston까지 가는 데 800이라는 weight를 가진 path 존재
• python 구현

  		 A
      / \
     B---C
  
  A -> [B, C]
  B -> [A, C]
  C -> [A, B]

  graph = [[] for _ in range(3)]
  
  graph[0].append((1, 7))
  graph[0].append((2, 5))
  
  graph[1].append((0, 7))
  
  graph[2].append((0, 5))

Matrix VS List

• matrix
  • graph의 크기가 작은 경우에는 유용
  • 그래프의 크기가 매우 크면 연결이 없는 부분에 대한 matrix의 메모리 낭비가 발생할 수 있음
• list
  • 인접한 노드를 찾기 위해서는 각 노드의 인접 리스트를 순회해야 하기에 search 과정이 오래 걸릴 수 있음
  • 노드와 노드 사이 연결 여부를 확인할 때에도 리스트를 순회해야 해서 시간이 소요됨

Union

• 서로소 집합 (Disjoint Sets): 공통 원소가 없는 두 집합
• 서로소 집합 자료 구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료 구조
• 트리 자료 구조를 활용하여 서로소 집합 구현
• 단계
  • union 합집합 연산을 확인하여 서로 연결된 두 노드 a, b를 확인
    • a, b의 루트 노드인 a’, b’를 각각 찾음
  • 모든 union 연산을 처리할 때까지 1번 과정 반복
• 예시
  • 아래 연산은 1, 4와 2, 3과 2, 4와 5, 6이 같은 집합이라는 뜻
    
  • 더 큰 루트 노드가 더 작은 루트 노드를 가리키도록 설정해서 연결 표시
    
  • 이 과정을 반복하다가 4번 노드의 루트는 1번 노드이기 때문에 2번 노드도 1번 노드를 가리키도록 한다
    
• 서로소 집합의 자료 구조는 연결성을 통해 확인할 수 있음
  

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    # 더 작은 노드의 부모 노드 변경하기
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

• 경로 압축 기법

  • 위의 방법은 만약 노드가 일렬로 연결되어 있으면 부모의 부모의 부모 노드를 타고 가는 방식으로 비효율적

    
    

  • 경로 압축 기법을 통해 모든 노드의 부모 자리에 가장 최상위 부모를 두는 방식 채택 가능

    [https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F6pADO%2Fbtrb6TQ7hCI%2F3j8KnlaAzGaIXSK1xopTyk%2Fimg.png](https://img1.daumcdn.net/thumb/R1280x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F6pADO%2Fbtrb6TQ7hCI%2F3j8KnlaAzGaIXSK1xopTyk%2Fimg.png)

    # 특정 원소가 속한 집합을 찾기
    def find_parent(parent, x):
        # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
        if parent[x] != x:
            parent[x] = find_parent(parent, parent[x])
        return parent[x]

Cycle

• 서로소 집합을 통해 무방향 그래프 내에서의 사이클 판별이 가능
• 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복해 사이클 확인
• 단계
  • 각 간선을 확인하며 두 노드의 루트 노드 확인
    • 루트 노드가 서로 다르다면 두 노드에 대해 union 연산 수행
    • 루트 노드가 서로 같다면 사이클 발생
  • 그래프에 포함되어 있는 모든 간선에 대해 1번 과정 반복
• 예시
  • 모든 노드에 대해 자기 자신을 부모로 설정하는 형태로 부모 테이블 초기화
    
  • 간선 (1, 2)를 확인하고 루트 노드를 업데이트
    
  • 간선 (1, 3)을 확인하고 루트 노드를 업데이트
    
  • 간선 (2, 3)을 확인할 때 이미 루트 노드가 동일하다면 사이클 발생
    

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    # 더 작은 노드의 부모 노드 변경하기
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i
    
# 사이클 발생 유무
cycle = False

for i in range(e):
    a, b = map(int, input().split())
    # 사이클이 발생한 경우 종료
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    # 사이클이 아니라면 합집합 실행
    else:
        union_parent(parent, a, b)

Algorithm

Kruskal Algorithm

• 모든 노드를 연결하는 문제에 자주 사용
• 그리디 알고리즘으로 분류됨
• 신장 트리를 찾는 알고리즘
  • 신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
  • 최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘
• 단계
  • 간선 데이터를 비용에 따라 오름차순으로 정렬
  • 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
    • 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
    • 사이클이 발생하는 경우 최소 신장 트리에 포함하지 않음
• 다음 그래프의 최소 신장 트리 구하기
  • 간선 데이터를 비용에 따라 오름차순으로 정렬
    
  • 가장 짧은 간선을 선택 → (3, 4) 선택되고 이것을 집함에 포함 
    
  • 처리하지 않은 간선 중 가장 짧은 (4, 7) 선택 
    
  • 처리하지 않은 간선 중 가장 짧은 (4, 6) 선택 
    
  • 처리하지 않은 간선 중 가장 짧은 (6, 7) 선택 
    
  • 이 과정을 반복해서 최소 신장 트리를 구하고 이 간선의 비용을 다 더하기 
    

def find_parent(parent, x):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    # 더 작은 노드의 부모 노드 변경하기
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 간선 정보 입력받기
for i in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
    
# 간선을 비용 순서로 정렬
edges.sort()

# 간선을 하나씩 확인
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않을 때만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost

• 크루스칼 알고리즘의 시간 복잡도는 O(E logE) 시간 복잡돠를 가짐
  • 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분은 간선을 정리하는 작업이며, E개의 데이터를 정렬했을 때의 시간 복잡도이기 때문

Topology Sort

• 위상 정렬: 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
• 예를 들어 선수과목을 고려한 학습 순서 결정 같은 문제
• 그래프 상에 선후 관계가 있을 경우
• 진입차수: 특정한 노드로 들어오는 간선의 개수
• 진출차수: 특정한 노드에서 나가는 간선의 개수
• 단계
  • 진입차수가 0인 노드를 큐에 넣음
  • 큐가 빌 때까지 다음의 과정을 반복
    • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
    • 새롭게 진입 차수가 0이 된 노드 큐에 넣기
• 예시
  • 위상 정렬을 수행할 그래프인 사이클이 없는 방향 그래프 준비 
    
  • 진입차수가 0인 모든 노드를 큐에 넣음 → 1이 들어감 
    
  • 노드 1을 꺼낸 뒤에 노드 1에서 나가는 간선 제거하고 새롭게 진입 차수가 0이 된 노드 삽입
    
  • 노드 2 꺼낸 뒤 노드 2에서 나가는 간선 다 제거하고 새롭게 진입 차수가 0이 된 노드 삽입 
    
  • 이 과정을 반복하면 위상 정렬 결과 
    
• 위상 정렬의 시간 복잡도는 O(V + E)
  • 위상 정렬을 수행할 때 차례대로 모든 노드를 확인하면서 간선을 차례대로 제거해야 하기 때문

Practice

1로 만들기

• 문제
  • 학교에서 학생들에게 0번부터 N번까지의 번호를 부여
  • 처음에는 모든 학생이 서로 다른 팀으로 구분되어, 총 N + 1 개의 팀이 존재
  • 이때 선생님은 '팀 합치기'연산과 '같은 팀 여부 확인'연산을 사용
  • '팀 합치기' 연산은 두 팀을 합치는 연산
  • '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산
  • 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인'연산에 대한 연산 결과를 출력하는 프로그램을 작성
• 입력 조건
  • 첫째 줄에 N, M이 주어짐 M은 입력으로 주어지는 연산의 개수 (1 <= N, M <= 100,000)
  • 다음 M개의 줄에는 각각의 연산이 주어짐
  • '팀 합치기' 연산은 0 a b 형태로 주어짐 이는 a번 학생이 속한 팀과 b번 학생이 속한 팀을 합친다는 의미
  • '같은 팀 여부 확인' 연산은 1 a b 형태로 주어짐 이는 a번 학생과 b번 학생이 같은 팀에 속해 있는지를 확인하는 연산
  • a와 b는 N 이하의 양의 정수
• 출력 조건
  • '같은 팀 여부 확인'연산에 대하여 한 줄에 하나씩 YES 혹은 NO로 결과를 출력

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    # 더 작은 노드의 부모 노드 변경하기
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선의 개수 입력받기
n, m = map(int, input().split())
parent = [0] * (n + 1)

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, n + 1):
    parent[i] = i

for i in range(m):
    oper, a, b = map(int, input().split())
    # 합집합 연산인 경우
    if oper == 0:
        union_parent(parent, a, b)
    # 찾기 연산인 경우
    elif oper == 1:
        if find_parent(parent, a) == find_parent(parent, b):
            print("Yes")
        else:
            print("No")

도시 분할 계획

도시 분할 계획

커리큘럼

• 문제
  • 동빈이는 온라인으로 컴퓨터 공학 강의를 듣고 있음
  • 이 때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있음
  • 동빈이는 총 N개의 강의를 듣고자 함
  • 강의는 1번부터 N번까지의 번호를 가짐
  • 또한 동시에 여러 개의 강의를 들을 수 있다고 가정
  • 예를 들어, N = 3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 있고, 1번과 2번 강의는 선수 강의가 없다고 가정
  • 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정
  • 1번 강의: 30시간
    2번 강의: 20시간
    3번 강의: 40시간
  • 이 경우, 1번 강의를 수강하기까지의 최소 시간은 30시간, 2번 강의를 수강하기까지는 최소 20시간, 3번 강의를 수강하기까지는 최소 70시간이 필요
  • 동빈이가 듣고자 하는 N개의 강의 정보가 주어졌을 때, N개의 강의에 대하여 수강하기까지는 걸리는 최소 시간을 출력하는 프로그램을 작성
• 입력 조건
  • 첫째줄에 동빈이가 듣고자 하는 강의의 수 N(1 <= N <= 500)이 주어짐
  • 다음 N개의 줄에는 각 강의의 강의 시간과 그 강의를 듣기 위해 먼저 들어야 하는 강의들의 번호가 자연수로 주어지며, 각 자연수는 공백으로 구분
  • 이 때 강의 시간은 100,000 이하의 자연수
  • 각 강의 번호는 1부터 N까지로 구성되며, 각 줄은 -1로 끝남
• 출력 조건
  • N개의 강의에 대해 수강하기까지 걸리는 최소 시간을 한 줄에 하나씩 출력

from collections import deque
import copy

# 노드의 개수 입력받기
v = int(input())

# 모든 노드에 대한 진입차수 0으로 초기화
indegree = [0] * (v + 1)

# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v + 1)]

# 각 강의 시간을 0으로 초기화
time = [0] * (v + 1)

# 방향 그래프의 모든 간선 정보를 입력받기
for i in range(1, v + 1):
    data = list(map(int, input().split()))
    time[i] = data[0]
    for x in data[1:-1]:
        indegree[i] += 1
        graph[x].append(i)

# 위상 정렬 함수
def topology_sort():
    # 알고리즘 수행 결과를 담을 리스트
    result = copy.deepcopy(time)
    q = deque()

    # 처음 시작할 때 진입차수가 0인 노드 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        for i in graph[now]:
            result[i] = max(result[i], result[now] + time[i])
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in range(1, v + 1):
        print(result[i])

topology_sort()