CS 106B Lecture Notes - Lecture 25: Hamiltonian Path, Backtracking, Dfs Furniture
29 Nov 2016
School
Department
Course
Professor
Document Summary
Graphs: a mathematical structure for representing relationships using nodes and edges, consists of a set of nodes connected by edges, directed vs undirected. Start and end vs no concept of start and stop: edge weights. Weight: cost associated with a given edge: ways to write graph structures. Create a vertex structure that has a value and a vector of all the edges (vector * type) Edge contains a start and an end (if directed graph) Graph contains a set of vector* type. Facebook significant other algorithm: finding dispersion score between you and a friend. Finding mutual friends between you and him/her and finding how many mutual friend pairs don"t know each other. We will use recursive backtracking to find every possible path that exists through all the nodes. Logistics: chris office hours tomorrow; moved to 10am-11am, will hold additional hours 3:30-5pm, final exam: 2 weeks from today!
