Question

-DFS and BFS implementations in the lecture slides ar e based on an input adjacency list of a graph. Modify each of the codes so that the DFS and BFS ca n be performed on an input adjacency matrix. • Submit the modified codes as well as a report including the d escription and screenshots

Answer 1

// Below is dfs code

#include<bits/stdc++.h>

using namespace std;

// Below is dfs implementation of dfs function

void dfs(int **a,bool *vis,int n,int k){

    // Displaying the first element

    cout<<k<<" ";

    // Making that element as visited

    vis[k]=true;

    // Looping through each node and calling dfs function again if it is not visited    

    for(int i=0;i<n;i++){

        if(a[k][i] && !vis[i]){

            dfs(a,vis,n,i);

        }

    }

}

int main(){

    int n,**a;

    cout<<"Enter number of vertices\n";

    cin>>n;

    a=new int* [n];

    for(int i=0;i<n;i++)

        a[i]=new int[n];

    // Below we are taking input of the adjacency matrix

    cout<<"Enter the adjacancy matrix,1 for an edge, 0 for no edge\n";

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){

            cin>>a[i][j];

        }

    }

    cout<<"DFS\n";

    // Below we created a bool type array to keep track of visited node

    bool vis[n];

    // Below we are initializing it to 0.

    memset(vis,false,sizeof(vis));

    // Below we are calling dfs function with input adjacency matrix and other values.

    dfs(a,vis,n,0);

    cout<<endl;

    return 0;

}

output

/////////////////////////////////////////////////////////

Below is the result of bfs ...

#include<bits/stdc++.h>

using namespace std;

// Below is dfs implementation of dfs function

void bfs(int **a,int n){

    // Below we are creating an queue.

    queue<int> q;

    q.push(0);

    bool vis[n];

    memset(vis,false,sizeof(vis));

    // making first element visited

    vis[0]=1;

    while(!q.empty()){

        int f=q.front();

        // printing first element

        cout<<f<<" ";

        for(int i=0;i<n;i++){

            if(a[f][i] && !vis[i]){

                q.push(i);

                vis[i]=true;

            }

        }

        // removing that element from the queue.

        q.pop();

    }

    cout<<endl;

}

int main(){

    int n,**a;

    cout<<"Enter number of vertices\n";

    cin>>n;

    a=new int* [n];

    for(int i=0;i<n;i++)

        a[i]=new int[n];

    // Below we are taking input of the adjacency matrix

    cout<<"Enter the adjacancy matrix,1 for an edge, 0 for no edge\n";

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){

            cin>>a[i][j];

        }

    }

    cout<<"BFS\n";

    // Below we are calling bfs function with input adjacency matrix and other values.

    bfs(a,n);

    return 0;

}

// output