CS210 · Graphs · Annotated SlidesDirected Graphs
Original
Overview

Directed Graphs

Digraph applications, the Digraph API and adjacency lists, reachability with DFS, BFS in digraphs (web crawler), topological sort, and directed cycle detection.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 69 slides
  1. 1 A l g o r i t h m s
  2. 2 Slide 2
  3. 3 Directed graphs
  4. 4 Road network
  5. 5 Political blogosphere graph
  6. 6 Overnight interbank loan graph
  7. 7 Uber taxi graph
  8. 8 Implication graph
  9. 9 Combinational circuit
  10. 10 WordNet graph
  11. 11 Digraph applications
  12. 12 Some digraph problems
  13. 13 Slide 13
  14. 14 Digraph API
  15. 15 Digraph API
  16. 16 Digraph representation: adjacency lists
  17. 17 Digraph representations
  18. 18 Adjacency-lists graph representation (review): Java implementation
  19. 19 Adjacency-lists digraph representation: Java implementation
  20. 20 Slide 20
  21. 21 Reachability
  22. 22 Depth-Þrst search in digraphs
  23. 23 Iiii
  24. 24 8
  25. 25 Depth-Þrst search demo
  26. 26 Depth-Þrst search (in undirected graphs)
  27. 27 Depth-Þrst search (in directed graphs)
  28. 28 Reachability application: program control-ßow analysis
  29. 29 Reachability application: mark-sweep garbage collector
  30. 30 Reachability application: mark-sweep garbage collector
  31. 31 Depth-Þrst search in digraphs summary
  32. 32 Breadth-Þrst search in digraphs
  33. 33 Directed breadth-Þrst search demo bfs 11.3.1919
  34. 34 Directed breadth-Þrst search demo
  35. 35 Multiple-source shortest paths
  36. 36 six
  37. 37 direted
  38. 38 Breadth-Þrst search in digraphs application: web crawler
  39. 39 Bare-bones web crawler: Java implementation
  40. 40 Web crawler output
  41. 41 Slide 41
  42. 42 Precedence scheduling
  43. 43 Topological sort
  44. 44 Topological sort demo
  45. 45 Topological sort demo
  46. 46 Depth-Þrst search order
  47. 47 Topological sort in a DAG: intuition
  48. 48 Topological sort in a DAG: correctness proof
  49. 49 Directed cycle detection
  50. 50 Directed cycle detection application: precedence scheduling
  51. 51 Directed cycle detection application: cyclic inheritance
  52. 52 Directed cycle detection application: spreadsheet recalculation
  53. 53 Depth-Þrst search orders
  54. 54 Slide 54
  55. 55 Strongly-connected components
  56. 56 Connected components vs. strongly-connected components
  57. 57 Strong component application: ecological food webs
  58. 58 Strong component application: software modules
  59. 59 X
  60. 60 Kosaraju-Sharir algorithm: intuition
  61. 61 Kosaraju-Sharir algorithm demo
  62. 62 Kosaraju-Sharir algorithm demo
  63. 63 Kosaraju-Sharir algorithm demo
  64. 64 Kosaraju-Sharir algorithm
  65. 65 Kosaraju-Sharir algorithm
  66. 66 Kosaraju-Sharir algorithm
  67. 67 Connected components in an undirected graph (with DFS)
  68. 68 Strong components in a digraph (with two DFSs)
  69. 69 Digraph-processing summary: algorithms of the day
Slide 1 / 69

A l g o r i t h m s

Slide 1: A l g o r i t h m s
Slide 2 / 69

Slide 2

Slide 2: Slide 2
Slide 3 / 69

Directed graphs

Slide 3: Directed graphs
Slide 4 / 69

Road network

Slide 4: Road network
Slide 5 / 69

Political blogosphere graph

Slide 5: Political blogosphere graph
Slide 6 / 69

Overnight interbank loan graph

Slide 6: Overnight interbank loan graph
Slide 7 / 69

Uber taxi graph

Slide 7: Uber taxi graph
Slide 8 / 69

Implication graph

Slide 8: Implication graph
Slide 9 / 69

Combinational circuit

Slide 9: Combinational circuit
Slide 10 / 69

WordNet graph

Slide 10: WordNet graph
Slide 11 / 69

Digraph applications

Slide 11: Digraph applications
Slide 12 / 69

Some digraph problems

Slide 12: Some digraph problems
Slide 13 / 69

Slide 13

Slide 13: Slide 13
Slide 14 / 69

Digraph API

Slide 14: Digraph API
Slide 15 / 69

Digraph API

Slide 15: Digraph API
Slide 16 / 69

Digraph representation: adjacency lists

Slide 16: Digraph representation: adjacency lists

Notes

  1. Adjacency lists, but each edge appears once (in v’s list only).

Slide 17 / 69

Digraph representations

Slide 17: Digraph representations
Slide 18 / 69

Adjacency-lists graph representation (review): Java implementation

Slide 18: Adjacency-lists graph representation (review): Java implementation
Slide 19 / 69

Adjacency-lists digraph representation: Java implementation

Slide 19: Adjacency-lists digraph representation: Java implementation
Slide 20 / 69

Slide 20

Slide 20: Slide 20
Slide 21 / 69

Reachability

Slide 21: Reachability
Slide 22 / 69

Depth-Þrst search in digraphs

Slide 22: Depth-Þrst search in digraphs
Slide 23 / 69

