What data structure to use to save the address of edges in depth first search?

Question

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.

Answer 1

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.