출처: 쉽게배우는 알고리즘(한빛미디어), C++ 자료구조론(인피니티북스)

Graph

정점(V)와 간선(E)로 이루어진 집합 : $G = (V,E)$

용어

• 무향그래프(양방향) vs 유향그래프
• 가중치 그래프 : 엣지에 가중치가 존재
• 완전그래프 : 모든 정점을 연결한 그래프
• 다중그래프 : multiple edge인 그래프 ( A → B 사이 간선이 2개 이상)
• 경로 : A → B
• 사이클 : A → A (자기자신으로 다시돌아오는)
• 차수 : 정점과 연결된 간선의 수
• 부분그래프 : 원 그래프에 속한 노드와 간선으로 구성된 그래프
• 연결요소 : 원 그래프에 속한 나누어진 각각의 그래프
• 이분그래프 : A에 포함된 정점끼리 연결된 간선이 없고 B그룹도 마찬가지 성질을 가지는 두 그룹 A,B로 나누어지는 그래프

참고) 트리 vs. 그래프
트리는 그래프에 속함(cycle이 존재하지 않고, level이 존재함)

그래프의 표현

• 인접행렬 : NxN배열, 정점i와 j가 연결되있음을 A[i][j]에 표시
  $O(V^{2})$, 밀도가 높은 경우에 사용

• 인접리스트 : 연결리스트, A[i] = i에 연결된 정점 리스트
  $O(E)$, 간선의 수가 적은 경우에 사용

• 간선리스트 : 배열이용, 간선들을 저장
  i번정점과 연결된 간선 = 간선배열에서 cnt[i-1] ~ cnt[i]-1 범위