# 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],[7],[6],[2]]

## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

- 1.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard