Computer Science 501
Data Structures and Algorithm Analysis
Fall 2015, The College of Saint Rose
Lecture 11: Graphs
Date: Wednesday, November 18, 2015
Agenda
- Announcements
- don't forget not to come to class next week - Thanksgiving break
- Practice final exam/study guide out
- Lab 9: Best Of [HTML] [PDF] past due, will also go over next class
- Lab 10: Trees [HTML] [PDF] now due, will go over next class
- Graphs
- definition and terminology
- graph structures: directed/undirected, adjacency matrix/adjacency list
- Graph algorithms
- reachability
- single-source shortest paths
- Lab 11: More Trees, Graphs, and Dijkstra's Road Trip [HTML] [PDF] out
- More graph algorithms
- transitive closure
- all-pairs shortest paths
Readings and References
Terminology
- graph
- node/vertex
- edge
- edge weight
- adjacent
- path
- simple path
- cycle
- directed graph/digraph
- degree (of a graph vertex)
- in-degree/out-degree
- connected (vertices)
- subgraph
- connected component
- acyclic (graph)
- complete (graph)
- adjacency matrix
- adjacency list
- reachability
- Dijkstra's algorithm
- breadth-first order
- depth-first order
- transitive closure
- Warshall's algorithm
- all-pairs minimum distance
- Floyd's algorithm
Examples