COMS W3134 Lecture Notes - Lecture 24: Disjoint Sets, Priority Queue, Binary Heap
6 Dec 2016
School
Department
Course
Professor
Document Summary
Announcements: hw 5 due tomorrow tue 12/6, allowed to modify merge method from textbook for programming problem 1. Lecture: dijkstra"s algorithm, from textbook dijkstra method. Extract from list of vertices, which has least distance and also marked unknown. Can scan across vertices (getvertices) to look for smallest (findmin: o(|v|) Can keep counter, when outer loop increment until all vertices are settled. Can also delete vertices as you go until no more vertices (a little more expensive) Or each time through list, extract smallest unknown vertex, can use priority queue (binary heap, min heap: deletemin cost: o(log|v|, percolating up, o(logn, or o(log|v|) for vertices, o(|e|log|v|) after running through the nested loops. Total cost of method: o(|v|log|v| +|e|, without priority queue, runtime is o(|v|^2, calculating minimum spanning tree, undirected graph. Subgraph that contains call of vertices, contains a subset of edges: needs to be fully connected. Spanning means reaches every vertex in the graph.
