Graphs I - Basics of Graphs

Graphs are an essential idea in mathematics and computer science. It is an abstraction of any kind of connection between things. For example: relations between all your family members, peers and others is a graph (in technical terms, its called a social network), the connection between adjacent roads and streets is a graph. Because of how abstract the concept of graphs are, it can be applicable in many different scenarios. From GPS navigation to molecular biology, it is a very powerful tool for structuring a system where many components are related to each other in some way. In competitive programming, there are numerous problems that require knowledge of graphs and graph algorithms. In this article we will cover some basic graph representation and traversal concepts. But before we start with those, lets get familiar with some terminology.

Graphs are basically relations between things. Here, the thing is called a node or a vertex (vertices in plural) and a connection between two things is called an edge. The number of edges associated with a node is called its degree.

A sequence of edges connecting adjacent nodes is called a path. If a path loops back to its starting node, it’s called a cycle.

Typology

Graphs can be of many types depending on its structure or type of connection.

Directed and Undirected Graphs

Directed graphs are graphs where each edge has a direction. For example: the relation between a mother and her son is directed. Their relation to each other is not mutually equivalent.
Undirected graphs don’t have edges with directions. The relation between two friends could be seen as undirected, as they are both friends to each other.

Weighted and Unweighted Graph

Weighted graphs have a number associated with every edge. Internet connectivity can be considered weighted graphs as connections can have different bandwidths and latencies.
Unweighted graphs don’t have any associated number (or alternatively every edge has the same number). Again, social networks are a good example here.

Connected and Disconnected Graphs

Connected graphs are where every node can be reached from any other node following a path. Flight routes across the globe are a connected graph.
Disconnected graphs are where this does not hold true. If you consider each position in a chess game a node in a graph (this is actually a very useful method of thinking for games!), once you push a pawn, you cannot go back. Therefore, the graph of the game state is disconnected.

Trees

Trees are a special type of connected graph with N nodes and N-1 edges. This constraint causes trees to have some very special properties. For example, There are no loops in trees; as a result, each node has a unique path to any other node. This is why trees can be considered a separate topic of their own. We will not be covering trees in this article.

Graph is a vast topic that has been studied for centuries. This is only scratching the surface, but enough to get started.

Graph Representation

In code, graphs can be represented using matrices or adjacency lists. Each have their own advantages. But in general, adjacency lists are more commonly used.

#include<bits/stdc++.h>
using namespace std;
const int nodes = 1e5 + 5;
vector<int> adj[nodes];

To add undirected edge between nodes u and v, we would do

adj.push_back( make_pair(u, v) );
adj.push_back( make_pair(v, u) );

For a directed edge, we would only do the first.

Traversal

Graph traversal can be of two basic types.

Breadth-first Search

Here, we start from a node and sequentially visit adjacent nodes. We keep an array to track if a node was previously visited. This stops us from running into an infinite loop in graphs with loops. We also use a queue to maintain which nodes are to be processed. One connected component of a graph will be processed until the queue becomes empty.

vector<bool> visited(nodes);
queue<int> Q;

void bfs(int startNode) {
    // put start node into queue
    Q.push(startNode);
    while (!Q.empty()) {
        // get node to be processed
        int u = Q.front();
        // don't forget this or you'll get an infinite loop
        Q.pop();

        // has the node been visited before ?
        if (visited[u]) continue;
        // nahh we're good :)
        visited[u] = true;

        // go to adjacent nodes
        for (int v : adj[u]) {
            Q.push(v);
        }
    }
}

BFS algorithm can be used to calculate shortest distances.

Depth-first Search

In DFS, we pick a node and keep going to an adjacent node until we reach a point where all adjacent nodes have been visited, then we go back to the previous node and look for adjacent unvisited nodes. This may seem difficult to implement at first, but can be done quite easily with recursion.

void dfs(int u) {
    // node has been visited
    visited[u] = true;
    // look or unvisited adjacent nodes
    for (int v : adj[u]) {
        // if not visited
        if (!visited[v])
            dfs(v);
    }
}

Both of these algorithms have a time complexity of O(N + M). Where, N is the number of nodes and M is the number of edges.

These are fairly basic, but still very powerful. Advanced concepts in the graph algorithms are based on these two simple algorithms.

Practice Problems

Here are a short list of problems. When you’re out solving real problems, sometimes its good to consider, maybe the graph doesn’t have to be a data structure in your code to be able to traverse it. Good Luck!