Iiii

Slide 23: Iiii
Slide 24 / 69

8

Slide 24: 8
Slide 25 / 69

Depth-Þrst search demo

Slide 25: Depth-Þrst search demo
Slide 26 / 69

Depth-Þrst search (in undirected graphs)

Slide 26: Depth-Þrst search (in undirected graphs)
Slide 27 / 69

Depth-Þrst search (in directed graphs)

Slide 27: Depth-Þrst search (in directed graphs)
Slide 28 / 69

Reachability application: program control-ßow analysis

Slide 28: Reachability application: program control-ßow analysis
Slide 29 / 69

Reachability application: mark-sweep garbage collector

Slide 29: Reachability application: mark-sweep garbage collector
Slide 30 / 69

Reachability application: mark-sweep garbage collector

Slide 30: Reachability application: mark-sweep garbage collector
Slide 31 / 69

Depth-Þrst search in digraphs summary

Slide 31: Depth-Þrst search in digraphs summary
Slide 32 / 69

Breadth-Þrst search in digraphs

Slide 32: Breadth-Þrst search in digraphs
Slide 33 / 69

Directed breadth-Þrst search demo bfs 11.3.1919

Slide 33: Directed breadth-Þrst search demo bfs 11.3.1919
Slide 34 / 69

Directed breadth-Þrst search demo

Slide 34: Directed breadth-Þrst search demo
Slide 35 / 69

Multiple-source shortest paths

Slide 35: Multiple-source shortest paths
Slide 36 / 69

six

Slide 36: six
Slide 37 / 69

direted

Slide 37: direted
Slide 38 / 69

Breadth-Þrst search in digraphs application: web crawler

Slide 38: Breadth-Þrst search in digraphs application: web crawler
Slide 39 / 69

Bare-bones web crawler: Java implementation

Slide 39: Bare-bones web crawler: Java implementation
Slide 40 / 69

Web crawler output

Slide 40: Web crawler output
Slide 41 / 69

Slide 41

Slide 41: Slide 41
Slide 42 / 69

Precedence scheduling

Slide 42: Precedence scheduling
Slide 43 / 69

Topological sort

Slide 43: Topological sort

Notes

  1. Topological sort: order vertices so every edge points forward. Possible only for a DAG. Reverse DFS postorder gives it.

Exam angle

PredictionQ1

A topological order exists if and only if the digraph:

Slide 44 / 69

Topological sort demo

Slide 44: Topological sort demo
Slide 45 / 69

Topological sort demo

Slide 45: Topological sort demo
Slide 46 / 69

Depth-Þrst search order

Slide 46: Depth-Þrst search order
Slide 47 / 69

Topological sort in a DAG: intuition

Slide 47: Topological sort in a DAG: intuition
Slide 48 / 69

Topological sort in a DAG: correctness proof

Slide 48: Topological sort in a DAG: correctness proof
Slide 49 / 69

Directed cycle detection

Slide 49: Directed cycle detection

Notes

  1. Directed cycle detection with DFS (a back edge to a vertex on the stack).

Slide 50 / 69

Directed cycle detection application: precedence scheduling

Slide 50: Directed cycle detection application: precedence scheduling
Slide 51 / 69

Directed cycle detection application: cyclic inheritance

Slide 51: Directed cycle detection application: cyclic inheritance
Slide 52 / 69

Directed cycle detection application: spreadsheet recalculation

Slide 52: Directed cycle detection application: spreadsheet recalculation
Slide 53 / 69

Depth-Þrst search orders

Slide 53: Depth-Þrst search orders
Slide 54 / 69

Slide 54

Slide 54: Slide 54
Slide 55 / 69

Strongly-connected components

Slide 55: Strongly-connected components
Slide 56 / 69

Connected components vs. strongly-connected components

Slide 56: Connected components vs. strongly-connected components
Slide 57 / 69

Strong component application: ecological food webs

Slide 57: Strong component application: ecological food webs
Slide 58 / 69

Strong component application: software modules

Slide 58: Strong component application: software modules
Slide 59 / 69

X

Slide 59: X
Slide 60 / 69

Kosaraju-Sharir algorithm: intuition

Slide 60: Kosaraju-Sharir algorithm: intuition
Slide 61 / 69

Kosaraju-Sharir algorithm demo

Slide 61: Kosaraju-Sharir algorithm demo
Slide 62 / 69

Kosaraju-Sharir algorithm demo

Slide 62: Kosaraju-Sharir algorithm demo
Slide 63 / 69

Kosaraju-Sharir algorithm demo

Slide 63: Kosaraju-Sharir algorithm demo
Slide 64 / 69

Kosaraju-Sharir algorithm

Slide 64: Kosaraju-Sharir algorithm
Slide 65 / 69

Kosaraju-Sharir algorithm

Slide 65: Kosaraju-Sharir algorithm
Slide 66 / 69

Kosaraju-Sharir algorithm

Slide 66: Kosaraju-Sharir algorithm
Slide 67 / 69

Connected components in an undirected graph (with DFS)

Slide 67: Connected components in an undirected graph (with DFS)
Slide 68 / 69

Strong components in a digraph (with two DFSs)

Slide 68: Strong components in a digraph (with two DFSs)
Slide 69 / 69

Digraph-processing summary: algorithms of the day

Slide 69: Digraph-processing summary: algorithms of the day