DFS: Depth First Search is the most familiar graph traversal method which is used in large number of searching application. A graph traversal is a systematic procedure of visiting all the nodes. The basic data structure for the DFS is stack. And we implement the procedures using the basic elements of programming.
Beyond all these implementation details, these methods convey various other concepts. Some of them are described below.
1. E-Node.
2. L-Node.
3. D-Node.
4. Discovery time.
5. Departure time.
Sometimes while programming we didn't pay attention to these stuffs. But they can provide a great information, when we extend the algorithms for solving the network related issues.
E-NODE ( Expanding or Exploring)
Node which is currently being explored or whose children is being generated is E-Node. There can be only one E-Node at a time during the traversal.
L-NODE (Live Node)
The node which has not been fully explored or all of the two children has not been generated is live node. There can be many number of live nodes during the traversal.
D-NODE(Dead Node)
The node which is not explored or all of its children has been generated is Dead Node.
TWO TIME CONCEPTS:
DISCOVERY TIME:
It is the time when we discover a particular node.
DEPARTURE TIME:
It is the time when we leave a node after exploring all the children
We usually say DFS as multiple DFS, because E-Node can be started from any node.
The unrolling of DFS can be visualised by the following graph
The working of the DFS algorithm based on the concepts of the nodes and times is as follows. Starting from the node 1. At time 1 we discovered the node numbered 1. At present the E-NODE is node 1. From the first node we have two possibilities. Either we can go for the 2nd or 3rd. For the time being we are going to discover the node numbered 2. At the moment we reach the node 2, node 1 will become the live node and node 2 will becomes the E node. Similarly the discovery time of the node 2 is 2. From 2nd node we can go to either 4 or 5. We are going to the 4th node correspondingly the node 2 will becomes the LIVE-NODE and node 4 will becomes the E-NODE. The discovery time is 3. Similarly we are going to other nodes in the sequence from the 4th node is as follows 4--8--7--3--6---. The corresponding discovery times is in the sequence 3--4--5--6--7. And the nodes except the 6th node will become the live node. The sixth node will becomes the E-NODE. The sixth node is devoid of any children which is unexplored. So the first departure takes place at the sixth node. The departure time is 8. we will return form the sixth node to the previous node. and it will become dead. On reaching the node 3 , there also no children remained unexplored. So returns to node number 7. and the node 3 will becomes dead. The departing time from the node 3 is 9. On reaching the node 7 the same process will happens. The departing time is 10. On reaching the node 8, Checks for any unexplored child. Here node 5 is unexplored. So the discovery time of the node 5 is 11...and the process is continues...The Whole process will come to an end when all the nodes of the graph becomes dead nodes..
The data structure view of these process shows the usage of stack for tracking the path. When a node becomes a live node, that node will be pushed in to the stack. When ever a node becomes a dead node, It will be popped from the stack. The whole process will comes to an end when the stack is empty.
There is another method called DFT. We usually DFS and DFT unknowingly at different places. There is a crucial difference between these two. DFT( Depth First Traversal) is used on a FOREST. It is used for traversing when the graph is disjointed or disconnected. DFS using the strategy of backtracking, it is used to know whether a graph is connected or not , Verifying whether a node is reachable and finding the articulation points in the graph, which is very essential in solving network related problems..
Thats all the story of DFS..............................................................................................
Beyond all these implementation details, these methods convey various other concepts. Some of them are described below.
1. E-Node.
2. L-Node.
3. D-Node.
4. Discovery time.
5. Departure time.
Sometimes while programming we didn't pay attention to these stuffs. But they can provide a great information, when we extend the algorithms for solving the network related issues.
E-NODE ( Expanding or Exploring)
Node which is currently being explored or whose children is being generated is E-Node. There can be only one E-Node at a time during the traversal.
L-NODE (Live Node)
The node which has not been fully explored or all of the two children has not been generated is live node. There can be many number of live nodes during the traversal.
D-NODE(Dead Node)
The node which is not explored or all of its children has been generated is Dead Node.
TWO TIME CONCEPTS:
DISCOVERY TIME:
It is the time when we discover a particular node.
DEPARTURE TIME:
It is the time when we leave a node after exploring all the children
We usually say DFS as multiple DFS, because E-Node can be started from any node.
The unrolling of DFS can be visualised by the following graph
The working of the DFS algorithm based on the concepts of the nodes and times is as follows. Starting from the node 1. At time 1 we discovered the node numbered 1. At present the E-NODE is node 1. From the first node we have two possibilities. Either we can go for the 2nd or 3rd. For the time being we are going to discover the node numbered 2. At the moment we reach the node 2, node 1 will become the live node and node 2 will becomes the E node. Similarly the discovery time of the node 2 is 2. From 2nd node we can go to either 4 or 5. We are going to the 4th node correspondingly the node 2 will becomes the LIVE-NODE and node 4 will becomes the E-NODE. The discovery time is 3. Similarly we are going to other nodes in the sequence from the 4th node is as follows 4--8--7--3--6---. The corresponding discovery times is in the sequence 3--4--5--6--7. And the nodes except the 6th node will become the live node. The sixth node will becomes the E-NODE. The sixth node is devoid of any children which is unexplored. So the first departure takes place at the sixth node. The departure time is 8. we will return form the sixth node to the previous node. and it will become dead. On reaching the node 3 , there also no children remained unexplored. So returns to node number 7. and the node 3 will becomes dead. The departing time from the node 3 is 9. On reaching the node 7 the same process will happens. The departing time is 10. On reaching the node 8, Checks for any unexplored child. Here node 5 is unexplored. So the discovery time of the node 5 is 11...and the process is continues...The Whole process will come to an end when all the nodes of the graph becomes dead nodes..
The data structure view of these process shows the usage of stack for tracking the path. When a node becomes a live node, that node will be pushed in to the stack. When ever a node becomes a dead node, It will be popped from the stack. The whole process will comes to an end when the stack is empty.
There is another method called DFT. We usually DFS and DFT unknowingly at different places. There is a crucial difference between these two. DFT( Depth First Traversal) is used on a FOREST. It is used for traversing when the graph is disjointed or disconnected. DFS using the strategy of backtracking, it is used to know whether a graph is connected or not , Verifying whether a node is reachable and finding the articulation points in the graph, which is very essential in solving network related problems..
Thats all the story of DFS..............................................................................................
No comments:
Post a Comment