Lesson 2 of 17 · Graphs and trees

Graphs — BFS and DFS (Basics)


What are graphs and trees used for in practice?

When we meet graphs and trees for the first time, a natural question comes up: what is this actually for, and where is it used in practice?

Graphs and trees are not abstract concepts that exist only in the theory of algorithms. On the contrary, they are one of the most often used models for describing real-world problems, especially when there are several objects connected with one another.

A tree is a special case of a graph that has a hierarchical structure. This means that there is one starting node (the root), and all the other nodes branch out from it, without cycles and without links back.

Trees are used when we want to represent relations of the kind: parent – child, superior – subordinate or general – specific.

Let us imagine the menu structure of a website:

  • Home
  • Algorithms
    • Graphs
      • BFS
      • DFS
    • Sorting
  • Contact

This structure is a pure tree. Every page has its "parent", and the path to it is unique.

Exactly such structures are used in:

  • website navigation
  • menus in applications
  • organising files and folders

We use a graph when the relations between objects are not strictly hierarchical. In other words, when objects can be connected in several ways.

Examples of problems that are naturally modelled with graphs are:

  • a map of towns and the roads between them
  • social networks (users and their friendships)
  • computer networks
  • dependencies between tasks

When we have a graph or a tree, we often want to answer questions like:

  • Is there a path between two nodes?
  • What is the shortest path?
  • Which nodes can we reach?
  • In what order should we visit them?

This is where the algorithms BFS and DFS come in.

BFS is especially useful when we are looking for:

  • the shortest path (in the number of steps)
  • solutions level by level

DFS is useful when we want:

  • to explore one branch of a problem in detail
  • to check whether there is a cycle
  • to search through all possible solutions

In other words, graphs and trees let us translate real problems into a structure that algorithms can work on.

In the rest of the lesson we will see how BFS and DFS are applied to a concrete graph and why the same graph can give different traversal orders, depending on the algorithm we use.

A graph is a data structure made of nodes (vertices) and edges that connect those nodes. Graphs are used for modelling networks, roads, social connections, hierarchies and many real problems.

In algorithmics, knowing how to search graphs is the basis for more advanced topics: Dijkstra, MST algorithms, topological sorting, DP on graphs.



Representing a graph


The most common way in competitions is an adjacency list, because it is memory-efficient and allows fast processing.


vector<int> graph[100]; // for n nodes

// an example of adding an edge (an undirected graph):
graph[1].push_back(2);
graph[2].push_back(1);

Terminology:

  • directed graph – the edges have a direction (A → B)
  • undirected graph – the connections go both ways (A — B)
  • weighted graph – every edge has a value (e.g. the length of a road)
  • adjacency matrix – kept in the form of an n×n table (less practical)


To make it easier to understand the difference between the algorithms BFS (Breadth-First Search) and DFS (Depth-First Search), we will first define a concrete graph on which both algorithms will run.

The picture below shows a tree (a special case of a graph) with one starting node (the root) and several connected nodes. This graph will stay unchanged throughout the lesson — only the way the algorithms traverse it changes.

It is important to first see clearly the complete graph and all its connections, because this will help us later to follow, step by step, how BFS and DFS reach different traversal orders.

A visual display of a tree with the nodes A, B, C, D, E, F and G, used as an example for the BFS and DFS algorithms.
Figure 1. An example of a tree (graph) that we will use to explain BFS (breadth-first search) and DFS (depth-first search). The graph is the same for both algorithms — only the order in which the nodes are visited differs.

In the graph shown, node A is the starting node (the root of the tree). The nodes B, C and D branch out from it. Node B has further descendants E and F, while node D leads to node G.

We will use this graph as a reference from now on. No matter whether we apply BFS or DFS, the structure of the graph stays the same — the difference is only in the order in which the nodes are visited.

In the next picture we will see how this same graph is broken down step by step for both algorithms, with the traversal order and the flow of the search clearly marked.

BFS and DFS algorithms – breadth-first and depth-first graph search, step by step
Figure 2: BFS vs DFS — the difference, uses and examples in graphs

