An Introduction to Graph Algorithms

Ute Loerch,

Department of Computer Science,

University of Auckland, Auckland, New Zealand,

ute@cs.auckland.ac.nz

Abstract:

These lecture notes contain the reference material on graph algorithms for the course: Algorithms and Data Structures (415.220FT) and are based on Dr Michael Dinneen's lecture notes of the course 415.220SC given in 1999. Topics include computer representations (adjacency matrices and lists), graph searching (BFS and DFS), and basic graph algorithms such as computing the shortest distances between vertices and finding the (strongly) connected components.

• The Graph Abstract Data Type
  • Basic definitions
  • Computer representations of graphs
  • Java graph ADT
  • Java adjacency matrix implementation
  • Java adjacency lists implementation
  • Standardized java graph class
• Graph Searching
  • Breadth-first search algorithm
  • Depth-first search algorithm
  • Graph connectivity algorithms
• Cycles in Graphs
  • Acyclic graphs and DAG's
  • Computing girth (of underlying graphs)
  • Bipartite and 2-colourable graphs
• Topological Sorting
  • Depth-first search sorting algorithm
  • Zero in-degree sorting algorithm
• Computing Distances and Diameter
  • Dijkstra's algorithm
  • Floyd's algorithm
• Final Remarks
• About this document ...