CS210 · Graphs · Annotated SlidesUndirected Graphs
Original
Overview

Undirected Graphs

Graph terminology and applications, the Graph API, representations (edge list, adjacency matrix, adjacency lists), depth-first search, breadth-first search and shortest paths, and connected components.

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 63 slides
  1. 1 A l g o r i t h m s
  2. 2 Slide 2
  3. 3 Undirected graphs
  4. 4 Border graph of 48 contiguous United States
  5. 5 Protein-protein interaction network
  6. 6 Map of science clickstreams
  7. 7 Kevin's facebook friends (Princeton network, circa 2005)
  8. 8 10 million Facebook friends
  9. 9 The evolution of FCC lobbying coalitions
  10. 10 Framingham heart study
  11. 11 The Internet as mapped by the Opte Project
  12. 12 Graph applications
  13. 13 Graph terminology
  14. 14 Some graph-processing problems
  15. 15 Slide 15
  16. 16 Graph representation
  17. 17 Graph representation
  18. 18 Graph API
  19. 19 Graph API: sample client
  20. 20 Graph representation: set of edges
  21. 21 Graph representation: adjacency matrix
  22. 22 hash
  23. 23 Graph representations
  24. 24 Graph representations
  25. 25 Adjacency-list graph representation: Java implementation
  26. 26 Slide 26
  27. 27 Maze exploration
  28. 28 Trmaux maze exploration
  29. 29 Trmaux maze exploration
  30. 30 Maze exploration: easy
  31. 31 Maze exploration: medium
  32. 32 Maze exploration: challenge for the bored
  33. 33 Depth-Þrst search
  34. 34 aw Depth-Þrst search demo
  35. 35 Depth-Þrst search demo
  36. 36 Design pattern for graph processing
  37. 37 Depth-Þrst search: data structures
  38. 38 Depth-Þrst search: Java implementation
  39. 39 Depth-Þrst search: properties
  40. 40 Depth-Þrst search: properties
  41. 41 Depth-Þrst search application: ßood Þll
  42. 42 Depth-Þrst search application: preparing for a date
  43. 43 Slide 43
  44. 44 is
  45. 45 Breadth-Þrst search demo
  46. 46 Breadth-Þrst search
  47. 47 Breadth-Þrst search: Java implementation
  48. 48 Breadth-Þrst search properties
  49. 49 Breadth-Þrst search application: routing
  50. 50 Breadth-Þrst search application: Kevin Bacon numbers
  51. 51 Kevin Bacon graph
  52. 52 Breadth-Þrst search application: Erds numbers
  53. 53 Slide 53
  54. 54 Connectivity queries
  55. 55 Connected components
  56. 56 Connected components
  57. 57 Connected components
  58. 58 Connected components demo
  59. 59 Connected components demo
  60. 60 Finding connected components with DFS
  61. 61 Finding connected components with DFS (continued)
  62. 62 Connected components application: particle detection
  63. 63 Graph traversal summary
Slide 1 / 63

A l g o r i t h m s

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

Slide 2

Slide 2: Slide 2
Slide 3 / 63

Undirected graphs

Slide 3: Undirected graphs
Slide 4 / 63

Border graph of 48 contiguous United States

Slide 4: Border graph of 48 contiguous United States
Slide 5 / 63

Protein-protein interaction network

Slide 5: Protein-protein interaction network
Slide 6 / 63

Map of science clickstreams

Slide 6: Map of science clickstreams
Slide 7 / 63

Kevin's facebook friends (Princeton network, circa 2005)

Slide 7: Kevin's facebook friends (Princeton network, circa 2005)
Slide 8 / 63

10 million Facebook friends

Slide 8: 10 million Facebook friends
Slide 9 / 63

The evolution of FCC lobbying coalitions

Slide 9: The evolution of FCC lobbying coalitions
Slide 10 / 63

Framingham heart study

Slide 10: Framingham heart study
Slide 11 / 63

The Internet as mapped by the Opte Project

Slide 11: The Internet as mapped by the Opte Project
Slide 12 / 63

Graph applications

Slide 12: Graph applications
Slide 13 / 63

Graph terminology

Slide 13: Graph terminology
Slide 14 / 63

Some graph-processing problems

Slide 14: Some graph-processing problems
Slide 15 / 63

Slide 15

Slide 15: Slide 15
Slide 16 / 63

Graph representation

Slide 16: Graph representation
Slide 17 / 63

Graph representation

Slide 17: Graph representation
Slide 18 / 63

Graph API

Slide 18: Graph API
Slide 19 / 63

Graph API: sample client

Slide 19: Graph API: sample client
Slide 20 / 63

Graph representation: set of edges

Slide 20: Graph representation: set of edges
Slide 21 / 63

Graph representation: adjacency matrix

