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.

• Mat: stackoverflow.com/questions/2209224/vector-vs-list-in-stl
• a3.14_Infinity: 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?
• solti: @a3.14_Infinity I was planning to access by traversing via a for loop

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.

• solti: @manilo -- I was going for multigraph. Thank you for the thought full insight. I will use set for now ..