CS210 · Annotated SlidesGraphs — Undirected Graphs

Graphs · Annotated slides

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.

63 slides
0 asked in real exams
0 related to real exam questions
3 practice questions

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up

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

Exam weight Low

Slide 2: Slide 2

Exam weight Low

Slide 3: Undirected graphs

Exam weight Low

Slide 4: Border graph of 48 contiguous United States

Exam weight Low

Slide 5: Protein-protein interaction network

Exam weight Low

Slide 6: Map of science clickstreams

Exam weight Low

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

Exam weight Low

Slide 8: 10 million Facebook friends

Exam weight Low

Slide 9: The evolution of FCC lobbying coalitions

Exam weight Low

Slide 10: Framingham heart study

Exam weight Low

Slide 11: The Internet as mapped by the Opte Project

Exam weight Low

Slide 12: Graph applications

Exam weight Low

Slide 13: Graph terminology

Exam weight Low

Path, cycle, connected, degree. Two vertices are connected if there is a path between them.

Slide 14: Some graph-processing problems

Exam weight Low

Slide 15: Slide 15

Exam weight Low

Slide 16: Graph representation

Exam weight Low

Slide 17: Graph representation

Exam weight Low

Slide 18: Graph API

Exam weight Low

Slide 19: Graph API: sample client

Exam weight Low

Slide 20: Graph representation: set of edges

Exam weight Low

Slide 21: Graph representation: adjacency matrix

Exam weight Low

Adjacency matrix: V × V booleans, O(V²) space; check an edge in O(1).

Slide 22: hash

Exam weight High

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

🎯 How this can come up · 1 question

MCQ

For a large sparse graph, the usual representation is:

Slide 23: Graph representations

Exam weight Low

Slide 24: Graph representations

Exam weight Low

Slide 25: Adjacency-list graph representation: Java implementation

Exam weight Low

Slide 26: Slide 26

Exam weight Low

Slide 27: Maze exploration

Exam weight Low

Slide 28: Trmaux maze exploration

Exam weight Low

Slide 29: Trmaux maze exploration

Exam weight Low

Slide 30: Maze exploration: easy

Exam weight Low

Slide 31: Maze exploration: medium

Exam weight Low

Maze exploration: challenge for the bored

32

Exam weight Low

Slide 33: Depth-Þrst search

Exam weight Low

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

Slide 34: aw Depth-Þrst search demo

Exam weight Low

Slide 35: Depth-Þrst search demo

Exam weight Low

Slide 36: Design pattern for graph processing

Exam weight Low

Depth-Þrst search: data structures

v

To visit a vertex:

v

Mark vertex as visited.

・

v

・

Recursively visit all unmarked vertices adjacent to.

Data structures.

・

Boolean array marked[]

to mark visited vertices.

・

Integer array edgeTo[]

to keep track of paths.

means that edge taken to visit for first time

(edgeTo[w] == v)

v-w

w

・

Function-call stack for recursion.

37

Exam weight Low

Slide 38: Depth-Þrst search: Java implementation

Exam weight Low

Slide 39: Depth-Þrst search: properties

Exam weight Low

Slide 40: Depth-Þrst search: properties

Exam weight Low

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

Exam weight Low

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

Exam weight Low

Slide 43: Slide 43

Exam weight Low

Slide 44: is

Exam weight High

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

🎯 How this can come up · 2 questions

MCQ

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

MCQ

BFS uses which data structure?

Slide 45: Breadth-Þrst search demo

Exam weight Low

Slide 46: Breadth-Þrst search

Exam weight Low

Slide 47: Breadth-Þrst search: Java implementation

Exam weight Low

Slide 48: Breadth-Þrst search properties

Exam weight Low

Slide 49: Breadth-Þrst search application: routing

Exam weight Low

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

Exam weight Low

Slide 51: Kevin Bacon graph

Exam weight Low

Breadth-Þrst search application: Erds numbers

hand-drawing of part of the Erds graph by Ron Graham

52

Exam weight Low

Slide 53: Slide 53

Exam weight Low

Slide 54: Connectivity queries

Exam weight Low

Slide 55: Connected components

Exam weight Low

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

Slide 56: Connected components

Exam weight Low

Slide 57: Connected components

Exam weight Low

Slide 58: Connected components demo

Exam weight Low

Slide 59: Connected components demo

Exam weight Low

Slide 60: Finding connected components with DFS

Exam weight Low

Slide 61: Finding connected components with DFS (continued)

Exam weight Low

Slide 62: Connected components application: particle detection

Exam weight Low

Slide 63: Graph traversal summary

Exam weight Low