Guide to Competitive Programming

This section discusses two fundamental graph algorithms: depth-first search and breadth-first search. Both algorithms are given a starting node in the graph, and they visit all nodes that can be reached from the starting node. The difference in the algorithms is the order in which they visit the nodes.

Depth-First Search:

Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.

Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.

Shows how depth-first search processes a graph. The search can begin at any node of the graph; in this example we begin the search at node 1. First, the search explores the path 1 → 2 → 3 → 5, then returns back to node 1 and visits
the remaining node 4.

Implementation Depth-first search can be conveniently implemented using recursion.

The following function dfs begins a depth-first search at a given node. The function assumes that the graph is stored as adjacency lists in an array

vector<int> adj[N];

and also maintains an array
In some older compilers, the function make_tuple must be used instead of the braces (e.g., make_tuple(1,2,5) instead of {1,2,5}).

Graph Traversal- Competitive programming
Graph Traversal- Competitive programming

bool visited[N];
that keeps track of the visited nodes. Initially, each array value is false, and when the search arrives at node s, the value of visited[s] becomes true. The function can be implemented as follows:

void dfs(int s) {
if (visited[s]) return;
visited[s] = true;
// process node s
for (auto u: adj[s]) {
dfs(u);
}
}

The time complexity of depth-first search is O(n + m) where n is the number of nodes and m is the number of edges, because the algorithm processes each node and edge once.

Graph Traversal- Competitive programming

Breadth-First Search:

Breadth-first search (BFS) visits the nodes of a graph in increasing order of their distance from the starting node.

Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search. However, the breadth-first search is more difficult to implement than depth-first search.

Breadth-first search goes through the nodes one level after another. First the search explores the nodes whose distance from the starting node is 1, then the nodes whose distance is 2, and so on. This process continues until all nodes have been visited.

Shows how breadth-first search processes a graph. Suppose that the search begins at node 1. First the search visits nodes 2 and 4 with distance 1, then nodes 3 and 5 with distance 2, and finally node 6 with distance 3.

Implementation Breadth-first search is more difficult to implement than depth-first search, because the algorithm visits nodes in different parts of the graph. A typical implementation is based on a queue that contains nodes. At each step, the next node in the queue will be processed.

The following code assumes that the graph is stored as adjacency lists and maintains the following data structures:

queue<int> q;
bool visited[N];
int distance[N];

The queue q contains nodes to be processed in increasing order of their distance.
New nodes are always added to the end of the queue, and the node at the beginning of the queue is the next node to be processed. The array visited indicates which nodes the search has already visited, and the array distance will contain the distances from the starting node to all nodes of the graph.

The search can be implemented as follows, starting at node x:

connectivity of a graph

visited[x] = true;
distance[x] = 0;
q.push(x);
while (!q.empty()) {
int s = q.front(); q.pop();
// process node s
for (auto u : adj[s]) {
if (visited[u]) continue;
visited[u] = true;
distance[u] = distance[s]+1;
q.push(u);
}
}

Like in depth-first search, the time complexity of breadth-first search is O(n+m), where n is the number of nodes and m is the number of edges.

Applications:

Using the graph traversal algorithms, we can check many properties of graphs. Usually, both depth-first search and breadth-first search may be used, but in practice, depth-first search is a better choice, because it is easier to implement. In the applications described below we will assume that the graph is undirected.

Connectivity Check A graph is connected if there is a path between any two nodes of the graph. Thus, we can check if a graph is connected by starting at an arbitrary node and finding out if we can reach all other nodes.

For example, since a depth-first search from node 1 does not visit all the nodes, we can conclude that the graph is not connected. In a similar way, we can also find all connected components of a graph by iterating through the nodes and
always starting a new depth-first search if the current node does not belong to any component yet.

Cycle Detection A graph contains a cycle if during a graph traversal, we find a node whose neighbor (other than the previous node in the current path) has already been visited. For example, in Fig. 7.16, a depth-first search from node 1 reveals that the graph contains a cycle. After moving from node 2 to node 5 we notice that the neighbor 3 of node 5 has already been visited. Thus, the graph contains a cycle that goes through node 3, for example, 3 → 2 → 5 → 3.

Graph Traversal- Competitive programming

Another way to determine if a graph contains a cycle is to simply calculate the number of nodes and edges in every component. If a component contains c nodes and no cycle, it must contain exactly c − 1 edges (so it has to be a tree). If there are c or more edges, the component surely contains a cycle.

Bipartiteness Check A graph is bipartite if its nodes can be colored using two colors so that there are no adjacent nodes with the same color. It is surprisingly easy to check if a graph is bipartite using graph traversal algorithms.
The idea is to pick two colors X and Y , color the starting node X, all its neighbors Y , all their neighbors X, and so on. If at some point of the search we notice that two adjacent nodes have the same color, this means that the graph is not bipartite.

Otherwise the graph is bipartite and one coloring has been found. For example, a depth-first search from node 1 shows that the graph is not bipartite, because we notice that both nodes 2 and 5 should have the same color,
while they are adjacent nodes in the graph.

This algorithm always works, because when there are only two colors available, the color of the starting node in a component determines the colors of all other nodes in the component. It does not make any difference what the colors are.
Note that in the general case it is difficult to find out if the nodes in a graph can be colored using k colors so that no adjacent nodes have the same color. The problem is NP-hard already for k = 3.