Artificial intelligence Depth First Search

Soory Only Slides .

1. Artificial Intelligence Presentation Topic Depth First Search

2. Introduction Name : Nouman Roll No : 17-Ntu-1236 Program : BSIT

3. Depth-first search   it is an algorithm for traversing or searching tree or graph data structures. One starts at the root and explores as far as possible along each branch before backtracking. A version of depth-first search was investigated in the 19th century French mathematician Charles Pierre Tremaux as a strategy for solving mazes. Depth-first search is a systematic way to find all the vertices reachable from a source vertex. Like breadth-first search, DFS traverse a connected component of a given graph and defines a spanning tree. The basic idea of depth-first search is methodically exploring every edge. We start over from a different vertices as necessary. As soon as we discover a vertex, DFS starts exploring from it (unlike BFS, which puts a vertex on a queue so that it explores from it later).

4. Basic Points Uninformed Search Uses Stack Phenomenon Deepest Node Incomplete (Possible That DFS didn’t give us result if search space infinite . Move one side till loop not completed) Non optimal (cost High or other cost low) Work on present Knowledge (Not on Estimation value)

5. Complexity: Each nodes and edges are visited once. So the complexity of DFS is  O(V+E) , where  V  denotes the number of nodes and  E  denotes the number of edges.

6. Applications of Depth First Search: Finding all pair shortest path in an undirected graph. Detecting cycle in a graph. Path finding. Topological Sort. Testing if a graph is bipartite. Finding Strongly Connected Component. Solving puzzles with one solution .

7. Rules For Traverse graph Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty.

8. Let's look at an example. We'll traverse this graph: Stack

9. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : AB A B

10. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABE A B E

11. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEF A B F

12. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEF A B

13. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEF A

14. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEFC A C

15. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEFCG A C G

16. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEFCG A

17. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEFCGD A D

18. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEFCGD A D H

19. Let's look at an example. We'll traverse this graph: Stack Rule #1 Put the starting vertex into the stack. Mark it visited Display it. Rule #2 if(stack{top} has adjacent unvisited vertex) { Visit adjacent unvisited vertex and mark it visited push it into stack display it. } Else { Pop top element of stack. } Repeat Rule 2 until stack is empty. Display : ABEFCGD