전공과목 정리/자료구조

[자료구조💾] 9장 그래프

최연재 2024. 1. 23. 09:40

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

9.1 그래프의 개념

1) 오일러 회로 (Eulerian circuit)

- 모든 간선을 한 번씩만 이용해 출발 위치로 돌아온다.

- 각 정점의 차수가 짝수여야 한다.

 

2) 오일러 경로 (Eulerian trail)

- 모든 정점을 한 번씩만 방문하고 출발 위치오 종착 위치가 다르다.

- 출발점과 종착점을 제외한 정점의 개수가 짝수여야 한다.

 

3) 그래프

- 통신망이나 도로망의 관리, 최단거리 경로 탐색,소셜 네트워크 분석 등 다양한 분야에 활용된다.

- 그래프로 해결 가능한 통신망 문제의 예

  • 네트워크의 연결성 확인
  • 네트워크에서 컴포넌트 탐색
  • 연결 네트워크를 유지하는 데 필요한 최소 간선 수

 

 

9.2 그래프의 용어

1) 정점과 간선

- 정점(vertex)의 집합(V)과 간선(edge)의 집합(E)으로 구성된다.

- 정점은 노드(node), 간선은 아크(arc)라고도 부른다.

- 정점 집합(V)은 유한 개수의 정점으로 구성되고, 간선 집합은 (tail, head)의 쌍으로 된 간선들의 집합.

- 무방향 그래프(undirected graph) : 간선에 방향성이 없다. 간선을 ( )로 표시한다.

- 방향 그래프(directed graph) : 간선에 방향성이 있다. 간선을 < >으로 표시한다.

- 한 정점에서 출발하여 자기 자신으로 되돌아온다.

  • 순환 루프 간선(self-loop edge)
  • 다중 간선(multiple occurrece edge)

 

2) 완전 그래프

- 각 정점을연결하는 간선이 모두 존재하는 그래프

- 정점의 수가 n개일 때 무방향 그래프의 최대 간선 수는 n * (n - 1) / 2이다.

- 정점의 수가 n개일 때 방향 그래프의 최대 간선 수는 n * (n - 1)이다.

 

3) 인접성

- 간선 (v1, v2)가 그래프 G의 간선일 때, 정점 v1, v2는서로 인접하다.

- 간선 (v1, v2)는 노드 v1, v2에 부속(incident)된다.

 

4) 서브 그래프 (sub-graph)

- 그래프 G의 서브 그래프 G1은 정점 집합과 간선 집합에 대해 다음의 관계를 만족한다.

V(G1) ⊆ V(G) and E(G1) ⊆ E(G)

 

5) 경로 (path)

- 그래프 G의 정점 v1에서 정점 vn에 이르는 정점들의 나열(sequence)

- 그래프 G의 경로 (v1, v2, ... , vn)가 존재하기 때문에 이 그래프 내에는 간선 (v1, v2), (v2, v3), ... , (vn-1, vn)이 존재해야 한다.

- 단순 경로 (simple path) : 경로 상의 첫 노드와 마지막 노드를 제외하고 모든 노드가 유일한(중복되지 않는) 경로

- 순환 경로 (cycle path) : 출발 정점과 도착 정점이 같은 단순 경로

- 경로의 길이(length) : 경로에 존재하는 간선의 수

 

6) 연결 그래프 (connected graph)

-  그래프에서 모든 정점의 순서쌍(vi, vj)간에 도달할 수 있는 경로가 존재한다.

 

7) 컴포넌트 (component)

- 더 이상의 정점을 추가할 수 없는 연결된 서브 그래프

 

8) 사이클(cycle) 과 연결성(connectivity)

- 사이클 : 순환 경로를 형성하는 것

- 사이클을 포함하는 간선 중 일부를 제거해도 연결성에 영향을 주지 않는다.

- 통신망에서 사이클은 중복된 비용을 의미하므로 발견 시 제거하는 것이 효율적이다.

 

9) 트리 (tree)

- 사이클이 없는 연결 그래프(connected and acyclic graph)

- 정점의 수가 n개일 때 n-1개의 간선만을 포함해야 한다.

 

10) 신장 트리 (spanning tree)

- 최초 그래프(original graph)의 모든 정점을 포함하고 트리의 조건을 만족하는 서브 그래프

- 그래프에 n개의 정점이 있었다면 신장 트리는 n개의 정점과 n-1개의 간선을 포함해야 한다.

- 네트워크(network) 또는 가중치 그래프 : 간선에 가중치(weight)가 부여된 그래프

- 최소 비용 신장 트리(minimum cost spanning tree) : 네트워크에서 간선의 가중치 합이 최소인 신장트리

 

 

9.3 그래프의 표현

1) 무방향 그래프의 정점 차수

- 정점의 차수(vertex degree) : 정점에 연결된 간선의 수

- 무방향 그래프는 간선의 방향성이 없으므로 연결된 간선의 개수만으로 차수를 계산한다.

- 무방향 그래프(G)에 n개의 정점과 e개의 간선이 존재할 때, 전체 정점의 차수 합은 2e이다. 

 

