CSE 100 Study Guide - Quiz Guide: Priority Queue, Dense Graph, Adjacency Matrix

• School: UCSD
• Department: Computer Science & Engineering
• Course: CSE 100
• Professor: Nuno Bandeira

Document Summary

Can have 0 edges (|e| = 0) Or vertex is connected to every other vertex in graph (|e|=|v| 2 ) Space complexity: o(|v| 2 ), therefore not ideal for sparse graphs. For undirected graph, both index for the pair will be marked. Breadth first search (bfs) be as large as |v| 2 . Explore all vertices reachable from the current vertex before moving onto the next. Uses a queue to determine the order in which to explore vertices. Allows us to find the shortest path from one node to any other node in a. Explore all vertices going down from the current vertex, before moving onto the next neighboring vertex. Difference in memory management (bfs vs dfs) Bfs stores all of a vertex"s neighbors in each step in a queue, to later be able to traverse those neighbors. Dfs only needed to store the previous neighbor to explore the next one.