• A Data Structure that can be used to model a lot of real-world problems

3 Ways to Represent

Adjacency Matrix

  • A 2d Array, the row and column index indicates the id of a node
  • Pros: Check the relationship of any 2 nodes in O(1)
  • Cons: Space wastage for Sparse Graph

Adjacency List

Adjacency Set

  • A collection of all Edge


Weighted Graph (加权图)

Directed Graph

  • Can be used to represent Relation which only involves one Set

Non-Directed Graph

Sparse Graph

  • A graph in which the number of edges is much less than the possible number of edges