COMPSCI 61B Lecture Notes - Lecture 24: Prims, Binary Heap, Dream Evil
Document Summary
Given an undirected graph, determing if it contains any cycles. May use any data structure or algorithm from the course. Approach 1: do dfs from 0 (arbitrary vertex) Keep going until you see a marked vertex. 1 looks back at 0 and sees marked. Solution: just don"t count the node you come from. For each edge, check if the 2 vertices are connected. Worse case runtime: o(v+elog*(v)) if we have path compression. Given an undirected graph, a spanning tree t is a subgraph of g, where t: Is connected - make it a tree. Is acyclic - make it a tree. Includes all of the vertices - makes it spanning. A minimum spanning tree is a spanning tree of minimum total weight. A shortest paths tree depends on the start vertex. Because it tells you how to get from a source to everything. But the mst sometimes happens to be an spt for a specific vertex.
