Graphs

Graphs and graph algorithms are one of the most popular topics for interview questions. In this section, we will consider what graphs are, and how to represent one in the computer program.

Graph representation

Graphs are objects that consist of vertices (also called nodes) and edges. One typical intuitive example of a graph is the road network between cities:

In this example we have four vertices representing cities (Paris, Rome, London, Berlin), and four edges representing roads between the cities.

A lot of other real-life situations can be modeled as graphs. But how do we represent graphs in the computer program? There are several methods.

Adjacency matrix

First, it's more convenient to represent vertices as integer numbers. In our cities graph we have 4 cities, so we can number them with integers from 0 to 3:

Now we can represent our graphs as a 4x4 matrix:

int[][] graph = {
  {0, 1, 1, 0},
  {1, 0, 1, 1},
  {1, 1, 0, 0},
  {0, 1, 0, 0}
};

Here, graph[A][B] is 1 if there is an edge between vertices A and B, and 0 otherwise.

Adjacency lists

For a graph of size N, adjacency matrix will have a size of N², and will mostly consist of zeros if there are not too many edges in the graph.

Alternative, and more memory efficient representation of a graph is adjacency lists:

List<List<Integer>> graph = Arrays.asList(
    Arrays.asList(1, 2),
    Arrays.asList(0, 2, 3),
    Arrays.asList(0, 1),
    Arrays.asList(1)
);

Here, for a vertex A, Ath list in the graph will contain all vertices that are connected to A with an edge. For example, 2nd vertex is connected to the vertices 0 and 1. If some vertex was disconnected from the rest of the graph, it's adjacency list would be empty.

Adjacency lists keep only necessary information about the graph, are more memory efficient and are much more suitable for the real-life graphs.

Read more about graphs

There are many great resources about graphs. Here are some that I recommend:

• Introduction to Algorithms has in-depth study of graphs and algorithms on them.
• Competitive Programmer’s Handbook has nice chapters on graphs as well. Specifically, you can read a chapter about graph properties and graph representation there.
• CP-Algorithms.com has a lot of articles about both easy and hard graph algorithms.

Next steps

Next, let's learn some graph algorithms and solve some problems. The first one is a depth-first search algorithm, read about it here:

0 0 1 0 0 
0 0 1 1 1 
1 1 0 0 0 
0 1 0 0 1 
0 1 0 1 0