CS 2420 Lecture Notes - Lecture 10: Adjacency Matrix, Priority Queue, Tree Traversal
7 Apr 2017
School
Department
Course
Professor
Document Summary
Evaluating the number of hearts, spades, clubs, and diamonds. Graphs represent ordered connections between entities, represented by nodes and edges (treeees) Fast at finding if edge exits between 2 vertices. Memory usage: o(v^2) since matrix is vxv dimension. O(edges) determination if an edge exists between 2 vertices (linear) O(edges) determination of all edges from a vertex (linear) If the node has not already been visited, mark the node put all neighbors in queue. Start the search at the source and assign it a distance of 0. Then visit all the neighbors of the source and give each neighbor (linked node) a distance of 1 and set its predecessor to be the source. Keep going until all vertices reachable from the source vertex have been visited, Uses recursion or stack, gets to end of one direction, goes in other direction. Greedy algorithm: always takes the best current solution. For problems such as min. distance greedy alogrithms are ideal.
