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

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

Breadth first search and applications to finding the shortest path

Screencast Suthers 16 min

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

Textbook 24 pages

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

Textbook 12 pages

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

Textbook 12 pages

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

Textbook 70 pages

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

Notes

Working with breadth first search and depth first search

Homework