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