# Graph Data Structure

A graph is a data structure that stores data in nodes that are connected to each other.
Graphs are useful to represent relationships between entities.
Here is a simple example of a graph: For example, a social network like LinkedIn can be modeled after a graph, where users are connected to eachother. Some users are first degree connections, second degree, or not connected at all.

## Graph Terminology

Let's use this graph to define some common graph terminology.
Each node, or vertex, in the graph contains a number. In no particular order, the graph above contains the following vertices:
`V = [6, 4, 2, 9, 7]`
The lines that connect each node are called edges. The following is a list of edges in the same graph:
`E = [ (6, 4), (6, 2), (6, 9), (2, 7) ]`
Sometimes, graph edges may have weights, which indicates some sort of cost to from from one node to another.
Vertices are adjacent to eachother if they are connected via an edge.
We can say that the node with `6` is adjacent to the node with `4`.
Finally, a path exists between two nodes, or vertices, if there are a set of edges that connect them.
For example, there exists a path from node `4` to node `9`: `[4, 6, 9]`

## Graph representation

There are a few ways to represent a graph in code.

### 1. Adjacency Matrix

Given a graph with `V` vertices, we can represent the graph with a `V x V` matrix.
Each item in the matrix at `(i, j)` represents if there is an edge that exists between node `i` and node `j`.
If the edge exists, the value is `1`. While the value `0` indicates that there is no edge.
Here's the adjacency matrix for our example graph. ### 2. Adjacency List

As you can tell, an adjacency matrix isn't very storage efficient, especially when the number of edges is small, or sparse. For example, the edge between `4` and `6` is stored in 2 places in our matrix: `(0, 2)` and `(2, 0)`.
An adjacency list is a collection of unordered lists, where each list tracks a single node's neighbors.
Using the same graph as an example, here is what the adjacency list looks like: In an adjacency list, each list can be either an array or linked list, where the head is the node that the list represents, and the connected nodes are its edges (or neighbors).
Now if the graph is sparse, we save space as we only store edges that exist.
In Python, that adjacency list `A` for the vertices `V` looks something like this:
`V = [6, 4, 2, 9, 7]A = [        [4, 2, 9],        [6, 2],        ,        ,        ]`

## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.
1. 1.Inorder TraversalEasy
2. 2.Tree SumEasy
3. 3.Tree HeightEasy
4. 4.LCAMedium
5. 5.Max Path SumHard
6. 6.Search mazeMedium
7. 7.Number of islandsMedium
8. 8.Kth SmallestMedium
9. 9.Sort K ArraysHard

## Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.