As the previous picture shows, BFS (breadth-first search) traverses the graph level by level. First all the nodes directly connected to the starting node are visited, and only then their descendants. This algorithm uses a queue to remember the nodes.

On the other hand, DFS (depth-first search) goes as deep as it can along one branch before it goes back and continues with the next branch. DFS is most often implemented with a stack or with recursion.

Exactly because of this difference in strategy, BFS and DFS give different traversal orders, even though they work on the same graph. Understanding this visualisation is the key to using these algorithms correctly in practice.

The adjacency matrix — another way to represent a graph


Besides an adjacency list, a graph can also be represented with an adjacency matrix. That is a two-dimensional array adj[n][n] where:

An example for an undirected graph with 4 nodes:


    0 1 2 3
0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 0 ]
3 [ 0 1 0 0 ]

When to use which representation?


Adjacency list Adjacency matrix
Efficient for sparse graphs (few edges) Good for dense graphs
Memory: O(V + E) Memory: O(V²)
Fast iteration through the neighbours A fast check whether an edge exists (O(1))

In competitive programming the adjacency list is used most often, because graphs are usually large, but with relatively few edges.

BFS — Breadth-First Search


When and why to use BFS


We use the BFS (breadth-first search) algorithm when we want to explore the nodes of a graph by levels, i.e. first all the nodes closest to the starting one, then the next ones and so on. This property is crucial when we look for the shortest path (in terms of the number of edges) between two nodes of a graph, which is a common need in real problems.

For example, let us imagine a problem:

  • In a maze we want to find the shortest path from the entrance to the exit.
  • In a social network we want to find the smallest number of steps between two users (how many "friendships" separate them).
  • In a computer network we explore which nodes are reachable in the minimum number of hops from the source node.
In such situations BFS first explores all the neighbours of the starting node, then their neighbours and so on, which lets it find the smallest number of moves whenever the graph has no weights on its edges.

BFS traverses the graph by levels. First it visits all the neighbours of the starting node, then their neighbours, etc.

It is used for finding the shortest path in an unweighted graph.

The implementation uses a queue.

A visual explanation of BFS traversal

Breadth-First Search (BFS) traverses a graph by levels. This means that it first visits all the nodes 1 step away, then all the nodes 2 steps away, etc.

An example graph:

        0
      /   \
     1     2
    / \     \
   3   4     5

If we start from node 0, the traversal goes by levels:

  • Level 0: 0
  • Level 1: 1, 2
  • Level 2: 3, 4, 5

0 → 1 → 2 → 3 → 4 → 5

That is why BFS guarantees that the first time we reach some node, we have reached it along the shortest path (by the number of edges).


Tracking the distances (the dist array)

To really find the shortest distance, we use the array dist.

  • dist[i] = -1 means that the node has not been visited yet
  • dist[start] = 0 because the starting node is 0 away from itself
  • For every neighbour:
    dist[neighbour] = dist[v] + 1

Since BFS traverses the graph by levels, the values in the dist array naturally grow level by level.


#include <bits/stdc++.h>
using namespace std;

vector<int> graph[100];
int dist[100];

void bfs(int start){
    queue<int> q;

    // Initialising the dist array
    for(int i = 0; i < 100; i++)
        dist[i] = -1;

    q.push(start);
    dist[start] = 0;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int neighbour : graph[v]){
            if(dist[neighbour] == -1){
                dist[neighbour] = dist[v] + 1;
                q.push(neighbour);
            }
        }
    }
}

A table of the states while BFS runs

The following table shows how the queue and the array of distances change while the algorithm runs on the example graph.

Step Node taken out State of the queue Dist array
Start - [0] [0, -1, -1, -1, -1, -1]
1 0 [1, 2] [0, 1, 1, -1, -1, -1]
2 1 [2, 3, 4] [0, 1, 1, 2, 2, -1]
3 2 [3, 4, 5] [0, 1, 1, 2, 2, 2]
4 3 [4, 5] [0, 1, 1, 2, 2, 2]
5 4 [5] [0, 1, 1, 2, 2, 2]
6 5 [] [0, 1, 1, 2, 2, 2]

