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.

CommonLounge Archive