8. Graph

• 연결되어 있는 객체 간의 관계를 표현하는 비선형적 자료구조
• 정점(vertex) : 여러가지 특성을 가질 수 있는 객체
• 간선(edge) : 정점들간의 관계 의미

8.1. Undirected Graph(adjacency matrix)

• 무방향 그래프 (인접행렬)

8.2. Undirected Graph(adjacency list)

• 무방향 그래프 (인접리스트)

8.3. Directed Graph(adjacency list)

• 방향 그래프 (인접리스트)

8.4. MST(Minimum Spanning Tree)

1. 크루스칼(kruskal) 알고리즘
2. 프림(prim) 알고리즘

8.5. Shortest Path

1. 다익스트라(Dijkstra) 알고리즘
2. 벨먼-포드(Bellman-Ford) 알고리즘
3. 플로이드-워셜(Floyd-Warshall) 알고리즘

생각해보기

• 💬 순환/비순환 그래프란?

  순환 그래프 (Cyclic Graph)	비순환 그래프 (Acylic Graph)
  하나 이상의 노드에서 다시 자신까지의 경로를 포함하는 그래프	어떠한 노드에서도 다시 그 노드를 통과할 수 없는 그래프

• 💬 그래프와 트리의 비교

  • 트리 는 그래프 의 특수한 형태: 유방향 비순환 그래프 (DAG, Directed Acyclic Graph)
  
  

  그래프 (Graph)	트리 (Tree)
  네트워크 모델	계층 모델
  유방향 or 무방향	유방향
  순환 or 비순환	비순환
  루트/부모/자식노드 개념X	루트/부모/자식노드 개념O (자식노드는 단 하나의 부모노드를 가짐)
  간선 개수 제한 X	간선 개수는 항상 정점 수 - 1

• 💬 그래프 표현방법 비교

  • 그래프를 활용하여 수행하려는 연산의 종류에 따라 표현방법 결정
  
  

  구분	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
  정의	정점 간의 연결여부를 이차원 배열로 나타냄	각 정점을 오름차순으로 배열에 담고 해당 정점에 연결된 정점을 리스트로 나열함
  전체탐색	O(V²)	O(E)
  (i,j)탐색	O(1)	O(V)

• 💬 그래프의 순회방법 비교
  • 깊이우선탐색(DFS) 너비우선탐색(BFS)

• 💬 MST 알고리즘의 성능 비교 (어떤 상황에서 어떤 알고리즘이 좋을까?)
  • kuskal vs prim

• 💬 각각의 최단경로 알고리즘이 사용되는 경우는?
  • 단일 출발, 단일 도착, 단일 쌍, 전체 쌍 최단 경로
  • 음수 가중치, 음수 사이클