We see that the values in the dist array grow level by level:

  • Node 0 has the distance 0
  • Nodes 1 and 2 have the distance 1
  • Nodes 3, 4 and 5 have the distance 2

The first time we reach a node, we have already found its shortest distance from the starting node. That is the key property of the BFS algorithm.


An example of building the graph

int main(){
    graph[0] = {1, 2};
    graph[1] = {0, 3, 4};
    graph[2] = {0, 5};
    graph[3] = {1};
    graph[4] = {1};
    graph[5] = {2};

    bfs(0);
    return 0;
}


A visual animation — BFS step by step

Below is a detailed display of how BFS goes through the graph level by level. We look at the graph from the previous example and start BFS from node 0.

The structure of the graph

        0
       / \
      1   2
     / \   \
    3   4   5

A table of how the BFS algorithm runs

Step Node taken out State of the queue Dist array Explanation
Start - [0] [0, -1, -1, -1, -1, -1] We put the starting node 0 into the queue and set dist[0] = 0.
1 0 [1, 2] [0, 1, 1, -1, -1, -1] We discover the neighbours 1 and 2. Their distance is 1.
2 1 [2, 3, 4] [0, 1, 1, 2, 2, -1] We discover 3 and 4. Their distance is 2.
3 2 [3, 4, 5] [0, 1, 1, 2, 2, 2] We discover 5. Its distance is 2.
4 3 [4, 5] [0, 1, 1, 2, 2, 2] No new nodes.
5 4 [5] [0, 1, 1, 2, 2, 2] No new nodes.
6 5 [] [0, 1, 1, 2, 2, 2] The queue is empty — BFS ends.

An explanation by levels

Level 0: node 0

Level 1: nodes 1 and 2

Level 2: nodes 3, 4 and 5

BFS traverses the graph by levels because it uses a queue (a FIFO structure). This means that all the nodes at distance 1 are processed before the nodes at distance 2, and all the nodes at distance 2 before those at distance 3, etc.

Why is the distance found the shortest one?

When we reach some node for the first time, we have reached it with the smallest possible number of edges.

The reason is that BFS:

  • First goes through all the shorter paths
  • Then moves on to the longer ones
  • Never comes back to a shorter path later

That is why BFS is the ideal algorithm for finding shortest paths in graphs without weights.

BFS with computing distances (the shortest path)


One of the most important uses of the BFS algorithm is finding the shortest distance from the starting node to all the other nodes in an unweighted graph.

We use the array dist, where:

  • dist[v] = the minimum number of edges from the starting node to the node v
  • At the start: we set all the values to -1 (the node has not been visited)
  • dist[start] = 0 because the starting node is 0 away from itself

Since BFS traverses the graph by levels, the first time we reach a node we have guaranteed found its shortest distance.


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {

    int n, m;
    cin >> n >> m;
    // n = the number of nodes in the graph
    // m = the number of edges

    // We create the adjacency list
    // adj[i] holds all the nodes connected to the node i
    vector<vector<int>> adj(n);

    // Reading all the edges of the graph
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        // u and v are the nodes the edge connects

        adj[u].push_back(v);
        // we add v to the neighbour list of the node u

        adj[v].push_back(u);
        // we add u to the neighbour list of the node v
        // remove this line if the graph is directed
    }

    // the starting node from which we compute the distances
    int start = 0;
    // the nodes are assumed to be indexed from 0 to n-1

    // dist[i] keeps the shortest distance from start to i
    vector<int> dist(n, -1);
    // -1 means that the node has not been visited yet

    queue<int> q;
    // the queue we use in the BFS algorithm

    dist[start] = 0;
    // the distance of the starting node from itself is 0

    q.push(start);
    // we put the starting node into the queue

    // the BFS loop
    while(!q.empty()) {

        int u = q.front();
        // we take the node from the front of the queue

        q.pop();
        // we remove it from the queue

        // we go through all the neighbours of the node u
        for(int v : adj[u]) {

            // if the neighbour has not been visited yet
            if(dist[v] == -1) {

                // its distance is the distance of u + 1
                dist[v] = dist[u] + 1;

                // we add it to the queue so that later
                // we visit its neighbours too
                q.push(v);
            }
        }
    }

    // Printing the results
    // we show the shortest distance from start to every node
    for(int i = 0; i < n; i++) {
        cout << "Distance from "
             << start
             << " to "
             << i
             << " is "
             << dist[i]
             << endl;
    }

    return 0;
}

