Jose Ortiz Jose Ortiz - 2 months ago 31
C++ Question

DFS implementation in c++ using adjacency list (using <vector> and linked list)

I have made an Adjacency list using and a linked list. Inside the struct for node, I have data, next and visited. When I try setting visited to true in the DFS function, The algorithm does not work correctly. It only works when I create a new array storing the boolean values and using that array for the dfs algorithm. I need help getting the member visited of the vertex struct to work. I am not sure why it does not work.

Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include <vector>

class Graph{
private:
struct vertex{
int data;
bool visited;
struct vertex* next;
};

struct adjList
{
struct vertex *head;
};

int V;
bool visited[100];
std::vector<adjList> G;
public:
Graph(int vertices);
vertex* addVertex(int data);
void addEdge(int index, int data);
void dfs(int vertex);
void printGraph();
};

#endif


Graph.cpp

#include "Graph.h"
#include <iostream>
#include <cstdlib>
using namespace std;

Graph:: Graph(int vertices){
this->V=vertices;
for(int i=0; i<V; i++){
//allocating space in G for V amount and using constructor of struct
G.push_back(adjList());
visited[i]=false;
}
}
//create a node
Graph:: vertex* Graph::addVertex(int data){
struct vertex* newNode= new vertex;
newNode->data= data;
newNode->next= NULL;
newNode->visited=false;
return newNode;
}
//add an Edge to the list
void Graph:: addEdge(int index, int data){
struct vertex* cursor= G[index].head;
while(cursor){
if(cursor->data==data)
return;
cursor= cursor->next;
}
struct vertex* newVertex= addVertex(data);
newVertex->next = G[index].head;
G[index].head= newVertex;
// this is undirected graph, so we are adding an edge from data to index;
newVertex = addVertex(index);
newVertex->next= G[data].head;
G[data].head= newVertex;
}
// dfs algorithm
void Graph::dfs(int vertex){
cout<<vertex<<", ";
G[vertex].head->visited = true;
visited[vertex]=true;
struct vertex* cursor = G[vertex].head;
while(cursor!=NULL){
vertex=cursor->data;
if(visited[vertex]==false)
dfs(vertex);
cursor= cursor->next;
}
}

void Graph::printGraph(){
for(int i=0; i<V; i++){
struct vertex* cursor= G[i].head;
cout<<"vertex: "<<i<<endl;
while(cursor!=NULL){
cout<<"->"<<cursor->data;
cursor=cursor->next;
}
cout<<endl;
}
}

int main(){
Graph Graph(5);
Graph.addEdge(0,1);
Graph.addEdge(0,4);
Graph.addEdge(1,2);
Graph.addEdge(1,3);
Graph.addEdge(1,4);
Graph.addEdge(2,3);
Graph.addEdge(3,4);

Graph.printGraph();
Graph.dfs(0);
return 0;
}

Answer

Clean up your data structures first, you are bending them in favour of your algorithm too early, which back fires with a bit of mess. Make sure you have some solid "model" first, without any algorithm in mind, then check what an algorithm needs, and add it either as local temporary inside algorithm, or some cached/extended data added to model. But keep the core model under it.

