Graph Basics

Graph Representations

• Adjacency Matrix

  • If we have a graph with $n$ vertices. We can represent this graph with a matrix $M_{n\times n}$, where $[M]_{i,j}=1$ if there is a edge from $v_i$ to $v_j$
  • $[M^n]_{i,j} =$ number of path from $v_i$ to $v_j$ with length $n$
  • If we replace the addition and multiplication with or and and, we can find the reachibility.
  • If we replace the addition and multiplication with min and addition, this is Floyd

• Adjacency List

  • We can use an array to store the neighbor for each vertex.

• Complexities

  	Space	Add/Delete	Lookup
  Adj. Mat.	O(|V^2|)	O(|V|)	O(1)
  Adj. List	O(|E|)	O(|N_v|)	O(|N_v|)

  N_v: neighbor of v

Basic Search Algorithms

• BFS
  • Underlying data structure: queue
  • Key property: visit the nodes in the order of depth from the starting node
  • Applications: Shortest Path on Unweighted Graph
• DFS
  • Number of the connected components is the same as the number of time we call the DFS function.
  • Applications: Bipartite Graph Checking, Cycle finding, Connected Component.

Shortest Path Problem

• Dijkstra
  • single-source shortest path algorithm for weighted graph
  • Time complexity: $O(E\log V)$
  • Underlying data structure: priority-queue
• Floyd
  • multi-source shortest path algorithm
  • Dynamic programming
  • Use matrix representation for graph
  • Time complexity: $O(V^3)$
  • Example: classroom and pen (???)
• Bellmen-Ford
  • Used for graph with negative weight

Tree

• Minimum Spanning Tree
  • Kruskal
  • Prim’s