Week 06
Graphs and Graph Algorithms
Graphs
Properties of Graphs
Describing Graphs
Graph Terminology
Graph ADT
Ex1: Canonical Edge Representation
Array-of-edges Representation
Ex2: Two points to consider
Ex3: Sorted Array of Edges
Ex4: Checking Neighbours (i)
Ex5: Getting Neighbours (i)
Adjacency Matrix Representation
Validity Checking
Adjacency Matrix Representation
Ex6: Checking Neighbours (ii)
Ex7: Getting Neighbours (ii)
Adjacency List Representation
Ex8: Checking Neighbours (iii)
Ex9: Getting Neighbours (iii)
Ex10: Adjacency List Storage
Comparison of Graph Representations
Graph Algorithms
Problems on Graphs
An Aside: Complexity Classes
Graph Algorithms
Finding a Path
Ex11: BFS
isPath()
Function
Ex12: Breadth-first Traversal
Ex13: Depth-first Traversal
Ex14: Finding Neighbours
Ex15: Implement GraphLab
Graph Traversal
Graph Traversal
Depth-first Traversal
Produced: 21 Aug 2017