Graph

• Representation
  • Adjacency list
    • $\Theta (V+E)$ space and time
    • Robust and can be modified to incorporate different variants of graphs
    • Difficult to determine existence of an edge.
    • Good for sparse graph
  • Adjacency matrix
    • $\Theta (V^2)$ space and time
    • Easily determine edge existence
    • One bit per edge for unweighted graph
    • Good for dense or reasonably small graph
• Searching the graph
  • Breadth-first search
  • Depth-first search
  • Minimum Spanning Tree