Greedy to Graphs

• BFS, DFS all edge weights equal, but not?
• Can greedily select which edges to search based on weight

Traversing Dijkstra’s

• Use racing method to prove effectiveness of Dijkstra’s
• Are subjecting to revision, so technically not Greedy
• Dijkstra’s only works for weights greater than 0
• $O((E+N)\log N)$
• Could you do a min cost breadth first search traversal on a weighted graph?
  • Expand weights to more nodes to make it effectively unweighted

Minimum Spanning Tree

• Minimum number of edges

Prim’s Algorithm

• Two disjoint sets of nodes (ones that contain, others that are growing)
  • Select node that is, connected to browning in spanning tree
  • Not in growing spanning tree
  • Has the lowest weighted edge and add it into the growing spanning tree
• Can chose arbitrarily, will be unique
• Prim’s is greedy, so negative edges work
• $O(E\log N)$

Kruskal’s Algorithm

• Greedy, adds edges
• Each iteration finds edge which as least weight and adds to spanning tree