2

I'm learning about data structures and abstract data types, and I keep getting stuck on one question that keeps coming up.

I don't understand how computer science can be 50 years old now (or older, I don't know exactly) and how data structures, ADTs, and algorithms can be such a foundational part of it all, yet still there is no standard to any of it.

My question is actually pretty specific: I'm trying to implement depth-first-search in C++ in a way that can work on any native (built-in) data-type. My question is, where do I look first? I know the stack class from the STL can be used to implement the DFS algorithm, but is the STL the first place to look? Should I be implementing DFS from scratch, using a stack and what I know about implementing this algorithm? Or do professional programmers have a library they turn to when they need to pursue this kind of search?

Please advise, this question isn't as concrete as I'd like it to be.

dvanaria
  • 6,593
  • 22
  • 62
  • 82
  • no u dont need any library to do it. very easy to implement and i m sure there are many examples. – DarthVader Sep 01 '12 at 05:17
  • @DarthVader "Swap" is easier to implement and there is a library function for that. – dsign Sep 01 '12 at 05:17
  • For me, if the standard library (often mistakenly called the STL) has the data structures or algorithms I need, I use that. If not then I turn to Boost, and if it's not in Boost either then I start doing a wider search (e.g. Google and Wikipedia). – Some programmer dude Sep 01 '12 at 05:17
  • @dsign there is no library for any graph or tree algorithms. None of the prog langs do that because there are several different ways to do it. have you ever seen a c# or java library that represents the graph? I work in corps and we always write it ourself. – DarthVader Sep 01 '12 at 05:19
  • Thanks Joachim, that's what I was looking for. So if you were presented with a pretty standard graph problem, that needed to be searched using DFS, you would turn first to the C++ standard library? It doesn't have a DFS algorithm that I know of. – dvanaria Sep 01 '12 at 05:20
  • 1
    @DarthVader There are quite a few libraries that implement graph and tree algorithms: boost::graph for example. Check this question: http://stackoverflow.com/questions/205945/why-does-the-c-stl-not-provide-any-tree-containers . They are not part of the STL because the need does not seem to be high enough. Plus, at least boost::graph, is as ugly as it comes. – dsign Sep 01 '12 at 05:21
  • Hi Darth, no I know Java and C# and other languages don't supply graph algorithms, but where do you turn to when you have to implement DFS? Do you just use what you know and write it from scratch? – dvanaria Sep 01 '12 at 05:21
  • @dvanaria yes, you write your own. if a prog language or a library to provide that they have to think about everything from synchronization to extensibility. That will cause too much of a pollution in the language API. – DarthVader Sep 01 '12 at 05:24
  • Like @dsign suggests, [boost.graph](http://www.boost.org/doc/libs/1_51_0/libs/graph/doc/index.html) is probably your best bet to start with. – Some programmer dude Sep 01 '12 at 05:28
  • And Jeffrey Ullman is still teaching, so a sciences is just at dawn if its pioneers are still alive and walking ;-) – dsign Sep 01 '12 at 05:38

2 Answers2

7

Boost has a C++ depth first search implementation here:

http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/depth_first_search.html

Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
5

Put your knowledge to use! You know STL and you know how to implement DFS using stack, and most importantly, it is quite simple, so you can code it yourself.

Most people suggest Boost. But if this is the only thing you would need Boost for, then it is better to write DFS on your own. On the other hand, you also want to learn how to use what is already available.

Vinayak Garg
  • 6,518
  • 10
  • 53
  • 80
  • 3
    +1: While I respect the boost Community for what they have done taking on big dependencies like boost has a cost of its own and its up to us as engineers to ask ourselves what is the most cost-effective way to develop software. Sometimes it's taking a dependency, sometimes it's avoiding a dependency and implement it by yourself. – Just another metaprogrammer Sep 01 '12 at 11:02