12. 그래프 ADT (Graph ADT)
2020.11.11
그래프 ADT는 정점vertex의 집합 $V$와 간선edge의 집합 $E$로 이루어진다. 정점은 노드node라고도 표현한다. 각 노드와 간선은 원소, 즉 정보를 저장한다. 간선에는 방향의 유무에 따라 유향 간선directed edge과 무향 간선undirected edge이 있는데, 모든 간선이 유향 간선인 그래프는 유향 그래프라 한다. 그래프 용어 간선 $a$에 연결된 노드를 각각 간선의 끝점이라 한다. 노드 $V$에 연결된 간선 $a, b, c$를 각각 노드 $V$에 부착되었다고 한다. 간선 $a$로 연결된 노드 $U, V$를 서로 인접한 노드라 한다. 한 노드 $X$가 5개의 간선과 연결되어 있다면, 해당 노드의 차수는 5라 한다. 어떤 간선 $h, i$가 각각 노드 $V, U$를 연결하면, 간선 ..