2) 무방향 그래프의 인접 행렬 (adjacency matrix)

- 그래프를 자료구조로 표현하기위해서는 인접 행렬 또는 인접 리스트를 사용한다.

- 무방향 그래프(G)의 인접 행렬(A) : 인접 행렬의 원소 A[i][j]는 두 정점 (i, j)간에 간선이 존재하면 1을, 그렇지 않으면 0의 값을 갖는다.

- 인접 행렬의 원소들은 상하 대칭(symmetric)이다.

- 인접 행렬의 유효한 원소를 위한 최소 저장공간 : (n-1)*n/2

- 무방향 그래프의 인접 행렬을 저장하는데 필요한 공간 복잡도 : O(n2)

 

3) 방향 그래프의 정점 차수

- 방향 그래프에서 정점 차수는 무방향 그래프와 다르게 간선의 방향에 따라 진입 차수(in-degree), 진출 차수(out-degree)로 구분한다.

  • 정점의 진입 차수 : 해당 정점으로 들어오는 간선(inbound edge)의 수 
  • 정점의 진출 차수 : 해당 정점에서 다른 정점으로 향하는 간선(outbound edge)의 수

- 일반적인 방향 그래프의 인접 행렬은 진출 차수를 기준으로 작성한다.

- 두 정점 i, j간에 간선 <i, j>가 존재하면, 인접 행렬의 원소 A[i][j]에 1을 저장하고 그렇지 않으면 0을 저장한다.

- 전체 그래프의 인접성을 위한 시간 복잡도 : O(n2)

 

4) 인접 리스트 (adjaceny list)

- 그래프의 각 정에 인접한 정점들을 연결 리스트의 노드로 저장한 구조

- 그래프에는 정점의 수만큼 인접 리스트가 필요하다.

- 정점 i를 위한 연결 리스트에 존재하는 노드의 수가 이 정점의 차수가 된다.

class Node:
  def __init__(self, value):
    self.data = value

class Graph:
  def __init__(self):
    self.graph = []
  
  def create(self, v, data):
    node = Node(v)
    if data not in self.graph:
      self.graph[data] = []
    self.graph[data].append(node)

  def show(self):
    temp = []
    for no, alist in self.graph.items():
      temp.append((no, alist))
    temp.sort()
    for no, alist in temp:
      print("[", no, "]", end=' ')
      for node in alist:
        print(node.data, end = ' ')
      print()

 

5) 역 인접 리스트 (inverse adjacency list)

- 진입 간선(inbound edge)을 기준으로 만들어진 인접 리스트

 

6) 네트워크 (network)

- 간선에 가중치(weight)가 부여된 그래프

- 인접 행렬로 표현할 때 인접성 값 대신에 간선의 가중치를 저장하면 효과적이다. 

 

9.4 그래프의 탐색

1) 깊이 우선 탐색 (DFS; Depth First Search)

- 인접 노드에 연결된 또 다른 인접 노드를 먼저 탐색한 후 특정 노드에 인접한 노드들을 탐색한다.

- 루트에서 단말 노드 방향으로 계속해서 탐색해나간다.

- 재귀 호출로 쉽게 구현할 수 있다.

- 시간 복잡도 (n : 정점의 수, e : 간선의 수)

  • 인접행렬 : O(n2)
  • 인접리스트 : O(n+e)

- 알고리즘

  1. 시작 노드에 대해 dfs 탐색을 수행한다.
  2. 주어진 노드의 인접 리스트에서 미방문 노드를발견하면 해당 노드로 분기하여 dfs 탐색을 수행한다.
  3. 특정 노드의 인접 리스트에 더 이상 방문할 노드가 없으면 호출한 이전 노드로 되돌아간다.
def dfs(v):
  visit.append(v) 
  for node in graph[v]:
    if node.data not in visit:
      dfs(node.data)

 

2) 그래프 연결성 탐색

- 시작 노드(V)에서 DFS 탐색을 시작하여 정점(U)에 도달하면 탐색을 종료한다고 가정 

  • 정점(U)에 도달하기 전에 DFS 탐색이 종료되었다면 정점(V)와 정점(U) 사이에 경로가 존재하지 않는다.

- 특정 노드에서 DFS 탐색을 시작해 그래프의 전체노드를 방문할 수 있으면 연결 그래프이다.

- DFS 신장 트리 (DFS spaning tree) : 그래프를 DFS 방법으로 방문할 때 사용한 간선만으로 이루어진 서브 그래프

 

3) 너비 우선 탐색 (BFS; Breadth Frist Search)

- 그래프에서 특정 노드의 인접 노드를우선적으로 방문하는 방법

- 트리의 레벨 탐색(level-order)과 유사

- 큐를 이용해 구현한다.

- 시간 복잡도 (n : 정점의 수, e : 간선의 수)

  • 인접행렬 : O(n2)
  • 인접리스트 : O(n+e)
def bfs(v):
  visit.append(v)
  for node in graph[v]:
    if node.data not in visit:
      bfs(node.data)

 

 

