7
\$\begingroup\$

I got the C++ implementation of depth-first search (DFS) from here and made slight modifications to it. The modified code is as follows:

#include "stdafx.h"
#include <iostream>
#include<map>
#include<list>

class Graph {
    void DFSUtil(int v);
public:
    std::map<int, bool> visited;
    std::map<int, std::list<int>> adj;
    void addEdge(int v, int w);
    void DFS();
};

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
}

void Graph::DFSUtil(int v)
{
    visited[v] = true;
    std::cout << v << " ";

    std::list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i);
}


void Graph::DFS()
{
    for (auto i : adj)
        if (visited[i.first] == false)
            DFSUtil(i.first);
}

int main()
{
    Graph g;
    g.addEdge(0, 1);
    g.addEdge(0, 9);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(9, 3);

    std::cout << "Depth First Traversal result\n";
    g.DFS();

    std::cin.get();

    return 0;
}

What further improvements can I make to this code?

\$\endgroup\$
9
  • \$\begingroup\$ You need to learn the visitor pattern. \$\endgroup\$ Mar 26, 2021 at 16:27
  • 2
    \$\begingroup\$ Not sure what DF search means when you apply it to a graph (what is down verses across). The term is usually applied to non-cyclic structures (like trees). \$\endgroup\$ Mar 26, 2021 at 16:32
  • \$\begingroup\$ @MartinYork Thank you for the response. Where do you see "DF"? I only see the word "DFS" in my question. \$\endgroup\$
    – a_sid
    Mar 26, 2021 at 17:05
  • \$\begingroup\$ DFS => DF Search => Depth First Search \$\endgroup\$ Mar 26, 2021 at 17:17
  • 6
    \$\begingroup\$ @MartinYork I don't know where you get the assumption that DFS is only used in the context of acyclic graphs. Just look at the cyclic examples in here: en.wikipedia.org/wiki/Depth-first_search Or look at the graph provided in the link in the question. Both of them have cycles \$\endgroup\$
    – Helena
    Mar 27, 2021 at 11:32

6 Answers 6

16
\$\begingroup\$

What further improvements can I make to this code?

The code is rather bad - the site you read it from tends to have lots of bad/amateur articles.

  1. The graph class:

    std::map<int, bool> visited;
    std::map<int, std::list<int>> adj;
    

This is extremely poor and inefficient graph implementation. std::map creates a new memory allocation for each element. So you do it twice for both the boolean and the list. Also std::list allocates a piece of memory for each element as well.

Overuse of memory allocation means both memory fragmentation issues as well as performance issues due lots of unmanageable RAM access and indirections. Memory loading is currently one of the slowest operations on modern processors. But compilers tend to optimize it quite well if the memory is contiguous - which is furthest from the truth in this case.

To simplify the structure you'd better use std::vector<Node> where Node contains vertex's information + std::vector<size_t> of neighbors. In general, I don't believe there is a perfect solution for graph representation - instead there are numerous ways to represent and each suitable or more attuned to specific types of graphs. For instance, solutions that are good for sparse graphs are surely very poorly suited for dense graphs. Also certain additional optimizations can be made assuming that graph is fixes. The question is complex and I cannot provide an answer without knowledge of the use-case.

  1. DFS() implementation is also pretty bad. It relies on recursion and I assure you, that for large enough connected graphs with it will blow the stack resulting in UB.

Proper DFS/BFS implementation store states-to-be-visited in a std::stack or std::queue or something similar while the visit routine occurs in a single loop instead of recursion.

Also, I presume you want some kind of output or action made on vertices from the DFS, no?

\$\endgroup\$
2
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$
    – Malachi
    Mar 29, 2021 at 16:10
  • \$\begingroup\$ Look at Boost's flat_map to overcome the efficiency issues with the std::map, but still make use of map features. \$\endgroup\$
    – JDługosz
    May 11, 2021 at 14:40
12
\$\begingroup\$

Disagreement

I have to disagree with @ALX23z blanket statement that using std::map is bad idea. There is a lot more to it than that (if the graph was sparse the map is great). But you don't give enough contect to evaluate the graph implementation. All I can say it is an acceptable "basic" implementation.