What I mean, let me show you super inefficient, but simple implementation of your DFS in hopefully something what can be considered "modern C++" (but I'm not expert either):

live demo at: http://cpp.sh/9fyw

#include <iostream>
#include <vector>
#include <string>

/**
 * Super naive and inefficient (but simple) implementation of Depth-first-search of graph
 * Just to show basic usage of std::vector, and how it helps to avoid new/delete
 **/

struct Vertex {
    // nothing at the moment
};

struct Edge {   // One-way edge, to make things intentionally harder
    size_t fromIndex, toIndex;

    Edge(const size_t _fromIndex, const size_t _toIndex)
        : fromIndex(_fromIndex), toIndex(_toIndex) {}
};

class Graph {
    std::vector<Vertex> vertices;
    std::vector<Edge> edges;

public:
    Graph(const size_t expectedVerticesCount = 20, const size_t expectedEdgesCount = 50) {
        if (expectedVerticesCount) vertices.reserve(expectedVerticesCount);
        if (expectedEdgesCount) edges.reserve(expectedEdgesCount);
    }

    void clear() {
        vertices.clear();
        edges.clear();
    }

    void initVertices(const size_t newVertexCount) {
        // A bit pointless function to set vertices, as vertices have no data
        // Storing the count itself inside Graph would suffice,
        // but let's demonstrate vector usage a bit more with N empty vertices
        clear();    // removes old vertices + edges
        vertices.resize(newVertexCount);
    }

    void addEdgeBiDirectional(const size_t v1Index, const size_t v2Index) {
        if (vertices.size() <= v1Index || vertices.size() <= v1Index) {
            std::cout << "Ups, unexpected vertex in edge: "
                << v1Index << " <-> " << v2Index << "\n";
            return;
        }
        if (v1Index == v2Index) {
            std::cout << "Ups, loop at vertex: " << v1Index << " - ignored\n";
            return;
        }
        // Add two one-way edges, to make this edge work in both directions
        edges.push_back(Edge(v1Index, v2Index));
        edges.push_back(Edge(v2Index, v1Index));
    }

    void printGraph() {
        for (size_t i = 0; i < vertices.size(); ++i) {
            std::cout << "Vertex " << i << " has edges to:";
            for (const auto & edge : edges) {
                if (edge.fromIndex == i) std::cout << " " << edge.toIndex;
            }
            std::cout << "\n";
        }
    }

private:
    void dfs(std::vector<size_t> & result, std::vector<bool> & visited, size_t v) {
        // It's important to pass vectors as references here (that "&")
        // so you don't fill stack space too quickly, and the modifications
        // done to them inside are propagated up into final result.
        // Without "&" a local copy of vector would be created.
        if (visited[v]) return;
        result.push_back(v);
        visited[v] = true;
        for (const auto edge : edges) {
            if (edge.fromIndex != v) continue;
            dfs(result, visited, edge.toIndex);
        }
    }

public:
    // Returns vector with vertex indices found
    std::vector<size_t> dfs(const size_t vertexIndex) {
        if (vertices.size() <= vertexIndex) {
            std::cout << "DSF: Ups, invalid starting vertex: "
                << vertexIndex << "\n";
            return std::vector<size_t>();
        }

        std::vector<bool> visited(vertices.size());
        std::vector<size_t> result;
        result.reserve(vertices.size());
        dfs(result, visited, vertexIndex);
        return result;
    }
};

int main()
{
    Graph g;
    // fill up graph data
    g.initVertices(5);
    g.addEdgeBiDirectional(0,1);
    g.addEdgeBiDirectional(0,4);
    g.addEdgeBiDirectional(1,2);
    g.addEdgeBiDirectional(1,3);
    g.addEdgeBiDirectional(1,4);
    g.addEdgeBiDirectional(2,3);
    g.addEdgeBiDirectional(3,4);
    // Show the validation works
    g.addEdgeBiDirectional(1,1);
    g.addEdgeBiDirectional(5,4);

    g.printGraph();

    auto dfsResult = g.dfs(2);
    std::cout << "DFS for 2 result:";
    for (const auto v : dfsResult) std::cout << " " << v;
    std::cout << "\n";
}

(now I realised, my "addEdge" doesn't prevent from duplicate edge addition, like yours, consider it bug or feature)


If you check it, you will see the performance is bad, because it's searching all edges every time. How to help it? To have already prepared neighbours data for each vertex.

struct Vertex {
    std::vector<size_t> adjacency;
};

Then in Graph you can set the adjacent vertex for each added edge:

void addAdjacency(const size_t v1Index, const size_t v2Index) {
    auto & adjacency = vertices[v1Index].adjacency;
    if (adjacency.end() != std::find(adjacency.begin(), adjacency.end(), v2Index)) return;
    adjacency.push_back(v2Index);
}

void addEdgeBiDirectional(const size_t v1Index, const size_t v2Index) {
    ...
    addAdjacency(v1Index, v2Index);
    addAdjacency(v2Index, v1Index);
}

Live demo: http://cpp.sh/4saoq

Now it's lot more efficient (as far as depth-first can be efficient, Breadth-first search would be lot more easier to write without recursion using lot of stack space).

But if the DFS and printGraph was your only goal, then this can be refactored by removing the edges completely, and keeping only vertices and inside them adjacency. You can try it on your own, you will see it will take only few changes.

But the visited field stays as temporary owned by the dfs, IMO that's the best-fit how to use it.


This is already so long, and took so long, that I'm not in mood to show you something with pointers, new and delete. Showing you how to avoid them is probably still of more benefit, at least until you can produce similar or better code on your own.

Learning the naked pointer/new/delete stuff is important too, but ... check some tutorial?

At least one hint "when to delete": In modern C++ you can think in the scope. Like everything belongs somewhere (in some scope), and then it's released, upon exiting the scope. By thinking this way, you just implement constructor+destructor in your classes, and you are done with clean-up.

Like the Graph g; in my example being local variable of main, thus in it's scope. When main is being exited, the destructor of g is called (which I didn't write, as the default destructors are created by compiler to call the vertices and edges destructor, and the Vertex destructor gets called by vector destructor, which implicitly calls adjacency destructor. So everything is released, no memory leak.

If I would use some new in Graph trough it's life cycle (either in constructor, or in some function), either I would put the pointer in some Graph member variable, and write explicit destructor checking that for non-nullptr value, and delete it, or delete it sooner in some function (and set the storage to nullptr to avoid double delete on the same pointer).

So if you make sure your design of classes makes sense, and everything belongs in some reasonable scope, you then use new/delete paired by constructor/destructor, and you know the clean-up happens upon exiting the scope, which did own (was responsible) for that piece.

There are other techniques, how to pass pointers (or any resource actually) around from the original owner to other classes ... generally I would try really hard to avoid that, but if you really insist on such application structure, you can use things around std::unique_ptr. But this design is a bit harder to keep clean, and to track down responsibility/ownership of particular memory or resource. Watch for example this video for some ideas how to deal with it in somewhat elegant way.