홍시홍의 프로그래밍

코사라주 알고리즘 강한 연결 요소(SCC)를 구하는 것이다 SCC란 사이클을 가지는 정점의 집합이다ㅣ 시간복잡도 코사라주 알고리즘은 dfs를 기반으로 한다 인접리스트의 경우 O(V+E)로 가능하다 준비 사항 코사라주 알고리즘을 실행하기 위해서는 그래프 역방향 그래프 stack 세가지가 필요하다 구현 방법 1. 역방향 그래프를 구한다 2. 원래 그래프에서 dfs를 실시한다 3. dfs가 끝나는 대로 stack에 정점을 넣을 수 있도록 한다. 4. stack에 끝에서 부터 역방향 그래프로 dfs를 실시한다 5. 종료 되거나 방문되지 않는 것들끼리 엮어져 있는것이 SCC가 된다 아래 글이 도움이 되었다 https://wondy1128.tistory.com/130 SCC-코사라주 알고리즘(Kosaraju's A..

사용하는 이유 주어진 그래프에서의 진입차수를 이용한 순서를 구하기 위하여 특징 여러가지 위상 정렬 그래프가 나올 수 있다. 구현 위상 정렬을 정렬한 리스트와 진입 차수가 0이 되면 삽입할 큐 2개를 이용하여 구현다 현재 노드와 연결된 간선을 하나하나 제거해주면 진입되는 노드의 진입 차수가 0이 되면 큐에 넣으면서 정렬할 수 있도록 한다. 시간 복잡도 시간 복잡도는 O(V+E) 모든 노드에 대해 모든 간선을 탐색하여야 한다.

셸 정렬 정의 삽입정렬을 활용한 정렬이다 구간을 만들어서 정렬하고 이러한 구간을 합쳐 완성된 정렬을 만드는 방법 구현방법 1. 맨처음은 크기/2 구간의 리스트를 만들어 그 리스트를 정렬할 수 있도록한다. 2. 정렬 된 것을 다시 나누기 2 구간으로 만들어 리스트를 정렬한다 3. 크기가 1이 되면 정렬이 종료된 것이다 장점 삽입 정렬에 비해 교환 횟수가 적어 빠르다 시간 복잡도 n^2이나 평균적으로 n^1.5

특징 모든 정점을 연결하는 최소 경로를 찾는 알고리즘 모든 정점 n개를 연결하므로 간선은 n-1개를 가진다 음수 간선을 가질 경우, 성립할 수 없다.( 벨만-포드 알고리즘 사용) 구현방법 크루스칼, 프림 알고리즘 시간복잡도 크루스칼로 구현할 경우 Union-Find는 상수 시간 복잡도를 가지므로 정렬하는 알고리즘에 의해 좌우된다.