# Graph

Graphs are usually stored in two ways - in a metric or in a set of nodes where each item has a references to a node it is connected with. Nice summary is in this [video](https://www.youtube.com/watch?v=WQ2Tzlxl_Xo).

## Adjacency Matrix

Directed graph. ![](https://1235041943-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3wXpaIhjJ_SlPm0Aby%2F-M3wY3XqBBucicplM4ZJ%2F-M3wYiLaTFtmcaGvU_1I%2FScreen%20Shot%202018-10-12%20at%2010.53.39%20PM.png?generation=1585858946934264\&alt=media)

```
```

For undirected graph, we can keep only one side of matrix (upper or lower).![](https://1235041943-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3wXpaIhjJ_SlPm0Aby%2F-M3wY3XqBBucicplM4ZJ%2F-M3wYiLc9mEn8rt2htxI%2FScreen%20Shot%202018-10-12%20at%2010.56.28%20PM.png?generation=1585858947707138\&alt=media)

```
```

Directed weighted graph. ![](https://1235041943-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3wXpaIhjJ_SlPm0Aby%2F-M3wY3XqBBucicplM4ZJ%2F-M3wYiLerOdSrUXzt2IZ%2FScreen%20Shot%202018-10-12%20at%2010.55.18%20PM.png?generation=1585858947462865\&alt=media)

```
```

## Adjacency List

Directed graph (we can store incoming or out-coming edges). ![](https://1235041943-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3wXpaIhjJ_SlPm0Aby%2F-M3wY3XqBBucicplM4ZJ%2F-M3wYiLghaE7q-ic3FeX%2FScreen%20Shot%202018-10-12%20at%2010.58.00%20PM.png?generation=1585858947812396\&alt=media)

```
```

Undirected graph, each edge is stored twice.![](https://1235041943-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3wXpaIhjJ_SlPm0Aby%2F-M3wY3XqBBucicplM4ZJ%2F-M3wYiLi-Xm86N6iPL6E%2FScreen%20Shot%202018-10-12%20at%2010.58.47%20PM.png?generation=1585858947587652\&alt=media)

```
```

Adjacency matrix is bad for sparse graphs and good for dense graphs. The opposite of adjacency list.