Graph

A graph is a collection of nodes (also called vertices).

A graph is connected if there is a path between every distinct nodes.

Each node might point to another node. The edge can be directed or undirected.

Typical questions we can ask about a graph:

• Is there a path from one node to another?

There are two ways to represent graph:

• Adjacency List: every node stores a list of adjacent nodes
  • Use in BFS algorithm
• Adjacency Matrix:
  • N x N matrix where N is the number of nodes, and where matrix[i][j] is 1 iff node i and node j are connected
  • Undirected graph has symmetric adjacency matrix.

Resources

https://www.youtube.com/watch?v=zaBhtODEL0w