자료구조 14강 - 그래프의 개념과 표현 방법 현실의 복잡한 관계를 정점과 간선으로 추상화하는 그래프의 기본 개념을 학습합니다. 방향·다중·가중 그래프, 인접과 차수, 경로와 사이클 등의 용어를 구분하고 그래프 추상 자료형과 인접 행렬·인접 리스트 표현을 정리합니다. 그래프의 개념 관계를 정점과 간선으로 추상화하기 그래프(graph)는 대상을 정점(vertex, node)으로, 대상 사이의 관계를 간선(edge)으로 나타내는 자료구조입니다. 지하철 노선에서 역을 정점으로, 역을 잇는 노선을 간선으로 표현하거나 도로망·통신망·프로젝트 일정·컴퓨터 네트워크의 연결을 나타낼 수 있습니다. 그래프 G는 하나 이상의 정점을 포함하는 집합 V와 두 정점의 관계를 나타내는 간선의 집합 E로 정의하며 G=(V,E) 로 씁니다. 같은 그림이라도 정점과 간선의 집합을 명시하면 그래프의 논리 구조를 정확히 표현할 수 있습니다. 기호 의미 G 그래프 전체 V 정점들의 유한 집합 E 정점 사이의 관계를 나타내는 간선 집합 vᵢ, vⱼ 그래프를 구성하는 개별 정점 추상화의 장점 실제 거리나 지도 모양을 모두 보존하지 않아도 “어떤 대상들이 어떤 관계로 연결되어 있는가”에 집중할 수 있습니다. 방향 그래프와 무방향 그래프 간선에 방향이 있는가 무방향 그래프의 간선은 방향이 없으며 두 정점의 순서를 구별하지 않습니다. 정점 v₁과 v₂를 잇는 간선은 순서 없는 쌍 {v₁,v₂} 로 나타냅니다. v₁에서 v₂로 이동할 수 있으면 같은 간선을 이용해 v₂에서 v₁로도 이동할 수 있습니다. 방향 그래프의 간선은 시작점과 끝점이 정해져 있으며 순서쌍 (v₁,v₂) 로 나타냅니다. 이는 v₁...