CODEWITHSUNDEEP
c++adjacency-matrix
Miss Jay
Miss Jay

Reputation: 35

Depth First Search with Adjacency Matrix

I am completing a class lab which takes an adjacency matrix, and determines connectivity among vertices. Although my code runs, it does not give the correct results.

I believe there is a problem with the the second if statement in my while loop. any help is greatly appreciated. Code is below:

#include "graph.h"
#include <assert.h>

using namespace std;

bool Graph::connected(int v,int w) {

    int visited[SIZE] ={0};

    if (v == w)         
        return adj_matrix[v][v];

    Queue<int> Q;      
    Q.Enqueue(v);      

    while (!Q.empty()) {
        int curr = Q.Dequeue();

        if (curr == w)
            return true;

        int z=0;         
        for (int i=0; i<SIZE; i++) {      
            if (adj_matrix[curr][z]==1 && visited[i]==false) {
                Q.Enqueue(z);
                visited[i]==true;
            }   
        }
    }
    return false;  
}

This is the output I am receiving:

0 0 1 0 
0 0 0 0 
0 0 0 0 
0 0 0 1 
vertex 0 is connected to vertices: 
vertex 1 is connected to vertices: 
vertex 2 is connected to vertices: 
vertex 3 is connected to vertices: 3

Which is clearly missing another connection between 0 and 2 correct?

Upvotes: 2

Views: 5897

Answers (2)

saurabh jindal
saurabh jindal

Reputation: 121

Also see that :

Q.Enqueue(z); visited[i]==true; (its having two "=") its wrong.

Change it to

Q.Enqueue(z); visited[i]=true;

And renmove the z altogether and use only i.

hey one more point: Do you want to implement 'Depth First", then why are you using Queue. Depth first uses stack. Please check once again, what you want to implement. Though for connectivity, both can be used.

Upvotes: 1

happydave
happydave

Reputation: 7187

Look closely at your use of the variables i and z. It appears that z is assigned the value 0, and never changed after that. You may want to try using more descriptive variable names to avoid this sort of confusion.

Upvotes: 1

Related Questions