Day 31 | Graphs and BFS, DFS | C++

Welcome to Day 31, today we start learning graphs in computer science. But let's answer one question we must be asking

Why do we even need data structures?

Before answering why we need it, let's answer what is data structure.

Data Structure is a way to organize/store data, so that is convenient in the future to retrieve data back or perform some operations.

For example - You have a list of 100 items, and you need to declare 100 variables to store it. You can store these 100 items in a data structure called an array, which will solve the issue of maintaining and accessing 100 variables (image million variables, your yearly target will be to declare all variables LOL)

Similarly, there are other data structures that are helpful for other things.

1. Heaps - Maintaining minimum/maximum of a list with Insertion and Deletion in O(log(n))

2. Segment Trees - Querying, updating a range in the list in O(log(n)) time

3. Linked List - Easy Deletion in a linear data list

and many more

What are Graphs and where are they used?

Graphs are data structures with nodes and vertices. Consider graphs like any network for example cities as vertices and roads connecting them as edges.

For now, just understand that the directed arrow from A to B means we can go from A to B.

Now, we can answer many questions from this data

1. Can we go from any node to any other node

2. Distance between two nodes

3. Stuff Stuff

Some Important Terms

Vertices - In the above example, A, B, C, D, and E are vertices

Edges - In the above example paths A->B, B->C, A->D, and D->E are all edges

Directed Graph - Notice the above graph, vertices are directed from A->B, this means that we can go from A to B but not from B to A. These are called directed graphs. In directed graphs, you will be given an edge in the form {to, from}.

Undirected Graph -

In undirected graphs, there are only edges but not the direction. They are drawn without arrows in the visual representation

Here we can go from A to B as well as from B to A

How do we implement graph in code?

To implement a graph, you need to store two things

1. Number of vertices

2. All the edges

Now, note that an edge is just a tell we can go from A to B (and may B to A as well if undirected)

So if we store all the vertices we can go to, for each vertex. Then we can implement a graph.

This is called adjacency list implementation

Let's create vector<vector<int>> of size N (number of vertices)

1 - [2, 5, 4]

2 - [3, 1]

3 - [2]

4 - [1, 6]

5 - [1]

6 - [4]

Another way is create N x N matrix (let's say adj) and set adj[i][j] = 1, if we can from directly from i to j else it's 0. This is called adjacency matrix implementation

Above graph can be represented as

- 1 2 3 4 5 6

1 0 1 0 1 1 0

2 1 0 1 0 0 0

3 0 1 0 0 0 0

4 1 0 0 0 0 1

5 1 0 0 0 0 0

6 0 0 0 1 0 0

Graph Traversal

Traversal just means visiting all vertices of a graph. It is similar to for loop used to visit all indices of an array.

There are two major traversals (in other words, I know of 2 traversals)

1. Depth First Search | DFS

2. Breadth First Search | BFS

Depth First Search

Imagine this algorithm as going to any vertex you find next. Imagine that the graph is your family tree and it starts with your Grandfather.

You will find the next vertex to be someone among your father or his siblings. Once you go to that person, you will have the choice to go to that person's children. You are traveling in-depth, going as deep into a family as you can. That's why this is called a depth-first search

You can implement it like this

void dfs(int curr, vector<vector<int>> &graph, vector<bool> &vis){
    if(vis[curr])
        return;
    vis[curr] = true;
    for(int i: graph[curr]){
        dfs(i, graph, vis);
}

Breadth First Search

Using the same example as before, but imagine if you complete a generation first. That is first you visit everyone from your father's generation that is your father, your aunts and your uncles. Then you, your siblings and cousins are visited.

You are now first covered width (or breadth), hence called Breadth First Search.

You can implement it like this

void bfs(int start, vector<vector<int>> &graph){
    list<int> in_queue; // Not using queue here because not yet discussed             
                        // in blogs, but use queue if you know about it
    vector<bool> visited ( graph.size() );
    in_queue.push_back(start);
    visited[start] = true;
    while(in_queue.size()){
        int u = in_queue.front();
        in_queue.pop_front();
        for(int v : graph[u]){
            if(visited[v])continue;
            visited[v] = true;
            in_queue.push_back(v);
        }
    }
}

Let's solve a problem

Sample Test Case -

Input:
3
6
1 2 3 4
2 2 3 6
3 2 1 2
4 1 1
5 0
6 1 2
5 1
1 0
1 0
0 0
10
1 6 3 5 6 7 8 9
2 1 9
3 2 1 5
4 5 6 7 8 9 10
5 4 1 3 7 8
6 3 1 4 7
7 5 1 4 5 6 8
8 5 1 4 5 7 10
9 3 1 2 4
10 2 4 8
7 1
1 0
2 1
4 1
7 1
0 0
2
1 0
2 0
1 1
0 0
Output:
graph 1
5
1 3 2 6 4
1 3 2 6 4
graph 2
7 1 4 5 6 8 3 9 10 2
1 3 5 7 4 6 8 10 9 2
2 9 1 4 3 5 6 7 8 10
4 6 7 8 9 10 1 5 2 3
7 1 4 5 6 8 3 9 10 2
graph 3
1

We will try this problem.

This problem is exactly what we have discussed above.

A few tips -

1. Spend a good amount of time understanding how is input and how is output

2. Use C++14 (GCC) unless you specifically know you want clang.

We can implement the solution like this

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


void dfs(int curr, vector<vector<int>> &graph, vector<bool> &vis){
    if(vis[curr])
        return;
    cout << curr << " ";
    vis[curr] = true;
    for(int i: graph[curr]){
        dfs(i, graph, vis);
    }
}

void bfs(int start, vector<vector<int>> &graph){
    list<int> in_queue; // Not using queue here because not yet discussed             
                        // in blogs, but use queue if you know about it
    vector<bool> visited ( graph.size() );
    in_queue.push_back(start);
    visited[start] = true;
    while(in_queue.size()){
        int u = in_queue.front();
        cout << u << " ";
        in_queue.pop_front();
        for(int v : graph[u]){
            if(visited[v])continue;
            visited[v] = true;
            in_queue.push_back(v);
        }
    }
}

void solve(int test_case){
    int n;
    cin >> n;
    vector<vector<int>> g(n+1);
    cout << "graph " << test_case << "\n";
    for(int i = 1; i <= n; i++){
        int v, sz;
        cin >> v >> sz;
        for(int j = 0; j < sz; j++){
            int x;
            cin >> x;
            g[i].push_back(x);
        }
    }
    while(true){
        int v, type;
        cin >> v >> type;
        // printf("v = %d, type = %d\n", v, type);
        if(v == 0 && type == 0){
            // As mentioned in problem
            break;
        }
        if(type == 0){
            vector<bool> vis(n+1,false);
            dfs(v,g,vis);
            cout << "\n";
        }else{
            bfs(v,g);
            cout << "\n";
        }
    }

}

int main(){
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
}