API tools faq
paste
wavec022

graphs

wavec022
Apr 15th, 2020
185
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.95 KB | None | 0 0
raw download clone embed print report
  1. Graphs: dots and lines
  2.  
  3. minimum spanning tree: all vertices, no cycles, minimum edge weight
  4.  
  5. Prims, Dijkstras, and Kruskals algorithms
  6.  
  7. ===
  8.  
  9. the actual graphs lesson
  10.  
  11. what is a graph and whatnot
  12.  
  13. graph-- G(v,e) vertices/edges
  14. directed vs undirected graph
  15.  
  16. endpoints, incident, adjacent vertices, degree, multi edges, self edges, path/simple path
  17.  
  18. subgraph
  19. connected vs complete-- connected: path from each to every other
  20.  
  21. ===
  22.  
  23. Graphs 2
  24. g = (v,e)
  25. v = n
  26. e = v-1
  27.  
  28. no cycle
  29. take any 5 edges
  30.  
  31. ncr for number of possible trees
  32.  
  33. ===
  34.  
  35. Prim's algorithm-- finds smallest connected edge
  36.  
  37. Kruskal's: chooses edge with minimum weight and repeats until it's done
  38. but it picks all the minimum ones not just the ones that are connected
  39. can use a minheap to store the edges in a minheap
  40.  
  41. dijkstra-- calculate cost from 1 to every other node; this is in pictures for math homework
  42.  
  43. Dijkstra table: https://gyazo.com/4e512ec296a83ebb4570ed0988151a4e
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!