그래프는 정점(vertex)와 간선(edge)로 구성된 한정된 자료구조를 의미한다. 자료 구조는 그래프 그조와 그래프 관리에 사용되는 알고리즘에 영향을 받는다.
<aside> 💡 그래프는 리스트와 행렬 구조 중의 하나로 구별 가능하다. 하지만 실제 적용에 있어서 최적의 자료 구조는 이 두 구조의 조합된 형태를 띤다고 한다.
</aside>
무방향 그래프(Undirected Graph)
무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다. 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다. (A, B)는 (B, A) 동일하다.
Ex) 양방향 통행 도로
방향 그래프(Directed Graph)
간선에 방향성이 존재하는 그래프 A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B>는 <B, A>는 다르다.
Ex) 일방 통행
가중치 그래프
간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’ 라고도 한다.
Ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등
연결 그래프(Connected Graph)
무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우이다.
Ex) 트리(Tree): 사이클을 가지지 않는 연결 그래프
비연결 그래프(Disconnected Graph)
무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우이다.
사이클(Cycle)
단순 경로(Simple Path;경로 중에서 반복되는 정점이 없는 경우)의 시작 정점과 종료 정점이 동일한 경우이다.
비순환 사이클(Acyclic Graph)
사이클이 없는 그래프이다.
완전 그래프(Complete Graph)
그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프이다. 무방향 완전 그래프의 정점 수가 n 이면 간선의 수는 n * (n-1) /2 이다.