Data Structure_#13 Graph

Graph

:가장 복잡한(일반적인) 자료구조

• G=(V,E) v=vertex(정점) set, E= edge(에지) set

• degree(분지수): 어떤 노드에 연결된 에지 수

• 인접성

​ (1) adjacent: 에지(u, v)가 존재할 때 u, v는 인접(adjacent)

​ (2) incident: 에지 e=(u, v)에 대해, e는 u와 v에 인접(incident)

• 경로(path)

​ (1)단순 경로

​ (2)경로의 길이

• 사이클

​ (1) 트리 : 사이클이 없는 연결 그래프 (두 노드를 연결하는 경로가 무조건 1개)

​ (2) 포리스트: 연결 트리의 집합

• 방향그래프/무방향그래프

표현법

1. 인접행렬(adjacency matrix): (가중치를 직접 적음) 대각선은 0이나 1로 통일 =>메모리 낭비

​ => 2차원 행렬(배열)로

1. 인접리스트(adjacency list): 에지만 표현하는 것 =>인접행렬 보완

​ =>1차원 배열들로

기본연산시간

Sparse(에지수<노드수)  dense(에지수>노드수) ​							

그래프 순회

1. DFS(Depth First Search)

​ : 길이우선탐색

=> 현재 방문 노드에서 방문하지 않는 이웃 노드를 방문 & backtrack으로 다시 안 가본곳 방문

=> 그 과정을 통해 만들어진 트리가 DFS 트리

​ [비재귀적]

​ backdege 존재=사이클 존재

1. DAG(Directed Acyclic Graph)

​ -> 사이클이 없는 방향 그래프

Post가 가장 늦게 끝나는( 다 받아야하는) 것이 제일 나중으로 (post time이 가장 작은 것!)

​ => Post 역순으로(큰 것부터 나열)!

​ Ex) A, C, B, F, H, D, I, G

1. BFS( 너비우선)

​ => 같은 레벨기준으로 안 가본 곳 가기