1. DFS #
Created Monday 30 March 2020
Algorithm: We implement the graph as an adjacency matrix:
- We ask the user number of vertices. We store this as n. Now we assume that the vertices are named from 0 to n-1.
- We ask for how many edges. The user inputs the edge pairs. We mark (a,b) and (b,a) as true for all inputs ‘a’ and ‘b’.
- We go through all vertices, calling DFS from it if they are absent from visited, at the same time checking if visited.size()<V. This ensures that disconnected components are also taken into account.
- Internal stack is used, i.e recursion.
- Our graph is a simple graph - i.e no self loops, no weights, single undirected edges only.
Insights/Takeaways:
- We need a visited array, and it is very important. If not used we’ll end up in an infinite loop, even if the graph has a single cycle.
- DFS internally uses stack. And stacks may work using an array, but it will still require us to pop/replace an element. And as we don’t scan all the neighbours it may happen that we pop a neighbour and again take it in some other run. So visited array/map is needed.
- Note that we go to the depths until we reach a node where all neighbours have been visited. Hence the name Depth First Search.
Efficiency T.C = O(V+E)** if we use hashmap as visited array.** S.C = O(V)
Implementation tips
- Use dynamic DSs.
Applications
- Most problems are just variations of DFS and BFS.