Some graphs you may have met under different circumstances.

Course prerequisites

	Topological sort gives order to take classes

Maze

Depth first search – Web as graph

	Avoid loops: don’t repeat nodes.
	Use some kind of Set ADT

Electronic circuits

	Edges labelled (resistors, switch, etc)
	Analyze Zasha’s incompetence in EE

Profiler call frequency info

Compiler analysis – Common Subexpression Elimination

Proofs – best case correct sorting by comparison

	List is x1,…,x8
	Edge is comparison
	<7 edges à graph not connected
	Connected components could be on either side. How would the algorithm know?

(small part of) Java class hierarchy

Cheapest Computer Network – Minimum Spanning Tree

Capacity of highways – max flow

TA assignments

	Bipartite graph – 2 node types (TAs and Courses)
	Maximal matching (assign as many TAs to as many courses as possible)

Six degrees of Kevin Bacon

Six degrees of Kevin Bacon