COMPSCI 61B Lecture Notes - Lecture 30: Linked List, Prims, Javadoc
1 Jun 2017
School
Department
Course
Professor
Document Summary
Signi cant project so don"t put o starting until the last minute. Larger than project 1, but not as big as project 2. Project will be closest to what you might do at an internship. Working with and improving upon an existing codebase. Use of many tools at once (webbrowser, maven, intellij) Given a undirected graph, determine if it contains any cycles. May use any data structure or algorithm from the course so far. Keep going until you see a marked vertex. Worst case runtime: theta(v + e) do study guide problems to reinforce this. For each edge, check if the two vertices are connected. Worst case runtime: o(v + e log* v) if we have path compression. Given an undirected graph, a spanning tree t is a subgraph of g, where t: Example: spanning tree is the black edges and vertices. A minimum spanning tree is a spanning tree of minimum total weight.
