Folders and files Name Name Last commit message
Last commit date
parent directory
View all files
Floyd-Walshall
모든 거쳐가는 경로에 대해 Cost를 계산한다.
Bellman-Ford
음수 Edge 도 가능
모든 Vertex 에 대해서 Edge 모두를 순회한다.
특별한 사항
루프의 맨마지막 vertex 까지 체그하게 되면 Negative Cycle이 있는거다.
distance[edges[i].dest] > distance[edges[i].source] + edges[i].weigh 일경우
Djikstra
방향그래프, 이미 방분한 V 를 기록함
바이너리 힙(우선순위큐)을 이용한 O((e+v)*lg(v)) : V 번 바이너리힙의 REMOVE(log(v)) + E번 UNION(log(v))
피보나치 힙을 이용한 O(e+v*lg(v))
구조
시간복잡도
추가설명
선형탐색
V^2
우선순위큐(바이너리 힙)
(V+E)*Lg(V)
V번 바이너리힙 DELETE_MAX(Lg(v)) + E번 Set Union(Lg(v))
우선순위큐(피보나치 힙)
E+V*Lg(v)
MST (Minimum Spanning Tree - 최소 신장 트리)
Prim
방향 그래프는 안됨
다익스트라 처럼 우선순위큐 을 사용해 최단 Cost 인것을 가져오면서 최소 신장 트리를 만듬
인접한 노드를 모두 우선순위 큐에 넣고 그중 최단 cost 선택하고 다시 인접한 노드를 모두 우선순위큐에 넣음
알고리즘
1.하나의 Vertex을 선택하여 트리만듬
2.그래프의 모든 Edge이 들어있는 집합을 만든다.
3.모든 Vertex이 트리에 포함되어 있지 않는동안(모든곳을 방문하기 전에)
1.트리에 연결된 Edge중에 트리내의 두개의 Vertex를 이미 연결하지 않는 가중치가 가장 작은 Edge 를 선택 트리에 추가
구조
시간복잡도
인접행렬
V^2
이진힙
(V+E)Lg(V) = E Lg(v)
피보나치힙, 인접리스트
E+V*Lg(v)
Kruskal (크러스컬)
알고리즘
그래프의 각 정점이 각각 하나의 트리가 되도록 하는 포레스트 F를 만든다.
모든 Edge 를 원소로 하는 집합을 만듬
집합이 비어있지 않는동안
가장 작은 가중치의 Edge을 S에서 하나 빼낸다.
Edge가 어떤 두개의 트리를 연결한다면 두 트리를 연결하여 하나의 트리로 만든다.
그렇지 않다면 그 Edge 는 버린다.
각 정점의 위상 선형 정렬 ex) 선수과목
(DAG-Directed Acylic Graph) 방향 그래프 가능, 싸이클이 있으면 안됨
알고리즘
1.자기 자신을 가리키는 Edge 가 없는 Vertex 를 찾음 (indegree = 0)
2.찾은 Vertex 를 출력, 연결되었던 Edge 삭제
3.아직 그래프에 Vertex 가 있으면 1단계로 돌아가고 아니면 종료
DFS 로 순환하면서 방문한 Vertex 를 기록하고 돌아서 다시 돌아모면 순환이 존재한다고 판단.
무방향 그래프일경우 역방향 Edge도 모두 지나간 길로 기록한다. 기록한길로는 다시 지나가지 않도록함
You can’t perform that action at this time.