undirected_graph.cpp

// Undirected & non weighted GRAPH
// O(n+m) time complexity
// vertices start from 1 onwards
#include <bits/stdc++.h>
using namespace std;

class Graph{
    int vertices;
    vector<int>*adj;
    bool *visited;
public:
    Graph(int v);
    ~Graph(){
        delete [] adj;
        delete [] visited;
        cout<<"\n";
    }
    void addedge(int a,int b);
    void visit_false();
    void dfs(int s);
    void bfs(int s);
};
Graph::Graph(int v){
    vertices=v;
    adj=new vector<int>[v];
    visited=new bool[v];
}
void Graph::addedge(int a,int b){
    adj[a].push_back(b);
    adj[b].push_back(a);
}
void Graph::visit_false(){
    for(int i=0;i<vertices;i++){
        visited[i]=false;
    }
}
void Graph::dfs(int s){
    if(visited[s]){
        return;
    }
    cout<<s+1<<" ";
    visited[s]=true;
    for(auto u: adj[s]){
        dfs(u);
    }
}
void Graph::bfs(int s){
    queue<int>q;
    q.push(s);
    visited[s]=true;
    int distance[vertices];
    distance[s]=0;
    cout<<s+1<<" ";
    while(!q.empty()){
        s=q.front();
        q.pop();
        for(auto u:adj[s]){
            if(!visited[u]){
                visited[u]=true;
                distance[u]=distance[s]+1;
                cout<<u+1<<" ";
                q.push(u);
            }
        }
    }
    cout<<"\n\ndistance of nodes from source:\n";
    for(int i=0;i<vertices;i++){
        cout<<i+1<<" : "<<distance[i]<<"unit\n";
    }
}

int main() {
    int vertices,edges;
    cout<<"Enter no of vertices & edges\n";
    cin>>vertices>>edges;
    Graph g(vertices);
    cout<<"Enter pair of adjacent vertices\n";
    for(int i=0;i<edges;i++){
        int a,b;
        cin>>a>>b;
        g.addedge(a-1,b-1);
    }
    cout<<"dfs from source "<<1<<"\n";
        g.visit_false();
        g.dfs(0);
    cout<<"\n\nbfs from source "<<1<<"\n";
        g.visit_false();
        g.bfs(0);
	return 0;
}