홍시홍의 프로그래밍

개념 그래프 내에서 시작 정점 부터 원하는 정점까지 이동가능한지 알아보는 알고리즘이다 하나의 분기에 도달했다면 그 분기에 대해서는 탐색할 수 있는 모든 경로를 탐색하고 넘어가는 알고리즘이다 사용하는 곳 A에서 B로의 이동 가능 여부 전자회로에서 연결 여부 시간 복잡도 인접 행렬의 경우 O(n^2) 인접 리스트의 경우 O(n+m) 구현방법 백트래킹을 사용해 구현한다 특징 너무 깊을 경우에는 모든 정점을 다 깊게 탐색하므로 다른 알고리즘을 사용하는것이 현명하다

시간 복잡도 모든 정점에 대해서 모든 가능성을 검사한다 O(V^3) 사용하는 곳 모든 최단 경로를 알고 싶을 경우 특징 음의 가중치가 있어도 사용 가능하다 구현방법 거리가 업데이트될 수 있으면 계속해서 업데이트 해준다 아래 블로그에 자세히 설명되어 있다 https://hsp1116.tistory.com/45 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 앞서 다익스트라 알고리즘 포스트에서, 그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이 있다고 했다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(si hsp1116.tistory.com

특징 1. 음의 가중치를 갖는 그래프에서 최단경로를 구할 수 있다. 2. 음의 가중치 여부를 알 수 있다 구현 방법 모든 노드의 숫자만큼 거리가 업데이트 될 수 있는가 검사한다 V만큼 E가 업데이트 될 수 있는지 검사한다 그리고 마지막 V+1번 검사할때, 거리가 업데이트된다면 음의 가중치를 갖는 그래프이다 시간 복잡도 V만큼 E가 업데이트 될 수 있는지 검사하므로 O(VE)이다

시간 복잡도 행렬을 사용하였을 경우는 O(n^2) 힙을 사용하였을 경우는 O(nlogn) 구현방법 프림 알고리즘은 현재 정점에서 다른 정점에 갈 수 있다면 가는 알고리즘? 이다 거리가 갱신된다면 그 정점으로의 이동이 가능하다 큐에 있는 정점 중 이동 거리가 제일 작은 것의 작은거??로 이동하는 알고리즘 pq에 시작 노드를 넣고 거리를 0으로 초기화 노드를 꺼내서 방문한 노드라면 pass 방문하지 않은 노드이고 연결된 노드라면 큐에 넣는다 모든 노드가 연결될때까지 n-1개의 간선이 생길때까지 연결한다 특징 노드의 수보다 간선이 더 많을때 사용한다 아래 블로그에 이해하기 쉽게 설명되어 있다 https://makefortune2.tistory.com/37 22. 최소신장트리(MST) 프림(Prim) 알고리즘 ..