Guide to Competitive Programming

In this section, we first go through terminology which is used when discussing graphs and their properties. After this, we focus on data structures that can be used to represent graphs in algorithm programming.

Graph Terminology:

A graph consists of nodes (also called vertices) that are connected with edges. In this book, the variable n denotes the number of nodes in a graph, and the variable m denotes the number of edges. The nodes are numbered using integers 1, 2, . . . , n.
For example, shows a graph with 5 nodes and 7 edges.

A path leads from a node to another node through the edges of the graph. The length of a path is the number of edges in it. For example, shows a path 1 → 3 → 4 → 5 of length 3 from node 1 to node 5. A cycle is a path where the first and last node is the same. For example, shows a cycle 1 → 3 → 4 → 1.

A graph is connected if there is a path between any two nodes. The left graph is connected, but the right graph is not connected, because it is not possible to get from node 4 to any other node.

The connected parts of a graph are called its components. For example, the graph in three components: {1, 2, 3}, {4, 5, 6, 7}, and {8}.

A tree is a connected graph that does not contain cycles. Shows an example of a graph that is a tree.

In a directed graph, the edges can be traversed in one direction only. shows an example of a directed graph. This graph contains a path 3 → 1 → 2 → 5 from node 3 to node 5, but there is no path from node 5 to node 3.

In a weighted graph, each edge is assigned a weight. The weights are often interpreted as edge lengths, and the length of a path is the sum of its edge weights. For example, the graph in weighted, and the length of the path 1 → 3 → 4 → 5 is 1 + 7 + 3 = 11. This is the shortest path from node 1 to node 5.

Two nodes are neighbors or adjacent if there is an edge between them. The degree of a node is the number of its neighbors. Shows the degree of each node of a graph. For example, the degree of node 2 is 3, because its neighbors are 1, 4, and 5.

The sum of degrees in a graph is always 2m, where m is the number of edges, because each edge increases the degree of exactly two nodes by one. For this reason, the sum of degrees is always even. A graph is regular if the degree of every node is a constant d. A graph is complete if the degree of every node is n −1, i.e., the graph contains all possible edges between the nodes.

In a directed graph, the indegree of a node is the number of edges that end at the node, and the outdegree of a node is the number of edges that start at the node.

Basics-of-Graphs-Competitive-programming Basics-of-Graphs-Competitive-programming Basics-of-Graphs-Competitive-programming Basics-of-Graphs-Competitive-programming

Shows the indegree and outdegree of each node of a graph. For example, node 2 has indegree 2 and outdegree 1.

A graph is bipartite if it is possible to color its nodes using two colors in such a way that no adjacent nodes have the same color. It turns out that a graph is bipartite exactly when it does not have a cycle with an odd number of edges. For example, Shows a bipartite graph and its coloring.

Graph Representation:

There are several ways to represent graphs in algorithms. The choice of a data structure depends on the size of the graph and the way the algorithm processes it. Next we will go through three popular representations.

Adjacency Lists In the adjacency list representation, each node x of the graph is assigned an adjacency list that consists of nodes to which there is an edge from x.

Adjacency lists are the most popular way to represent graphs, and most algorithms can be efficiently implemented using them.
A convenient way to store the adjacency lists is to declare an array of vectors as follows:

Graph Representation

vector<int> adj[N];

The constant N is chosen so that all adjacency lists can be stored. For example, the graph in a can be stored as follows:

adj[1].push_back(2);
adj[2].push_back(3);
adj[2].push_back(4);
adj[3].push_back(4);
adj[4].push_back(1);

If the graph is undirected, it can be stored in a similar way, but each edge is added in both directions.
For a weighted graph, the structure can be extended as follows:

vector<pair<int,int>> adj[N];

In this case, the adjacency list of node a contains the pair (b,w) always when there is an edge from node a to node b with weight w. For example, the graph in b can be stored as follows:

adj[1].push_back({2,5});
adj[2].push_back({3,7});
adj[2].push_back({4,6});
adj[3].push_back({4,5});
adj[4].push_back({1,2});

Using adjacency lists, we can efficiently find the nodes to which we can move from a given node through an edge. For example, the following loop goes through all nodes to which we can move from node s:

for (auto u : adj[s]) {
// process node u
}

Adjacency Matrix An adjacency matrix indicates the edges that a graph contains.
We can efficiently check from an adjacency matrix if there is an edge between two nodes. The matrix can be stored as an array

int adj[N][N];

where each value adj[a][b] indicates whether the graph contains an edge from node a to node b. If the edge is included in the graph, then adj[a][b] = 1, and otherwise adj[a][b] = 0. For example, the adjacency matrix for the graph in a
adjacency matrix for the graph
.
If the graph is weighted, the adjacency matrix representation can be extended so that the matrix contains the weight of the edge if the edge exists. Using this representation, the graph in b corresponds to the following matrix:
corresponds graph matrix
The drawback of the adjacency matrix representation is that an adjacency matrix contains n2 elements, and usually most of them are zero. For this reason, the representation cannot be used if the graph is large.

EdgeList Anedge list contains all edges of a graph in some order. This is a convenient way to represent a graph if the algorithm processes all its edges, and it is not needed to find edges that start at a given node.

The edge list can be stored in a vector

vector<pair<int,int>> edges;

where each pair (a, b) denotes that there is an edge from node a to node b. Thus, the graph in a can be represented as follows:

edges.push_back({1,2});
edges.push_back({2,3});
edges.push_back({2,4});
edges.push_back({3,4});
edges.push_back({4,1});

If the graph is weighted, the structure can be extended as follows:

vector<tuple<int,int,int>> edges;

Each element in this list is of the form (a, b,w), which means that there is an edge from node a to node b with weight w. For example, the graph in b can be represented as follows:

edges.push_back({1,2,5});
edges.push_back({2,3,7});
edges.push_back({2,4,6});
edges.push_back({3,4,5});
edges.push_back({4,1,2});