Overall

Things that are actually bad:

1: The two main structures are public.

class Graph {
    void DFSUtil(int v);
public:
    std::map<int, bool> visited;        // public member variable
    std::map<int, std::list<int>> adj;  // public member variable.
                                        // The user of this class can
                                        // damage the state of the object.
                                        //
                                        // but more importantly it locks you
                                        // to a specific implementation.
                                        // You can never remove the map without
                                        // fixing all the code that uses the map.
    void addEdge(int v, int w);
    void DFS();
};

The adj should absolutely be private. The only method that should be public is addEdge(). That way if your usage of map turns out to be bad (after you measure it) then you can easily swap it out for another implementation without affecting any of the code that uses your Graph class.

2: You have a member that tracks some external processes.

std::map<int, bool> visited;

This is not a property of the class this is a property of the traversal itself. Storing it in the class limits how the class can be used you should store this as part of the traversal processes (there is a pattern for this "Visitor Pattern").

Code Review

Be consistent on your formatting:

#include <iostream>
#include<map>              // Why no space here
#include<list>

Public members variables!!

public:
    std::map<int, bool> visited;
    std::map<int, std::list<int>> adj;

Member variables should always be private. If they need to be public you need to be able to articulate in a very detailed way why you are exposing the state and allowing the potability of it being mutated in a non controlled manner and thus potentially allowing the object to become invalid.

Note: const (preferably static) state is ok to be public.


This is a good interface for creating a graph.

    void addEdge(int v, int w);

You can use this and the internal state can be nearly anything you want. If you used a PIMPL pattern you could customize the internal state depending on the type of graph.


The problem with your code is that it only does one thing. Print out the key of the node. If you want it to do anything else you need to change the code.

void Graph::DFSUtil(int v)
{
    visited[v] = true;
    std::cout << v << " ";

    std::list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i);
}


void Graph::DFS()
{
    for (auto i : adj)
        if (visited[i.first] == false)
            DFSUtil(i.first);
}

This is where you should inject your functionality (the action you want done). This is a form of "Dependency Injection" you pass the work action (as a function) into DFS() your function then gets called once for each node.

void Graph::DFS(std::function<void(int)>&& action);
void Graph::DFSUtil(std::function<void(int)>&& action, int v);

Now the usage becomes:

graph.DFS([](int n){std::cout << v << " ";}); // Or you can pass any action
                                              // you like.

But your main problem is implementing the visitor pattern:

class GraphVisitor
{
        std::map<int, bool>   visited;
        virtual void doVisit(int n) = 0;
    public:
        virtual ~GraphVisitor() {}
        void visit(int n)  {
            if (!visited[n]) {
                visited[n] = true;
                doVisit(n);
            }
        }
};
class Graph
{
        void accept(int i, GraphVisitor& visitor)
        {
            visitor.visit(i);
            for(auto e: edges(i)) {    // some way to get edges from i.
                  accept(e.dst.id, visitor);
            }
        }
    public:
        void accept(GraphVisitor& visitor)
        {
             for(auto i: adj) {
                 accept(i, visitor);
             }
        }
};
\$\endgroup\$
1
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$
    – Malachi
    Mar 29, 2021 at 16:33
10
\$\begingroup\$

I've assumed here the OP is performing DFS on undirected graphs - if not only my second point is valid.

There are several other answers here suggesting better coding practices and more efficient implementations, but they're missing the biggest problem with you code: it doesn't perform depth first search!

To demonstrate this run it with the graph created by:

Graph g;
g.addEdge(0, 1);
g.addEdge(1, 3);
g.addEdge(1, 2);
g.addEdge(4, 3);
g.addEdge(3, 5);

This outputs 0 1 3 5 2 4. This is wrong. 4 is part of the 3 branch so should be explored before the program backtracks and explores 2. The bug here is in the addEdge() function which makes w reachable from v but does not make v reachable from w. You need to add adj[w].push_back(v);.

The other issue with your code is that it will explore nodes which aren't attached to the rest of the graph (try adding g.addEdge(20, 21);. DFS shouldn't be able to get to these nodes but can anyway). The root problem here is your DFS() function, which starts a new depth first search every time it finds an unvisited i. This loop should not exist. Instead your program should have a parameter for where the depth first search should start, eg: 0, and go straight to the functionality in DFSUtil().

