ECS122A final review

• graph traversal
  • BFS: start with given node; visit node popped from queue, add unvisited nodes to queue, repeat until nodes exhausted
  • DFS: start from any node; for each unvisited node, DFS-visit all unvisited neighbors
  • time complexity for both BFS & DFS: $O(V+E)$ if adjacency list, $O(V^2)$ if adjacency matrix
• graph single-source shortest path (shortest destination)
  • Bellman-Ford algorithm: for $|V|-1$ times: loop over all edges and try to update $d_v$ and ${\pi }_v$; do a final iteration to check if there is a negative-weight cycle
    • time complexity: $O(VE)$
  • Dijkstra’s algorithm: initialize min priority queue keyed by $d_v$; pop a node $u$, for each directed edge $(u,v)$, try to update the neighbor $v$‘s distance
    • time complexity: $O(V^2)$ w/o priority queue or $O(E\log V)$ with priority queue)
• find minimum spanning tree for an undirected graph
  • Prim’s algorithm
    • $O((V+E)\log V)$ – use when graph is dense
  • Kruskal’s algorithm
    • $O(E\log E)$ – use when graph is sparse