If some node is still equal to -1 after the algorithm has run, it means that it is not reachable from the starting node (the graph is not fully connected).

A detailed explanation — BFS with computing distances

The BFS algorithm makes it possible to find the shortest distance from the starting node to all the other nodes in an unweighted graph.

Since all the edges have an implicit weight of 1, the shortest path means:

The path with the smallest number of edges.


What does the array dist represent?

We use the array dist[v], where:

  • dist[v] = the minimum number of edges from the starting node to the node v
  • At the start: all the values are -1 (the node has not been visited)
  • dist[start] = 0

The value -1 means that we have not reached that node yet.


An example graph

        0
       / \
      1   2
     / \   \
    3   4   5

We start BFS from node 0.


A visual table of the execution

Step Node taken out State of the queue dist array Level
Start - [0] [0, -1, -1, -1, -1, -1] 0
1 0 [1, 2] [0, 1, 1, -1, -1, -1] 1
2 1 [2, 3, 4] [0, 1, 1, 2, 2, -1] 2
3 2 [3, 4, 5] [0, 1, 1, 2, 2, 2] 2
4 3 [4, 5] [0, 1, 1, 2, 2, 2] --
5 4 [5] [0, 1, 1, 2, 2, 2] --
6 5 [] [0, 1, 1, 2, 2, 2] --

What do we notice?

  • Level 0 → node 0
  • Level 1 → nodes 1 and 2
  • Level 2 → nodes 3, 4 and 5

BFS traverses the graph by levels because it uses a queue (FIFO). First all the nodes at distance 1 are processed, then all the nodes at distance 2, etc.


Why is the first arrival at a node the shortest path?

When we reach the node v for the first time:

dist[v] = dist[u] + 1

This means that we reached it along the shortest possible path, because BFS never skips levels.

There is no way to find a shorter path later, since it would have to have fewer edges, and all the shorter paths have already been processed earlier.


An important note

If after the algorithm ends:

dist[i] == -1

it means that node i is not reachable from the starting node.


Time complexity

For a graph represented with an adjacency list:

O(n + m)

  • n — the number of nodes
  • m — the number of edges
  • m — the number of edges

The key property of the BFS algorithm

The first time we reach a node, we have already found its shortest distance.

This property holds only for unweighted graphs.

BFS on a grid (the maze problem)


A graph does not always have to be given explicitly. In problems with a matrix (e.g. a maze), we can look at every cell as a node, and moving to a neighbouring cell as an edge.

The allowed moves are: up, down, left and right. Every move is one edge (one step).

If a cell is marked with the character '.', we consider it passable. Other characters (e.g. '#') can be walls.

#include <iostream>
#include <queue>
using namespace std;

// The arrays are global: a matrix of 1000 × 1000 is too big
// for the local variables of main (stack overflow).
char grid[1000][1000];
// the matrix that represents the maze

int dist[1000][1000];
// dist[i][j] = the minimum number of steps
// from the starting cell to the cell (i,j)

