0

Im taking a course in algorithms and data structers, and my instructor wants me to implement several data structers (such as BST, stack etc.), and algorithms (such as quick search, DFS, etc.). I want to belive that I understand the basics, but everytime Im starting to plan the code I have the same difficulty:

here's my current assigment: my instructor wants me to implement a DFS (depth first search) for a directed graph (using c++).

my question is- how do I suppose to implement the graph? should I use adjacency matrix? or should I use adjacency list? neither this nor that?? so I asked my instructor, and his answare was this: "think of the graph as a black box"... more confused than before, I rashed to stackoverflow, and here i am posting this question... I dont look for someone to tell me how to implement DFS (or any other algorithm- I can google too!)- I just need someone to explain what should I get as input, and what should I provide as output?

I'll appreciate any comment! thanks!

12
  • 7
    By "think of the graph as a block box", he means you're not supposed to be implementing the graph. Mar 26, 2013 at 19:56
  • 1
    This comes down to the question of what you need to know about the graph to implement DFS? That should give you and answer to the question of "what kind of interface should my graph class have so that I can implement DFS on it?" Mar 26, 2013 at 19:58
  • 1
    I assume that you have gotten a few more informations then just implement DFS on a data structure you have no informations about. Maybe you should be more specific about the informations you have. If you are supposed to treat the graph as a black box you need to get a graph type somewhere and need to know waht operations it supoorts
    – Grizzly
    Mar 26, 2013 at 20:04
  • 2
    You can assume you know the interface, otherwise you can't use the variable. Just don't assume anything specific about how the interface is implemented. (You walk up the counter. You order your food. You pay your money. You get the food. You eat. You leave. That's the "interface" to a fast food restaurant. I don't care what they do with the money or how they get the food to me. That's the implementation.) Mar 26, 2013 at 20:04
  • 1
    You just use the implementation without caring how it gets the job done. Mar 26, 2013 at 20:05

1 Answer 1

1

What he means by a black box is just that you cannot see the nodes and how they connect before you do your DFS. You will probably just get the root node and your algorithm with have to explore from there. As for what you should output- that depends on the assignment. Are you looking for specific data? if not, perhaps a detail of which nodes were visited in which order.

7
  • thats a good comment about the output, but not quite helpful with the input: lets say i have the root. how do i know how to locate its adjacencies if i dont know how the graph is even implemented? from the comments above, i understand thats not the point of this assignment, but still, I need to write the code...
    – omi
    Mar 26, 2013 at 20:39
  • Having the root node should give you the data for that node, like pointers to its children. Does that help? Mar 26, 2013 at 20:46
  • i guess that by root you meen the vertex i start the DFS from, right? and if so, i will need to know somehow who r his adjacencies- how can i find them if i dont know how a vertex is implemented? should i assume i get a list of adjacencies for every vertex? isn't it cheating?
    – omi
    Mar 26, 2013 at 20:52
  • 1
    Your professor should have given you a look at what the struct or class for the nodes look like. If they have not, I'm not sure where to go from there. If you know what the data are for the nodes, you can know what the children pointers are called and reference them. Mar 26, 2013 at 20:58
  • 2
    @omi: Assume you have an interface that includes a way to get the adjacencies. Use an actual interface to make it more concrete and so you can actually test. When you implement a DFS for a graph, it should be a DFS for any graph that complies with a specific graph interface regardless of implementation. Mar 26, 2013 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.