Scribd Logo
Upload

Welcome to Scribd!

  • 88 views

    Continuous Assesment 1 (Ca1) AY-2022-2023 (ODD SEM) (Makaut Examination) Assessment Type-Presentation

    Uploaded by

    Rohit Kumar
    Depth First Search (DFS) is a graph traversal algorithm that explores nodes as deep as possible along each branch before backtracking. It uses a stack to keep track of traversed nodes. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The space complexity is lower than breadth-first search since it doesn't require additional memory for queue. DFS is a complete algorithm that will find a solution if one exists regardless of the graph type.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Continuous Assesment 1 (Ca1) AY-2022-2023 (ODD SEM) (Makaut Examination) Assessment Type-Presentation

    Uploaded by

    Rohit Kumar
    88 views11 pages
    Depth First Search (DFS) is a graph traversal algorithm that explores nodes as deep as possible along each branch before backtracking. It uses a stack to keep track of traversed nodes. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The space complexity is lower than breadth-first search since it doesn't require additional memory for queue. DFS is a complete algorithm that will find a solution if one exists regardless of the graph type.

    Original Title

    AI(URL 27600120045)

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Depth First Search (DFS) is a graph traversal algorithm that explores nodes as deep as possible along each branch before backtracking. It uses a stack to keep track of traversed nodes. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The space complexity is lower than breadth-first search since it doesn't require additional memory for queue. DFS is a complete algorithm that will find a solution if one exists regardless of the graph type.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    88 views11 pages

    Continuous Assesment 1 (Ca1) AY-2022-2023 (ODD SEM) (Makaut Examination) Assessment Type-Presentation

    Uploaded by

    Rohit Kumar
    Depth First Search (DFS) is a graph traversal algorithm that explores nodes as deep as possible along each branch before backtracking. It uses a stack to keep track of traversed nodes. The time complexity of DFS is O(V+E) where V is the number of vertices and E is the number of edges. The space complexity is lower than breadth-first search since it doesn't require additional memory for queue. DFS is a complete algorithm that will find a solution if one exists regardless of the graph type.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 11

    BUDGE BUDGE INSTITUTE OF TECHNOLOGY

    AFFILIATED TO MAKAUT(FORMERLY WBUT)& APPROVED BY AICTE, NAAC ACCREDITED KOLKATA -


    700 137, WEST BENGAL, INDIA PHONE : 033 2482 0676 / 0670 HTTP://WWW.BBIT.EDU.IN
    DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NBA (NATIONAL BOARD OF
    ACCREDITATION) VALID FROM ACADEMIC YEAR 2021-2022 TO 2023-2024 I.E. UPTO 30-06-2024.
    CONTINUOUS ASSESMENT 1(CA1)
    AY-2022-2023(ODD SEM)
    (MAKAUT EXAMINATION)
    ASSESSMENT TYPE- PRESENTATION

    UNIVERSITY ROLL NUMBER :- 27600120045

    NAME OF THE STUDENT :- ROHIT KUMAR

    COURSE CODE:- PEC-IT501B

    COURSE NAME :- ARTIFICIAL INTELIGENCE

    SEMESTER :-5TH

    YEAR:- 3RD
    DEPARTMENT :- COMPUTER SCIENCE AND ENGINEERING

    TOPIC OF PRESENTATION:- SPACE AND TIME COMPLEXITY OF DEPTH FIRST SEARCH


    SPACE AND TIME COMPLEXITY OF DEPTH FIRST SEARCH

    • Depth First Search Algorithm


    • A standard DFS implementation puts each vertex of the graph into one of two categories:
    1. Visited
    2. Not Visited
    • The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
    • The DFS algorithm works as follows:
    • 1. Start by putting any one of the graph's vertices on top of a stack.
    • Take the top item of the stack and add it to the visited list.
    • Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack.
    • Keep repeating steps 2 and 3 until the stack is empty.

    • Depth First Search Example


    • Let's see how the Depth First Search algorithm works with an example. We use an undirected graph with N
    vertices.
    DEPTH FIRST SEARCH IS A GRAPH TRAVERSAL ALGORITHM.
    • The search starts on any node and explores further nodes going deeper and deeper until
    the specified node is found, or until a node with no children is found. If a node is found
    with no children, the algorithm backtracks and returns to the most recent node that has
    not been explored. This process continues until all the nodes have been traversed.
    • A stack is used as an auxiliary data structure to keep track of traversed nodes to help it
    backtrack when required.
    TIME COMPLEXITY: 

    • If you can access each node in O(1) time, then with branching factor of b and max depth
    of m, the total number of nodes in this tree would be worst case = 1 + b + b 2 + … + bm-1.
    Using the formula for summing a geometric sequence (or even solving it ourselves) tells
    that this sums to = (bm - 1)/(b - 1), resulting in total time to visit each node proportional to
    bm. Hence the complexity = O(bm).
    • On the other hand, if instead of using the branching factor and max depth you have the
    number of nodes n, then you can directly say that the complexity will be proportional
    to n or equal to O(n).
    • The other answers that you have linked in your question are similarly using different
    terminologies. The idea is same everywhere. Some solutions have added the edge count
    too to make the answer more precise, but in general, node count is sufficient to describe
    the complexity.
    SPACE COMPLEXITY: 

     The length of longest path = m. For each node, you have to store its siblings so that when
    you have visited all the children, and you come back to a parent node, you can know which
    sibling to explore next. For m nodes down the path, you will have to store b nodes extra for
    each of the m nodes. That’s how you get an O(bm) space complexity.
    The complexity is O(n+m) where n is the number of nodes in your tree , and m is the
    number of edges.
    The reason why your teacher represents the complexity as O(b^m), is probably because he
    wants to stress the difference between Depth First Search and Breadth First Search.
    • When using BFS, if your tree has a very large amount of spread compared to it's depth,
    and you're expecting results to be found at the leaves, then clearly DFS would make
    much more sense here as it reaches leaves faster than BFS, even though they both reach
    the last node in the same amount of time (work)
    • When a tree is very deep, and non-leaves can give information about deeper nodes, BFS
    can detect ways to prune the search tree in order to reduce the amount of nodes necessary
    to find your goal. Clearly, the higher up the tree you discover you can prune a sub tree,
    the more nodes you can skip. This is harder when you're using DFS, because you're
    prioritize reaching a leaf over exploring nodes that are closer to the root.
    PROPERTIES

    Time Complexity
    • The worst case occurs when the algorithm has to traverse through all the nodes in the
    graph. Therefore the sum of the vertices(n) and the edges(m) is the worst-case scenario.
    This can be expressed as O( |n| + |m| ).
    Space Complexity
    • The space complexity of a depth-first search is lower than that of a breadth first search.
    Completeness
    • This is a complete algorithm because if there exists a solution, it will be found regardless
    of the type of graph provided.
    CONCLUSION

    • DFS is the traversal algorithms for graphs and trees. In this article, we witnessed
    the DFS algorithm, its working, and its implementation in different programming
    languages. In the next article, we will learn about another graph traversal
    algorithm BFS ( Breadth-First Search ).

    You might also like