Graphs and Graph
Algorithms
Author: PhD Jaanus Pöial, Estonian
IT College
All videoclips are captured
during fall semester of 2011 when the course was taught in
English.
Learning outcomes:
- Student knows the basic definitions - graph, digraph,
multigraph, simple graph, cyclic vs. acyclic graph, etc.
- Student knows common classical graph algorithms -
topologigal sort, shortest paths, traversal methods (depth
first, breadth first), spanning tree, etc.
- Student is able to use different graph algorithms in
programs
- Student is able to implement a graph ADT in object oriented
framework
- Student is able to test an implementation of a graph
algorithm
- Student can write a technical report about the program
Video (254 min)
Video
1 - Graph, basic
definitions
Video
2 - Operations on graphs
and related matrices, representation of graphs
Video
3 - Graph, adjacency
matrix, shortest pathlengths, transitive closure,
Floyd-Warshall algorithm, topological sort, depth-first and
breadth-first traversal, shortest paths (Dijkstra)
Video
4 - Dijkstra's algorithm
in detail, finding connected components, minimal spanning tree
Video
5 - Instructions for
individual homework on graphs
Lecture Notes
Lecture - Graphs and algorithms on graphs (in Estonian:
graafid ja algoritmid graafidel)
Extra