\$\endgroup\$
1
  • \$\begingroup\$ From the graph model I would assume that the graph is directed. Other than that, very good observations \$\endgroup\$
    – sehe
    May 10, 2021 at 13:25
5
\$\begingroup\$
std::map<int, bool> visited;

This is useless as a member variable.

  • It means nothing before or after you call DFS, so it's a waste of space most of the time
  • There's only one copy of it for a given Graph, which means you can't call DFS twice concurrently
  • It retains its state after calling DFS the first time, which means you can't even call DFS twice in sequence.

This variable should be local to DFS, created afresh at each call, and passed in to DFSUtil by reference, if at all (using a stack and a loop, as mentioned in ALX23z's review, does not require a helper method at all).

\$\endgroup\$
1
  • 1
    \$\begingroup\$ "you can't even call DFS twice in sequence." - well you can, but it may not do what you require. Then again, there are algorithms that usefully retain state for incremental operations. \$\endgroup\$
    – sehe
    May 10, 2021 at 11:47
2
\$\begingroup\$

You have received excellent feedback from others. I can only add to that in a show-and-tell fashion.

What my version does is address all the issues mentioned by others:

  • make the directed/undirected choice explicit in your graph

  • make the algorithm iterative so you don't have the stack limit

  • make your containers contiguous to reduce allocations and increase locality of reference.

    I opted for deque which, given the current access patterns still offers reference stability.

  • For the visited marks I use a local data structure. A dynamic_bitset would probably be the most pure, but I chose std::vector<bool> for simplicity.

Some things that haven't been mentioned:

  • Your algorithm lacked a feedback mechanism. I added a callback argument that can be used to act on visited vertices.

  • You had DFS and the Graph model coupled. There's no reason. I made a simple interface that you could optionally define as a "concept" (AdjacencyGraph, if you will):

    struct AdjacencyGraph {
        using VertexId = unsigned;
    
        size_t size() const;
        bool empty() const;
        void addEdge(VertexId, VertexId);
        range<VertexId> adjacent(VertexId id) const;
     };
    

    And the DFS algorithm is a free function that operates on any such graph:

  • I added quite a few precondition checks, .at(x) instead of [x] (which does bounds checking)

  • I fixed sloppy const-correctness (most notably inside DFS, even though it's now a free function)

  • I committed the "sin" of premature optimization by using small_vector from Boost Container to optimize for "expected out-degree".

    See here for a demonstration where this makes a big difference:

    Just for kicks, I made a little profile of the median out-degree of nodes: i.imgur.com/7zcIZ5Q.png. Since it shows the median is 40 out-edges, I replaced vector<OutEdge> with small_vector<OutEdge, 40> and behold: it runs 4x faster (10s without, 22s with heuristics) . – sehe Apr 24 at 20:51

The resulting separation of concern gives a calmer code image, IMO:

The Graph

struct Graph {
    enum mode { directed, undirected };
    Graph(mode mode) : _mode(mode) {}

    using VertexId = unsigned;

    size_t size() const { return _vertices.size(); }
    bool empty() const { return _vertices.empty(); }

    void addEdge(VertexId v, VertexId w) {
        auto& target = vertex(w); // ensure it is created
        if (_mode == undirected)
            target.adjacent.push_back(v);

        vertex(v).adjacent.push_back(w);
    }

    auto const &adjacent(VertexId id) const {
        return _vertices.at(id).adjacent;
    }

  private:
    struct Vertex {
        small_vector<VertexId, 10> adjacent;
    };
    std::deque<Vertex> _vertices;
    mode _mode = directed;

    Vertex& vertex(VertexId id) {
        _vertices.resize(std::max(id + 1ul, _vertices.size()));
        return _vertices.at(id);
    }
};

Note how nice it is to be able to just flip a switch to get undirected behaviour.

The Algorithm

The algorithm can be viewed in two levels:

template <class Graph, class V, class F>
void DFS(Graph const& g, V start, F callback) {
    /// local state and methods
    /// ...
    /// end local definitions

    while (!stack.empty()) {
        for (V v : g.adjacent(pop()))
            push(v);
    }
}

You see it is ultra-brief and clear. Of course, the devil must be in the details. However, with some good organization, we can limit the "damage":

/// local state and methods
using V = typename AdjacencyGraph::VertexId;
std::vector<bool> visited(g.size());
std::vector<V> stack{start};

auto push = [&](V v) {
    if (visited.at(v))
        return false;
    callback(v);
    stack.push_back(v);
    visited[v] = true; // no boundscheck needed here
    return true;
};

auto pop = [&] {
    auto v = stack.back();
    stack.pop_back();
    return v;
};
/// end local definitions

Really, this is just like a local class with two data members and two member functions. In fact, if you would have any use for re-use, you would do good to extract that type. See e.g. this answer where I do exactly that by extracting struct BFS_State (Read CSV and use bidirectional BFS to find the shortest connections between actors)

Full Listing

Live On Coliru

#include <boost/container/small_vector.hpp>
#include <deque>
#include <vector>
#include <iostream>
using boost::container::small_vector;

/*
 *struct AdjacencyGraph {
 *    using VertexId = unsigned;
 *
 *    size_t size() const {return {};}
 *    bool empty() const {return {};}
 *    void addEdge(VertexId, VertexId) { }
 *    std::vector<VertexId> adjacent(VertexId id) const { return {}; }
 *};
 */

struct Graph {
    enum mode { directed, undirected };
    Graph(mode mode) : _mode(mode) {}

    using VertexId = unsigned;

    size_t size() const { return _vertices.size(); }
    bool empty() const { return _vertices.empty(); }

    void addEdge(VertexId v, VertexId w) {
        auto& target = vertex(w); // ensure it is created
        if (_mode == undirected)
            target.adjacent.push_back(v);

        vertex(v).adjacent.push_back(w);
    }

    auto const &adjacent(VertexId id) const {
        return _vertices.at(id).adjacent;
    }

  private:
    struct Vertex {
        small_vector<VertexId, 10> adjacent;
    };
    std::deque<Vertex> _vertices;
    mode _mode = directed;

    Vertex& vertex(VertexId id) {
        _vertices.resize(std::max(id + 1ul, _vertices.size()));
        return _vertices.at(id);
    }
};

template <class Graph, class V, class F>
void DFS(Graph const& g, V start, F callback)
{
    /// local state and methods
    using VertexIndex = typename Graph::VertexId;
    std::vector<bool> visited(g.size());
    std::vector<VertexIndex> stack{start};

    auto push = [&](VertexIndex v) {
        if (visited.at(v))
            return false;
        callback(v);
        stack.push_back(v);
        visited[v] = true; // no boundscheck needed here
        return true;
    };

    auto pop = [&] {
        auto v = stack.back();
        stack.pop_back();
        return v;
    };
    /// end local definitions

    while (!stack.empty()) {
        for (VertexIndex v : g.adjacent(pop()))
            push(v);
    }
}

int main()
{
    Graph g(Graph::directed);
    using VertexId = Graph::VertexId;

    for (auto [s, t] :
         {std::pair{0, 1}, {0, 1}, {0, 9}, {1, 2}, {2, 0}, {2, 3}, {9, 3}})
    {
        g.addEdge(s, t);
    }

    std::cout << "Depth First traversal\n";

    VertexId start = 0;
    DFS(g, start, [](VertexId v) { std::cout << "Visited " << v << "\n"; });
}

Prints

Depth First traversal
Visited 1
Visited 9
Visited 3
Visited 2
Visited 0
\$\endgroup\$
1
  • \$\begingroup\$ Thank you very much for promptly responding to my request :) \$\endgroup\$
    – a_sid
    May 11, 2021 at 5:37
1
\$\begingroup\$

regarding

std::list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i);

You have the definition of i outside the for statement and not initialized; you spell out the complex and specific type rather than using auto, you repeatedly index adj[v] and you call .end() each time through the loop.

Yet the following function shows a simple range-based for loop instead. So why is this one so clunky, when you do in fact know better?

Also, could it have used a const_iterator instead?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.