DFS(Depth First Search) example in real-world by applying it to the wireless sensor network
Depth First Search(DFS) Algorithm
Let say we have 10000 sensor nodes are deployed in the border of one country and each one of this sensor has a mac address and other attributes behaviors, let’s assume those sensors doesn’t have a GPS. Our goal is to find the node that detects the thank of the enemy in the specific area, well, we will use the DFS solution to find the sensor, these sensors are deployed at the same distances, and the distance between every two nodes is 15 meters, all nodes separated to the same distance
Applying DFS solution
when the sensor detects the enemies thank, it will tell the base station about that, and the base station will know that node by its mac address because each node has a unique address called the mac address.
The user at the base station will choose the first node as the root node
The routes or paths connected between nodes called edges
when the sensor node detects the strange object.
I will just write the necessary codes, not the whole things, our code example include tree class, node class, last node class, and dfs solution method to find the detected node and its depth to route then the distance to the root node, also we will include in this solution and you can make any additional attributes or behavior methods to this classes or you can add other classes joined to this class.
We added extra steps to the tree of sensors, to find all last nodes in the tree,
We can get benefit from lastnode of the tree by calculating how far from the destination node that detected the, so we will know this tank passed the last elements of tree sensors or not yet,
so we can add in our class one method called objectPassedLast, so it will check an array of all lastNodes of tree that include or contains the detected sensor or not yet. In this way, we can know the sensor passed the end of the tree or not.
After we explained the DFS in a real-world example, we are talking a little about the dfs.
The complexity of dfs is o(v,e) , v vertices, and e edges.
How DFS works,
1- He will choose the root node for startup
2- Check the root nodes edges may include only one path or many paths
3- Root node will randomly pick up one index of node of node in his array of paths
4- The detected index form detected edge from edges, will used to check in the indexof array of nodes.
5- Then we will make our first node after root node
6- For extra steps we are going to check is this node last in Tree or not
A- if the detected index form detected edge from edges in his route path has
only one index, then this index is a last index one path in the tree, then we will make LastNode object we called f
b- if not then we will make normal node
7-If the node only has one path then, we will go second index in the array of indexes in the edge of arrays .
8-if this node has index path has more indexes the after making node, we will consider this node parent to other to the nodes connected to him ,
9- we will apply dfs recursion here to make the same steps as we did
10-new dfs method argument will include new parent node, the child node we have made it
, and k: the picked up index from an array of the detected edge that we also detect the edge from edges.
11- We have a problem that some of the detected in the index already detected, so we are going to use
One variable array of Boolean, so every time when we add new node we will check in the edges of this node already visited or not. if not visited then we will make new node, if it visited we will choose another index from an array of detected edge, thus all the process will go like this.
