Module: Graphs

Definitions, methods, breadth first search, depth first search, shortest path, asymptotic complexity, topological sort, strongly connected components.

Learning Outcomes

Understand graphs

Be able to assess when to use different graph algorithms and why they might be preferred for a given problem context.


Graph definitions

Graph definitions

Screencast Suthers 13 min

Graph ADT and representations

Methods in the graph ADT

Screencast Suthers 23 min

Breadth first search

Breadth first search and applications to finding the shortest path

Screencast Suthers 16 min

Depth first search

Depth first search and its asymptotic complexithy

Screencast Suthers 10 min

Depth first search: example and properties

Depth first search trace.

Screencast Suthers 17 min

Topological sort

Topological sort and strongly connected components

Screencast Suthers 26 min

CLRS 22 - Elementary graph algorithms

Representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components

Textbook 24 pages

Sedgewick 32 - Directed graphs

Depth first search, transitive closure, topological sorting, strongly connected components

Textbook 12 pages

Sedgewick and Wayne 4 - Graphs

Undirected graphs, directed graphs, minimum spanning trees, shortest paths

Textbook 12 pages

Goodrich and Tommassia 13 - Graphs

The graph ADT, data structures for graphs, graph traversals, directed graphs, weighted graphs, shortest paths, minimum spanning trees

Textbook 70 pages

Notes on graphs

Graph definitions, examples, the ADT, representations, breadth first seach, depth first search, topological sort, strongly connected components


Experiential Learning

Breadth first search and depth first search

Working with breadth first search and depth first search