Slide 21: Graph representation: adjacency matrix
Slide 22 / 63

hash

Slide 22: hash

Notes

  1. Adjacency lists: a list of neighbours per vertex; space O(E + V). Used in practice (sparse graphs).

Exam angle

PredictionQ1

For a large sparse graph, the usual representation is:

Slide 23 / 63

Graph representations

Slide 23: Graph representations
Slide 24 / 63

Graph representations

Slide 24: Graph representations
Slide 25 / 63

Adjacency-list graph representation: Java implementation

Slide 25: Adjacency-list graph representation: Java implementation
Slide 26 / 63

Slide 26

Slide 26: Slide 26
Slide 27 / 63

Maze exploration

Slide 27: Maze exploration
Slide 28 / 63

Trmaux maze exploration

Slide 28: Trmaux maze exploration
Slide 29 / 63

Trmaux maze exploration

Slide 29: Trmaux maze exploration
Slide 30 / 63

Maze exploration: easy

Slide 30: Maze exploration: easy
Slide 31 / 63

Maze exploration: medium

Slide 31: Maze exploration: medium
Slide 32 / 63

Maze exploration: challenge for the bored

Slide 32: Maze exploration: challenge for the bored
Slide 33 / 63

Depth-Þrst search

Slide 33: Depth-Þrst search

Notes

  1. DFS: go as deep as possible, backtrack; marks every vertex connected to s in time proportional to the sum of degrees.

Slide 34 / 63

aw Depth-Þrst search demo

Slide 34: aw Depth-Þrst search demo
Slide 35 / 63

Depth-Þrst search demo

Slide 35: Depth-Þrst search demo
Slide 36 / 63

Design pattern for graph processing

Slide 36: Design pattern for graph processing
Slide 37 / 63

Depth-Þrst search: data structures

Slide 37: Depth-Þrst search: data structures
Slide 38 / 63

Depth-Þrst search: Java implementation

Slide 38: Depth-Þrst search: Java implementation
Slide 39 / 63

Depth-Þrst search: properties

Slide 39: Depth-Þrst search: properties
Slide 40 / 63

Depth-Þrst search: properties

Slide 40: Depth-Þrst search: properties
Slide 41 / 63

Depth-Þrst search application: ßood Þll

Slide 41: Depth-Þrst search application: ßood Þll
Slide 42 / 63

Depth-Þrst search application: preparing for a date

Slide 42: Depth-Þrst search application: preparing for a date
Slide 43 / 63

Slide 43

Slide 43: Slide 43
Slide 44 / 63

is

Slide 44: is

Notes

  1. BFS: visit vertices in order of distance from s using a QUEUE; finds shortest paths (fewest edges).

Exam angle

PredictionQ1

Which search finds the path with the fewest edges in an unweighted graph?

PredictionQ2

BFS uses which data structure?

Slide 45 / 63

Breadth-Þrst search demo

Slide 45: Breadth-Þrst search demo
Slide 46 / 63

Breadth-Þrst search

Slide 46: Breadth-Þrst search
Slide 47 / 63

Breadth-Þrst search: Java implementation

Slide 47: Breadth-Þrst search: Java implementation
Slide 48 / 63

Breadth-Þrst search properties

Slide 48: Breadth-Þrst search properties
Slide 49 / 63

Breadth-Þrst search application: routing

Slide 49: Breadth-Þrst search application: routing
Slide 50 / 63

Breadth-Þrst search application: Kevin Bacon numbers

Slide 50: Breadth-Þrst search application: Kevin Bacon numbers
Slide 51 / 63

Kevin Bacon graph

Slide 51: Kevin Bacon graph
Slide 52 / 63

Breadth-Þrst search application: Erds numbers

Slide 52: Breadth-Þrst search application: Erds numbers
Slide 53 / 63

Slide 53

Slide 53: Slide 53
Slide 54 / 63

Connectivity queries

Slide 54: Connectivity queries
Slide 55 / 63

Connected components

Slide 55: Connected components

Notes

  1. Connected components: run DFS from each unmarked vertex; label vertices with a component id.

Slide 56 / 63

Connected components

Slide 56: Connected components
Slide 57 / 63

Connected components

Slide 57: Connected components
Slide 58 / 63

Connected components demo

Slide 58: Connected components demo
Slide 59 / 63

Connected components demo

Slide 59: Connected components demo
Slide 60 / 63

Finding connected components with DFS

Slide 60: Finding connected components with DFS
Slide 61 / 63

Finding connected components with DFS (continued)

Slide 61: Finding connected components with DFS (continued)
Slide 62 / 63

Connected components application: particle detection

Slide 62: Connected components application: particle detection
Slide 63 / 63

Graph traversal summary

Slide 63: Graph traversal summary