int main() {

    int n, m;
    cin >> n >> m;
    // n = the number of rows of the matrix
    // m = the number of columns of the matrix

    // Reading the matrix and initialising the dist array
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> grid[i][j];
            // we read the character that represents the cell

            dist[i][j] = -1;
            // -1 means that the cell has not been visited yet
        }
    }

    // BFS uses a queue
    queue<pair<int,int>> q;

    // the starting position in the maze
    int startX = 0;
    int startY = 0;

    // the starting cell has the distance 0
    dist[startX][startY] = 0;

    // we put the starting cell into the queue
    q.push({startX, startY});

    // Moves in the 4 directions
    // index 0 → down
    // index 1 → up
    // index 2 → right
    // index 3 → left
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // The main BFS loop
    while(!q.empty()) {

        // we take the current cell from the queue
        auto [x, y] = q.front();
        // a C++17 structured binding:
        // x = row, y = column

        q.pop();

        // we check all 4 neighbouring cells
        for(int d = 0; d < 4; d++) {

            int nx = x + dx[d];
            int ny = y + dy[d];
            // nx, ny are the new cell

            // Checking whether we are inside the borders of the matrix
            if(nx >= 0 && nx < n && ny >= 0 && ny < m) {

                // If the cell is passable and has not been visited
                if(grid[nx][ny] == '.' && dist[nx][ny] == -1) {

                    // the distance is +1 step from the current cell
                    dist[nx][ny] = dist[x][y] + 1;

                    // we put the new cell into the queue
                    // so that we explore its neighbours later
                    q.push({nx, ny});
                }
            }
        }
    }

    return 0;
}

Since BFS goes through the cells by levels, dist[i][j] is the minimum number of steps needed to reach that cell from the starting position.

If some cell stays equal to -1, it means that it cannot be reached.

BFS on a grid is ideal for problems about the minimum number of steps. If a problem asks you to optimise a sum (e.g. the minimum sum of weights), dynamic programming or Dijkstra's algorithm is a better choice.

If you are interested in optimising a path through a grid (e.g. minimising a sum) instead of just the number of steps, see also Grid DP — dynamic programming on a matrix .

A visual example of a BFS search in a maze

Let us look at the following simple maze. The cell S is the starting position, . are passable cells, and # are walls.

S . . #
# . . #
# . . .
# # . E

The goal is to find the minimum number of steps from the starting cell S to every reachable cell in the maze.

After the BFS algorithm has run, the matrix of distances can look like this:

0 1 2 X
X 2 3 X
X 3 4 5
X X 5 6
  • 0 marks the starting cell
  • every number is the minimum number of steps from the starting position
  • X marks a wall or an unreachable cell

BFS goes through the cells by levels:

  • first all the cells 1 step away
  • then all the cells 2 steps away
  • then all the cells 3 steps away, etc.

That is why BFS always finds the shortest path in graphs without weights, which makes it the ideal algorithm for maze and grid problems.

Comparing BFS and DFS

Although both algorithms are used to traverse a graph, the way they work and their uses are different.

Property BFS DFS
Data structure Queue Stack / recursion
Way of traversal By levels In depth (goes as deep as possible)
Shortest path (unweighted graph) Yes Not guaranteed
Typical use Shortest path, minimum number of steps Connected components, cycles
Memory Can use more (keeps a level) Usually less

Intuitively:

  • BFS explores the "width" of the graph.
  • DFS explores the "depth" of the graph.

If your goal is the minimum number of steps — use BFS.
If your goal is to visit all the components or check for cycles — DFS is often the more natural choice.

DFS — Depth-First Search



When and why to use DFS


The DFS (depth-first search) algorithm uses the strategy of exploring one direction in the graph "to the end" before it goes back and explores other directions. This approach is especially useful when we want to:

  • check whether there is a path between nodes at all;
  • determine whether a graph contains a cycle;
  • find all the nodes that are part of the same connected component;
  • perform a topological sort when we work with directed acyclic graphs.
For example:
  • in a maze search problem, DFS can explore one path to the end and go back if it was a "dead end";
  • in a system of tasks with dependencies (e.g. compiling modules), DFS is used to determine the order in which the tasks can be done without breaking the dependencies.
This style of search emphasises depth, which can be useful when we are more interested in exploring a complete subgraph or structure than in finding the shortest path.

A step-by-step DFS simulation

We use the same graph as in the BFS example:

        0
      /   \
     1     2
    / \     \
   3   4     5

DFS goes as deep as possible before it goes back. Let us assume that we visit the neighbours in the order in which they are listed.

Start

We start from node 0.

Step 1

0 → we move to 1 (the first neighbour)

