1

I am currently trying to write my own Depth First Search. I have created a class called node.

class node{ 
    private:
      bool is_visited;
      <data structure to collect edges>
    public : 
      size_t get_number_of_edges();
      void   set_is_visited( bool val);
      bool   get_is_visited();
};

Node is basically a vertex for DFS. I still have to make another class DFS, which will place this node in its private member (I will cross this bridge latter). This node has to store the address of other nodes (edges). I was wondering what data structure should I use to save the address of edges.

I was thinking of using vector.

vector<node*> collect_edges;

or should I use list ?

list<node*> collect_edges;

I personally don't see any difference.

  • think of diff use-case in your problem, if the number of edges keep increasing, what all operations are dependent on it - for example, you need to access it by index or by traversing - which would be better.. if you are going to search randomly? – a3.14_Infinity May 23 '16 at 7:03
  • @a3.14_Infinity I was planning to access by traversing via a for loop – solti May 23 '16 at 20:15
2

You should consider:

  • the type of the graph
  • the operations you need

For a simple graph, as opposed to a multigraph, the edges form a set (each edge is an unordered pair of distinct vertices) so you could also consider std::set<node *>.

A set is a good choice also if you have to maintain an order among edges.


              vector   list   set
removal        O(1)    O(1)   O(1)
enumeration    O(n)    O(n)   O(n)
insertion      O(1)    O(1)   O(log n)

compactness     *
cache friendly  *

A std::list-based edge-list doesn't seem the right solution. Especially if you're going to construct the graph and perform multiple DFSs.

An interesting reference is Choosing the Edgelist and VertexList, it has many details but the boost::adjacency_list class is very general and some considerations don't hold for your class.

  • @manilo -- I was going for multigraph. Thank you for the thought full insight. I will use set for now .. – solti May 23 '16 at 16:24

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.