# An Introduction to Graphs

### Definitions

A graph is defined by its vertices (aka nodes) and edges: `G := (V, E)`

. A connected graph is one where there exists a path between any two vertices. Edges can have directions. A graph with directed edges is called a directed graph (or digraph).

A connected graph without cycles is called a tree. Most trees in computer science are rooted trees.

### Representations

The adjacency matrix representation of graph `G`

is defined to be a boolean matrix `M`

in which `M[i][j]`

equals 1 if and only if the i-th and j-th vertices are connected by an edge.

For example, the adjacency matrix representation of the following graph

is
`[[0,1,1],[1,0,1],[1,1,0]]`

.

The adjancency list representation of graph `G`

describes the neighbors of each vertex.

For example, the adjacency list representation of the following graph

is
`{'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b']}`

.

### Tradeoffs

First off, if a graph is dense, then adjacency matrix and adjacency list have similar performance. When dealing with a sparse graph, however, the two representations have their individual advantages and disadvantages.

If we want to obtain all neighbors of a node, then the adjacency list representation wins. If we want to check two nodes are connected, then the adjacency matrix representation wins.