CS 225 Lecture Notes - Lecture 41: Disjoint Sets, Adjacency List, Minimum Spanning Tree

87 views4 pages

Document Summary

Dfs: visits each vertex, classifies each edge as either discovery or back Discovery edges are edges that lead you to a deeper "level", or new vertex. Back edges are edges that lead you back to a previously visited vertex, other way of thinking, back up a level. Output: labeling of the edges of g as discovery and back edges. For all v in g. vertices() if get label(v) = unvisited. Output: labeling of the edges of g in the connected component of v as discovery edges and back edges setlabel(v, visited) For all w in g. adjacentvertices(v) if getlabel(w) = unvisited setlabel((v,w), discovery) Cs 225 - lecture page 1 setlabel((v,w), discovery) Same runtime as bfs o(n+m) where n is the number of vertices, m is edges. // both algorithms need to check every vertex and edge. Start at a, get b from adjacency list, mark as visited vertex, mark edge a-b as discovery.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers