GRAPH DFS & BFS, C++ (gcc)

GRAPH DFS & BFS

#include <bits/stdc++.h>
using namespace std;
#define MAX 7
struct Vertex{
    int data;
    bool isVisited;
};

stack<int> stk; 
queue<int> q;
vector<Vertex *> v;
int vCount=0;

int adjMat[MAX][MAX];

void addVertex(int data){
    Vertex* newV = new Vertex();
    newV->data = data;
    newV->isVisited = false;
    v.push_back(newV);
    vCount++;
}

void addEdge(int l, int r){
    adjMat[l][r] = 1;
    adjMat[r][l] = 1;
}

int getAdjacent(int idx){
    for(int i=0;i<vCount;++i){
        if(adjMat[idx][i]==1 && v[i]->isVisited==false){
            return i;
        }
    }
    return -1;
}

void displayDFS(){
    v[0]->isVisited = true;
    cout<<v[0]->data<<" ";
    stk.push(0);
    while(!stk.empty()){
        int adj = getAdjacent(stk.top());
        if(adj==-1){
            stk.pop();
        }
        else{
            cout<<v[adj]->data<<" ";
            v[adj]->isVisited = true;
            stk.push(adj);
        }
    }
    for(int i=0;i<vCount;++i){
        v[i]->isVisited = false;
    }
}
void displayBFS(){
    v[0]->isVisited = true;
    cout<<v[0]->data<<" ";
    q.push(0);
    
    int adj;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        while((adj = getAdjacent(temp)) != -1){
            v[adj]->isVisited = true;
            cout<<v[adj]->data<<" ";
            q.push(adj);
        }
    }
    
    for(int i=0;i<vCount;i++)
        v[i]->isVisited = false;
}
int main()
{
    addVertex(0);
    addVertex(1);
    addVertex(2);
    addVertex(3);
    addVertex(4);
    addVertex(5);
    addVertex(6);
    
    cout<<vCount<<endl;
    
    addEdge(0,1);
    addEdge(0,2);
    addEdge(0,3);
    addEdge(1,4);
    addEdge(2,4);
    addEdge(3,5);
    addEdge(4,6);
    addEdge(5,6);
    
    for(int i=0;i<vCount;i++){
        for(int j=0;j<vCount;j++)
            cout<<adjMat[i][j]<<" ";
        cout<<endl;
    }
    cout<<"\nDFS : ";
    displayDFS();
    cout<<"\nBFS : ";
    displayBFS();
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development