Step 2

1 → we move to 3

Step 3

3 has no new neighbours → we go back to 1

Step 4

From 1 we move to 4

Step 5

4 has no new neighbours → we go back to 1 → then to 0

Step 6

From 0 we move to 2

Step 7

2 → we move to 5

A possible traversal order:

0 → 1 → 3 → 4 → 2 → 5

We see that DFS goes deep through one branch before it goes back. Unlike BFS, it does not visit the nodes by levels.

DFS goes as deep as possible into the graph until it reaches the end, and then it goes back (backtracking) and continues the search from the previous node. The most common implementation of the DFS algorithm uses recursion, which means that the function calls itself for the neighbouring nodes.

DFS is often used for:

  • checking whether a graph is connected
  • finding cycles
  • topological sorting (directed graphs)
  • finding connected components
  • searching mazes, trees and other structures

// Including all the standard C++ libraries
#include <bits/stdc++.h>
using namespace std;

// The adjacency list of the graph
// graph2[i] holds all the nodes connected to the node i
vector<int> graph2[100];

// The array that marks whether a node has already been visited
// true  → the node has already been processed
// false → the node has not been visited yet
bool visited[100];

// The DFS function that traverses the graph starting from the node v
void dfs(int v){

    // We mark the current node as visited
    visited[v] = true;

    // We print the current node
    cout << v << " ";

    // We go through all the neighbours of the node v
    for(int neighbour : graph2[v]){

        // If the neighbour has not been visited yet
        // we call DFS recursively for that node
        if(!visited[neighbour])
            dfs(neighbour);
    }
}

Calling the function:

int main(){

    // Building an undirected graph by hand
    // Every node has a list of its neighbours
    graph2[1] = {2, 3, 4};
    graph2[2] = {1, 3};
    graph2[3] = {1, 2, 4};
    graph2[4] = {1, 3};

    // Starting the DFS algorithm from node 1
    // DFS will traverse the graph as deep as possible
    dfs(1);

    return 0;
}

Output:

1 2 3 4 


BFS vs DFS — a comparison


Property BFS DFS
Data structure Queue Recursion or a stack
Search order Level by level (the width of the graph) Goes as deep as possible, then goes back
Shortest path? YES (if the graph has no weights) NO
Time complexity O(V + E) O(V + E)
Example uses Shortest path, breadth search Topological sorting, cycles, components


Exercises and tasks


Try the following tasks:

  • Compute the distance (the number of steps) of every node from the starting one using BFS.
  • Count how many nodes there are in a connected component using DFS.
  • Determine whether a graph is connected.
  • Write a program that checks whether there is a cycle in an undirected graph.

This knowledge is the basis for the next topics, such as: Dijkstra's algorithm, MST (Kruskal and Prim) and topological sorting.



Detecting a cycle with DFS


One of the important uses of the DFS algorithm is detecting a cycle in a graph.

In an undirected graph a cycle exists if during the DFS traversal we come across an already visited node that is not the parent of the current node.

#include <iostream>
#include <vector>
using namespace std;

// The adjacency list of the graph
// adj[i] holds all the nodes connected to the node i
vector<vector<int>> adj;

// The array that marks whether a node has already been visited
vector<bool> visited;

// The variable that marks whether the graph contains a cycle
bool hasCycle = false;

// The DFS function
// u      - the current node
// parent - the node from which we came to the current node
void dfs(int u, int parent) {

    // We mark the current node as visited
    visited[u] = true;

    // We go through all the neighbours of the node u
    for(int v : adj[u]) {

        // If the neighbour has not been visited yet
        // we continue the DFS traversal
        if(!visited[v]) {
            dfs(v, u);
        }

        // If the neighbour has already been visited
        // and is not the parent of the current node,
        // then there is a cycle in the graph
        else if(v != parent) {
            hasCycle = true;
        }
    }
}

