그래프
-
객체들 간의 관계를 표현하는데 사용되는 추상적인 자료구조
-
정점(vertex) or 노드(node)와 이를 연결해주는 간선(edge)으로 이루어져 있다.
무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)
-
무방향 그래프는 간선의 방향이 없는 그래프로, 노드 간의 연결 관계가 양방향으로 표현됨
-
방향 그래프는 간선에 방향이 있는 그래프로, 노드 간의 연결 관계가 단방향으로 표현됨.
-
방향 그래프에서, 노드가 자기 자신으로 향하는 간선을 갖는 그래프를 셀프 루프 그래프(Self-Loop Graph)라고 함 -> 자기 참조의 데이터 구조를 표현할 때 유용
기타 다양한 그래프들 정리
-
가중치 그래프(Weighted Graph)는 간선에 가중치가 부여된 그래프로, 도로의 길이와 네트워크 비용과 같은 데이터를 표현할 때 유용
-
멀티그래프(MultiGraph)는 두 개 이상의 간선이 동일한 두 노드를 연결하는 그래프로, 중복된 간선을 허용하는 그래프
-
사이클 그래프(Cyclic Graph)는 하나 이상의 사이클(순환 경로)가 존재하는 그래프. 반대로 이런 사이클이 존재하지 않는 그래프는 비순환 그래프(Acyclic Graph)라고 한다.
-
연결 그래프(Connected Graph)는 그래프에서 어떤 두 노드간에 경로가 존재하는 그래프. 어떠한 노드에서 다른 모든 노드로 이동할 수 있다고 생각하면 편하다. 반대로 연결 그래프가 아니라면 비연결 그래프(Disconnected Graph)라고 함.
-
완전 그래프(Complete Graph)는 모든 노드가 서로 연결된 그래프를 말한다. 모든 노드가 인접해 있다고 생각하면 편할듯. 위의 연결 그래프와 혼동 주의!
