
그래프는 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조이다 그래프 G 객체를 나타내는 정점과 객체를 연결하는 간선의 집합 G = (V,E)V 는 그래프에 있는 정점들의 집합 E는 정점을 연결한는 간선들의 집합(그림이 발컨이다 ..)그래프 하면 나오는 대표적

깊이 우선 탐색(DFS, Depth-First Search)는 루트에서 시작해서 다음 분기로 넘어가전에 해당 분기를 환벽하게 탐색하는 방법이다 시작 정점에서 한 방향으로 갈수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림

BFS란 루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다 이전에 DFS는 루트노드에서 깊게 들어가며 모든 정점을 순회하는 방법이라고 생각을하면 BFS는 루트노드에서 넓게 들어가며 모든 정점을 순회하는 방법이라고 생각을하면된다 이전에 DFS같은경우는 재귀를 활

신장트리란 n 개의 정점으로 이루어진 무방향 그래프 G에서 n 개의 모든정점과 n-1개의 간선으로 만들어진 트리이다깊이 우선 탐색을 이용하여 생성된 신장트리 너비 우선 탐색을 이용하여 생성된 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중 치 합

다익스트라 알고리즘은 도로 교통망 같은 곳에 나타날 수 있는 그래프에서 꼭짓점 간의 최단경로를찾는 알고리즘이다 도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 가정하면 다익스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장짧은거리를 찾는