[자료구조 및 알고리즘] CH7. Graph

 

그래프란?

• finite set of vertex(V)와 edge(E)로 이루어진 것 - graph G : (V,E)

Edge(간선)란?

• 집합 E는 VxV의 subset이다.
• 일종의 relation이라 볼 수 있다.

directed graph(digraph) vs. undirected graph

• 그래프에서 방향성이 중요한지의 여부에 따라 구분

path란?

• 그래프에서 node의 sequence다. 단, 각 노드를 연결하는 edge가 있어야 함

Connected graph vs. Disconnected graph

• connected graph : 모든 노드 사이에 path가 존재(disconnected는 그 반대)
• disconnected graph는 여러 개의 connected component로 구성

그래프에서 cycle이란?

• 마지막 노드와 시작 노드가 같은 path
• cycle이 존재하면 그 그래프는 cyclic, 존재하지 않으면 acyclic이라 함

그래프 표현법(Graph representation) 두 가지

• Adjacency matrix 이용(인접행렬) : 그래프를 2차 행렬(A)로 표현
  • 장점 : 구현이 간단하고 두 노드가 연결되어있는지를 행렬 원소에 바로 접근해 알 수 있다.
  • 단점 : O(n^2)의 메모리 소모
• Adjacency list 이용(인접리스트) : 그래프를 linked list로 표현. 
  • 장점 : 메모리 절약
  • 단점 : 특정 노드가 연결되어있는지를 파악하기 위해 최대 O(n) 시간이 소요될 수 있다.

그래프의 degree

• 노드 x의 degree : x와 연결된 edge 갯수
  
  • indegree : x로 들어오는 edge 갯수
  • outdegree : x로부터 나가는 edge 갯수

Graph traversal(그래프 탐색)의 두 가지 방법 - 그래프를 탐색해 연결성(Connectivity) 조사

• DFS - 재귀 또는 스택으로 구현
• BFS - 큐로 구현

DFS, BFS 실습

• DFS

m.blog.naver.com/ndb796/221230945092

16. 깊이 우선 탐색(DFS)

• BFS

m.blog.naver.com/ndb796/221230944971

15. 너비 우선 탐색(BFS)