그래프
1.[자료구조]그래프
그래프는 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조이다 그래프 G 객체를 나타내는 정점과 객체를 연결하는 간선의 집합 G = (V,E)V 는 그래프에 있는 정점들의 집합 E는 정점을 연결한는 간선들의 집합(그림이 발컨이다 ..)그래프 하면 나오는 대표적
2.[알고리즘] DFS : 깊이 우선 탐색
깊이 우선 탐색(DFS, Depth-First Search)는 루트에서 시작해서 다음 분기로 넘어가전에 해당 분기를 환벽하게 탐색하는 방법이다 시작 정점에서 한 방향으로 갈수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림
3.[알고리즘] BFS(너비 우선탐색)
BFS란 루트노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다 이전에 DFS는 루트노드에서 깊게 들어가며 모든 정점을 순회하는 방법이라고 생각을하면 BFS는 루트노드에서 넓게 들어가며 모든 정점을 순회하는 방법이라고 생각을하면된다 이전에 DFS같은경우는 재귀를 활
4.[알고리즘] 크루스칼 알고리즘
신장트리란 n 개의 정점으로 이루어진 무방향 그래프 G에서 n 개의 모든정점과 n-1개의 간선으로 만들어진 트리이다깊이 우선 탐색을 이용하여 생성된 신장트리 너비 우선 탐색을 이용하여 생성된 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중 치 합
5.[알고리즘] 다익스트라
다익스트라 알고리즘은 도로 교통망 같은 곳에 나타날 수 있는 그래프에서 꼭짓점 간의 최단경로를찾는 알고리즘이다 도시의 지도에서 출발지와 목적지 사이의 가장 짧은 거리를 찾는다고 가정하면 다익스트라 알고리즘에서는 교차점마다 출발지로부터의 거리를 적어서 가장짧은거리를 찾는