Graph Representation in C++

I am g开发者_Python百科oing through a book The Design and Analysis of Computer Algorithms Reading through the Graph chapter, I am trying to implement DFS. By Reading definition of this algorithm it says, Graph G=(V,E) partiions the edges in E into two sets T and B. An Edge (v,w) is place in set T if vertes w has not been previously visited when we are at vertex v considering edged (v,w) , otherwise edge `(v,w) is place in set B.

Basically his algorithm of DFS will give me new Graph which will be G=(V,T). I want to know how one would implement this in C++.

I tried using adjacency list, but I am confuse is there a need of storing edges of just a map of list should be fine.

---

In VTK, edges are stored in a vector, and it always stores a pair (v,w). Near this vector there are 2 other vector of vectors to store in and out edges of graph nodes. When a new edge is added, it added to edge vector, its nodes (v,w) are added to in and out edges vector of vectors, too.

---

I am not quite clear about what your exact question is. I assume that you are asking about how to maintain two sets T and B to distinguish edges that have been visited from edges that have been not during DFS. I think the easiest way to do so is to add a bool field "visited" to the node struct in your adjacency list. Initial value of this field for all nodes are "false". Suppose in the above case, when DFS come to v, and the edge (v,w) is not visited, then the node on the list of v that corresponds to w would have a value "false" for "visited" at that time. Otherwise it will have a value of "true".

I think the author just try to give you the idea that edges will be categorized into two kinds: visited and not visited at the end of DFS. But I don't think keep two explicit sets maintaining those two kinds of edges are necessary. You can always print the visited edges after DFS according to their updated "visited" value.