자료구조
-
그래프의 이해와 종료 (+추가 예정)Algorithm\자료구조 2021. 8. 23. 16:00
그래프 알고리즘 : 출발지와 목적지를 정하고 그에 맞는 최적의 경로를 찾는 방법 - 수학자 '오일러'에 의해 고안되었음 (쾨니히스베르크의 다리) "정점 별로 연결된 간선의 수가 모두 짝수이어야, 한번씩만 지나서 처음 출발했던 정점으로 도착" 정점 (vertex) : 연결의 대상이 되는 개체 또는 위치 간점 (edge) : 이들 사이의 연결을 의미 - 무방향 그래프 (undirected) : 방향성이 없는 그래프 - 방향 그래프 (directed, digraph) : 간선에 방향 정보가 포함된 그래프 - 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 무방향 그래프와 방향 그래프는 간선의 연결 형태의 따라 구분됨 방향 그래프의 간선의 수는 무방향 그래프의 간선선의 수에 두 배 (쌍방 가능해..