Videos / DSA

Episode 21 of 22 · DSA, end to end

Graphs: the structure most problems turn out to be

Chapters

1. Dots and string0:00
2. Three flavours0:15
3. Degree, counted twice0:33
4. The modelling step0:49
5. The grid nobody builds1:06
6. Three shapes with names1:22
7. Two filing systems1:41
8. The adjacency list1:57
9. The adjacency matrix2:16
10. Density decides2:32
11. The honest table2:52
12. Weights, and a third form3:11
13. Rings, and a maze3:27
14. The queue does the work3:44
15. Layers are distances4:00
16. Four lines of recursion4:17
17. Distance against shape4:35
18. Linear, and why exactly4:53
19. An archipelago5:09
20. The loop that counts5:27
21. A cycle in an undirected graph5:44
22. White, grey, black5:59
23. Laying it on a line6:16
24. Peel the zeroes off6:35
25. Hops are not minutes6:52
26. Always the smallest7:09
27. The heap, in practice7:28
28. One negative edge, broken7:45
29. Relax everything, V−1 times8:01
30. The extra pass, and the picker8:19
31. Cable for a campus8:37
32. Cheapest first, skip cycles8:54
33. Are these two connected9:12
34. Union by size, then flatten9:30
35. Almost constant, honestly9:47
36. Prim, and the pick10:06
37. The whole thing10:22

Graphs: the structure most problems turn out to be. Pin some dots on a wall and draw string between them. That is a graph. The dots are vertices. The strings are edges. That is the entire definition, and it is why graphs turn up in

Mark as watchedSaved in this browser only.