Try

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 - 워셜 알고리즘은 각각 꼭짓점 쌍을 지나는 그래프의 모든 경로를비교한다. 이 방법은 그래프에서 의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대 의 변이 있을수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾는다. 1에서 {\displaystyle N}까지 번호가 매겨진 {\displaystyle V}를 꼭짓점으로 갖는 그래프 {\displaystyle G}를 생각한다. 그 후 {\displaystyle i}에서 {\displaystyle j}로 집합 {\displaystyle \{1,2,\ldots ,k\}}의 꼭짓점..

넓이우선탐색 (BFS, Breadth First Search) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. https://has3ong.tistory.com/54Graph 소스 가져왔습니다. 소스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626..

깊이 우선 탐색(DFS, Depth First Search) 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.여기서 부모노드로 되돌아오는 과정을 백..