그래프 (Graph)

정의

정점(Vertex or Node)과 이들을 연결하는 간선(Edge or line)으로 구성된 자료구조. 객체 간의 쌍별 관계를 모델링하는 데 사용.

종류

• 무방향 그래프: 간선에 방향이 없는 그래프 (예: 소셜 네트워크 친구 관계)
• 방향 그래프: 간선에 방향이 있으며 순서가 쌍으로 표현
• 가중 그래프: 간선에 거리나 비용과 같은 가중치 부여
• 연결 그래프: 모든 노드에 대해 항상 경로가 존재
• 비연결 그래프: 특정 노드가 경로를 가지지 않는 경우
• 순환 그래프: 시작 노드와 종료 노드가 같은 경우
• 완전 그래프: 모든 노드가 서로 연결, 간선이 최대한 많은 구조

그래프 vs 트리