Depth First Search (Graphs) OCR A Level Computer Science

Hello,

I am currently doing DSA and I just want to check if my understanding of DFS is correct.

Attached is a little diagram that I will go through here, but I am just a little confused because the way it works is very similar to a BFS just using a stack.

Explanation of diagram:
1)
I start with node E. It being addded to the discovered list, and to the "check" stack. E is popped of the check stack and set to the current Node. We check the graph (adjacency list) seeing that it has one neighbor, C. This is pushed to the check stack and the discovered list.
2)
We pop C from the check stack, check its neighbors and find that D,E and A are neighbors, E is already discovered so therefore we add D and A to the discovered list and then push them onto the stack. This is where it gets a little confusing for me, if D was pushed after A then we would check D first like a BFS. Is this normal or did I implement it wrong?

The process repeats until we find G.

I also have a general question for people who are studying OCR A Level CS algorithms, since the specification is so vague (even the clarification document) how are we supposed to find out what exactly we need to know, since for linked lists e.g I learned how to implement it via an OOP approach but then they started talking about arrays in another source I found. The whole topic is just vague and seems to rely solely on how lucky you are to get a good teacher.

Thanks,

1

(edited 1 month ago)

Reply 1

acting-earthquak

I’ll be honest with you i’m doing AQA so there may be a slight difference and I can’t answer your second question, but I don’t think it will matter much. As long as you go all the way down one route before revisiting a node, it counts as DFS. So in this specific case it doesn’t actually matter whether D or A is pushed first. Personally, this is not the best way to show DFS

Although you can start anywhere it’s always so much easier to start from the root node unless the question asks otherwise (A) because it makes the difference between DFS and BFS way more obvious, then I go all the way along one route, eg. I always choose the leftmost node (A, C, E). Now E has no more unexplored neighbours so back to C, A is already explored so D is next. Now that whole branch is completed and I move on to the right branch, still choosing the leftmost route (A, C, E, D, B, G), and then F is the last one. For the same starting node, BFS would be (A, C, B, E, D, G, F) so the difference is much easier to see

Quick Reply

Related discussions

Latest

Trending

Articles for you

International Baccalaureate (IB) students: applying to university

Try out the app

Continue on web