int main() {

    int n, m;
    // n - the number of nodes
    // m - the number of edges

    cin >> n >> m;

    // We create the adjacency list for n nodes
    adj.resize(n);

    // We initialise the array visited to false
    visited.assign(n, false);

    // Reading the edges of the graph
    for(int i = 0; i < m; i++) {

        int u, v;

        // we read the ends of the edge
        cin >> u >> v;

        // Since the graph is undirected,
        // we add the edge in both directions
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // We start DFS from every node
    // (needed if the graph is not connected)
    for(int i = 0; i < n; i++) {
        if(!visited[i])
            dfs(i, -1);
    }

    // Printing the result
    if(hasCycle)
        cout << "The graph contains a cycle\n";
    else
        cout << "The graph has no cycle\n";
}

In an undirected graph we must ignore the edge to the parent, because it does not form a cycle. When during the DFS traversal we come across an already visited node that is not the parent of the current node, it means that there is another path to that node, and so a cycle has been formed in the graph.

Detecting a cycle in an undirected graph with the DFS algorithm, where node B visits node C, which has already been visited and is not its parent, which shows that there is a cycle in the graph.
Figure 3: DFS cycle detection in an undirected graph: during the traversal from node B we find the already visited node C, which is not the parent, so there is a cycle in the graph.

Practice tasks — BFS and DFS


1. BFS — the shortest distance from the starting node

Task text

An undirected graph with n nodes is given. Using the BFS algorithm, compute the shortest distance (the number of edges) from the starting node s to all the other nodes in the graph.

Example

Input:
Graph:
1 - 2
1 - 3
2 - 4
3 - 4
Start = 1

Output:
dist[1] = 0
dist[2] = 1
dist[3] = 1
dist[4] = 2

2. BFS — checking whether a graph is connected

Task text

An undirected graph is given. Check whether the graph is connected.


3. DFS — the number of nodes in a connected component

Task text

An undirected graph and a starting node s are given. Using the DFS algorithm, compute how many nodes belong to the connected component that contains the node s.

Example


Input:
Graph:
1 - 2
2 - 3
4 - 5
Start = 1

Output:
Number of nodes in the component = 3


4. DFS — detecting a cycle in an undirected graph

Task text

An undirected graph is given. Determine whether the graph contains a cycle using the DFS algorithm.

Example


Input:
Graph:
1 - 2
2 - 3
3 - 1

Output:
The graph CONTAINS a cycle


Practical tasks (real problems) — BFS and DFS


5. The shortest route in a network of city roads (BFS)

Task text

A city is represented as an unweighted graph in which the nodes are crossroads, and the edges are two-way roads between them. N crossroads and a list of roads are given. Find the smallest number of roads you need to travel to get from the crossroads S to the crossroads T.

Example


Input:
5 6
1 2
1 3
2 4
3 4
4 5
2 5
S = 1, T = 5

Output:
2

Explanation:
The shortest route is 1 → 2 → 5 (two edges).


6. Evacuating an area – checking connectivity (DFS)

Task text

During a natural disaster, an area is divided into zones. The zones are connected by passages and represented as a graph. Check whether all the zones are reachable from the command centre (zone 1). If some zone is not reachable, the evacuation is not possible.

Example


Input:
6 4
1 2
2 3
3 4
5 6

Output:
NO

Explanation:
Zones 5 and 6 are not connected to zone 1.


Medium-difficulty tasks — BFS and DFS


7. BFS — reconstructing the shortest path (the parent array)

Task text

An undirected graph and two nodes s and t are given. Using the BFS algorithm, find the shortest path from the node s to the node t and print all the nodes on that path.

Example


Input:
Graph:
1 - 2
1 - 3
2 - 4
3 - 4
Start = 1
End = 4

Output:
1 2 4


8. DFS — the number of connected components

Task text

An undirected graph with n nodes is given. Using the DFS algorithm, compute the number of connected components in the graph.

Example


Input:
Graph:
1 - 2
2 - 3
4 - 5

Output:
Number of components = 2


Check your knowledge

Open the quiz

BFS and DFS

1. Which structure is used in BFS traversal?




2. What does BFS find in a graph in which all the edges have the same length?




3. What is the complexity of BFS and DFS with an adjacency list?




4. How are connected components counted?