# Introduction to Graphs (and how to represent them)

December 27, 2016

I recommend watching the following videos for learning about graphs. These are really well made videos and he covers a lot in these short videos, so if you feel overwhelmed, use the rewind and pause buttons.

# Introduction to Graphs

What are graphs? What are different types of graphs (directed and undirected, trees and DAGs, etc)? And examples of using them to model web links, flights between cities, and other things.

# How to represent graphs?

How to store (or represent) a graph in code? i.e. adjacency list and adjacency matrix. When do you use one vs the other?

# Implementation

## 1. Adjacency matrix

The following c++ code represents a graph as **adjacency matrix**. The complexity of building the graph is O(m) where m is the number of edges in the graph.

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
// Number of nodes
n = 6;
// Number of edges
m = 5;
int adj_matrix[n][n];
// Initialising all values equal to 0
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
adj_matrix[i][j] = 0;
}
/*
We will be adding the
following 5 edges.
(0,1), (0,2), (0,3),
(2,4), (4,1)
*/
pair<int, int> edges[] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 1}};
for (int i = 0; i < m; i++)
{
int x = edges[i].first;
int y = edges[i].second;
adj_matrix[x][y] = adj_matrix[y][x] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cout << adj_matrix[i][j] << " ";
cout << endl;
}
return 0;
}
```

Following is the code in python to represent a graph as an adjacency matrix.

```
n = 5
# initialising a nxn matrix with 0
adj_matrix = [[0]*n for _ in range(n)]
# adding the following edges
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (4, 1)]
for i in range (0, 5):
x = edges[i][0]
y = edges[i][1]
adj_matrix[x][y] = 1
adj_matrix[y][x] = 1
print(adj_matrix)
```

If we are given an edge x→y in a directed graphs, we will only make one edge x→y by `adj_matrix[x][y] =1`

and **not** `adj_matrix[y][x] = 1`

.

If we are given a weight w_{x,y} corresponding to the edge connecting x and y, then denote the weight by `adj_matrix[x][y] = w`

.

Similarly, you can think in the case of both directed and weighted graph.

## 2. Adjacency List

The following c++ code represents a graph as **adjacency list**. The complexity of building the graph is O(m) where m is the number of edges in the graph.

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
// Number of nodes
n = 6;
// Number of edges
m = 5;
vector<int>adj_list[n];
/*
We will be adding the
following 5 edges.
(0,1), (0,2), (0,3),
(2,4), (4,1)
*/
pair<int, int> edges[] = {{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 1}};
for (int i = 0; i < m; i++)
{
int x = edges[i].first;
int y = edges[i].second;
// As graph is undirected
adj_list[x].push_back(y);
adj_list[y].push_back(x);
}
for (int i = 0; i < n; i++)
{
cout << "Edges connected to " << i <<" vertex are: ";
for (int j = 0; j < adj_list[i].size(); j++)
cout << adj_list[i][j] << " ";
cout << endl;
}
return 0;
}
```

The code in python is as follows:

```
from collections import defaultdict
graph = defaultdict(list)
# adding the following edges
edges = [(0, 1), (0, 2), (0, 3), (2, 4), (4, 1)]
for i in range (0, len(edges)):
x = edges[i][0]
y = edges[i][1]
graph[x].append(y)
graph[y].append(x)
print(graph)
```

If we are given an edge x→y in a directed graphs, we will only make one edge x→y by `adj_list[x].push_back(y)`

.

If we are given a weight w_{x,y} corresponding to the edge connecting x and y, then we store both the pair, the neighbouring vertex and the weight. This can be done easily in python, and few modifications in cpp as given below. Here, we add the directed edge connecting 1 and 2 with weight 199.

```
vector< pair<int, int> >weighted_list[5]; // Neighbour, weight
weighted_list[1].push_back({2, 199}); // Neighbour, weight
```

In the next few tutorials, we will understand that both the representations have an important role under different constraints.

# Further reading

The following text tutorials on csacademy are quite simple and high quality. Here are the links: Introduction to graphs and Graph Representation.