Objectives¶
Upon completion of this section, each student will be able to:
describe with accuracy and precision the concepts present in the reference book chapter that deals with graphs,
evaluate and implement classical representations of graphs,
choose an appropriate representation of a graph based on the operations to be performed on that graph,
- implement graph traversal and manipulation algorithms, in particular
- depth and breadth first search:
computation of connected components (computation of strongly connected components is not covered in this course)
cycle detection
topological sorting
computation of minimum weight spanning trees (Kruskal and Prim)
computation of shortest paths (Dijkstra, Bellman-Ford)