그래프, 트리

그래프

: 정점(vertex)과 간선(edge)의 집합으로 정의된 자료구조 G=(V,E)

( ) : 무방향 , <> : ->방향

degree(차수) : 정점에 연결된 간선의 수(방향그래프에서는 indegree,outdegree)

cycle

weight(가중치) : 간선에 할당되는 무게 

 

인접행렬(adjcent matrix) :  두 정점간의 간선 연결관계를 |v| * |v|크기의 행렬(배열)로 표현 +)구현간단 -)공간복잡도 v^2

인접리스트(adjcent list) : O(E)

인접행렬(간선여부) vs 인접리스트(해당 정점에서 나가는 간선의 목록)

 

DFS(스택 , 재귀함수사용) : 끝까지 가는 방식 BFS(큐,

 

※ 부분 그래프, 연결 요소, 강력 연결 요소, 트리, 신장 트리, 단절점, 이중 결합 그래프, 이중 결합 요소 ...