9.5 최소 비용 신장 트리

1) 최소 비용 신장 트리 (minimun cost spanning tree)

- 신장 트리 (spanning tree) : 사이클이 없는 연결 그래프  

- 최소 비용 신장 트리 : 간선의 합이 최소가 되는 신장 트리

- 간선 제거에 의한 방법

  • 그래프에서 사이클에 속한 간선 중 연결성에 영향을 주지 않으면서도 비용이 최고인 간선을 제거한다.
  • 그래프에 사이클이 존재하지 않을 때까지 위 과정을 반복한다.

- 간선 선택에 의한 방법

  • 간선을하나씩선택해최소 신장 트리를 찾는다.
  • 네트워크의 정점만을 포함한 상태에서 시작한다.
  • 간선 비용을 오름차순으로 정렬한 후 최소 비용 간선부터 사이클을 형성하지 않는 것은 하나씩 추가해나간다.
  • 사이클을 유발하는간선을 제외하고 n-1개의 간선이 추가되면 종료한다.
  • 간선 선택을 통한 최소 비용 신장 트리 탐색 방법
    • 크루스칼(Kruskal)의 방법
    • 프림(Prim)의 방법
    • 솔린(Sollin)의 방법

 

2) 크루스칼의 방법

  1. 네트워크의 간선 없이 정점만으로 이루어진 포리스트(foreset)에서 시작한다.
  2. 간선 비용을 오름차순으로 정렬하여 최소 비용 간선부터 검토한다.
  3. 기존 트리에 사이클을 형성하는 간선을 제외하고, 그렇지 않은 경우에는 추가한다.
  4. n-1개의 간선이 포함되면 종료한다.
class Node:
  def __init__(self, value):
    self.data = value

class Graph:
  def __init__(self):
    self.graph = {}
    self.v_list = {}
    self.edge = []
    self.total = 0

  def create(self, v, data, weight):
    node = Node(data)
    if v not in self.graph:
      self.graph = []
    self.graph[v].append((node, weight))

  def sort_edge(self, network):
    temp = []
    for v1, v2, cost in network:
      temp.append((cost, v1, v2))
    temp.sort()
    return temp
  
  def find(self,v2):
    for v1, lst in self.v_list.items():
      if v2 == v1:
        return v1
      if v2 in self.v_list[v1]:
        return v1
    return -1
  
  def union(self, s1, s2):
    if s1 < s2:
      self.v_list[s1].append(s2)
      self.v_list[s1].extend(self.v_list[s2])
      del self.v_list[s2]
    else:
      self.v_list[s2].append(s1)
      self.v_list[s2].extend(self.v_list[s1])
      del self.v_list[s1]

  def kruskal(self):
    for v1, v2,cost in network:
      if v1 not in self.v_list:
        self.v_list[v1] = []
      if v2 not in self.v_list:
        self.v_list[v2] = []
    print('set list = ', self.v_list)
    sort_network = self.sort_edge(network)

    print('cost sorted (cost, v1, v2)', sort_network)
    for cost, v1 , v2 in sort_network:
      print('(', v1, ', ', v2 , ') cost =', cost)
      s1 = self.find(v1)
      s2 = self.find(v2)
      print('v1 set: ', s1, ', v2 set: ', s2)
      if s1 == s2:
        print("The same set. Rejected for cycle")
        continue
      self.edge.append((v1, v2, cost))
      self.total += cost
      self.union(s1, s2)
      print(self.v_list)

 

3) 프림의 방법

  1. 주어진 그래프의 모든 정점만을 포함한다.
  2. 시작 정점에 인접한 간선 중 최소 비용 간선을 선택하여 검토한다.
  3. 사이클을 형성하지 않으면 추가하고 그렇지 않으면 제외한다.
  4. n-1개의 간선이 포함되면 종료한다.
  5. 새로운 트리에서 최소 비용 간선을 선택하여 3번 과정을 반복한다.

 

4) 솔린의 방법

  1. 그래프의 간선을 제외하고 n개의 정점(n개의 트리)에서 시작한다.
  2. 각 트리에서 최소 비용 간선을 각각 선택하여 포함 여부를 검토한다.
  3. 중복 선택된 간선은 1회만 포함하고 사이클 생성 간선은제외한다. n-1개의 간선이 포함되면 종료한다.
  4. 간선이 추가된 새로운 트리를 기준으로 2번 과정부터 반복한다. 

'전공과목 정리 > 자료구조' 카테고리의 다른 글

[자료구조💾] 11장 탐색과 해싱  (4) 2024.01.25
[자료구조💾] 10장 최단 경로와 작업 네트워크  (0) 2024.01.24
[자료구조💾] 8장 정렬  (4) 2024.01.21
[자료구조💾] 7장 최대 힙  (0) 2024.01.20
[자료구조💾] 6장 이진 트리  (0) 2024.01.18

'전공과목 정리/자료구조'의 다른글

  • 현재글[자료구조💾] 9장 그래프

관련글

티스토리툴바