프로그래밍/자료구조
-
[자료구조] 그래프프로그래밍/자료구조 2019. 5. 16. 00:23
그래프란? : 그래프(graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. 그래프는 정점과 간선들의 집합이라고 할 수 있습니다. 그래프는 보통 지도에서 자주 사용하는 자료구조인데, 예를 들어 인천에서 서울까지의 최단거리, 최소비용 등을 구하는 데 사용합니다. 필요한 개념 및 용어 1. 정점(vertex) 와 간선(edge) 정점은 그래프의 위치, 간선은 정점들 간의 관계를 의미합니다. 2. 무방향 그래프(undirected graph) 와 방향 그래프(directed graph) 무방향 그래프는 간선을 통해 양 방향 이동이 가능하다. 방향 그래프는 간선을 통해 단 방향 이동이 가능하다. 3. 가중치 그래프(weight graph) 간선에 연결 강도를 표시할 수 있는 그래프 (ex..