Algorithm Graph DFS(Depth First Search)

 

Bismillahir Rahmanir Rahim

A graph is said to be connected if there is a path between every pair of vertex. From every vertex to any other vertex, there should be some path to traverse. That is called the connectivity of a graph. A graph with multiple disconnected vertices and edges is said to be disconnected.

Connected Graph

Disconnected Graph

We can check graph connectivity through dfs algorithm.

Depth first Search or Depth first traversal is a recursive algorithm for searching all the vertices of a graph or tree data structure. 

Traversal means visiting all the nodes of a graph.

Starting from 1 traverse like that 1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 7

DFS Code is given below.

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+9;

vector<int>g[N];

bool vis[N];

void dfs(int node)

{

    vis[node]=true;

    for(int i=0; i<g[node].size(); i++)

        if(!vis[g[node][i]])

            dfs(g[node][i]);

}

int main()

{

    int node,edge,a,b;

    cin>>node>>edge;

    while(edge--)

    {

        cin>>a>>b;

        g[a].push_back(b);

        g[b].push_back(a);

    }

    dfs(1);

    for(int i=1; i<=node; i++)

        if(!vis[node])

        {

            cout<<"Disconnected"<<endl;

            return 0;

        }

    cout<<"Connected"<<endl;

    return 0;

}

Time Complexity of DFS = O(V+E) where V is vertices and E is edges.