Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 38 views

    Algorithm Presentation

    Uploaded by

    Aishwarya Rajesh
    The document discusses two common graph search algorithms: breadth-first search (BFS) and depth-first search (DFS). It provides definitions of BFS and DFS, describes their processes and pseudocode, compares their advantages and disadvantages, and lists some example problems for each algorithm. Key differences between BFS and DFS include their use of queues vs stacks and performance for problems where the target is closer vs farther from the source.

    Copyright:

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

    Algorithm Presentation

    Uploaded by

    Aishwarya Rajesh
    38 views15 pages
    The document discusses two common graph search algorithms: breadth-first search (BFS) and depth-first search (DFS). It provides definitions of BFS and DFS, describes their processes and pseudocode, compares their advantages and disadvantages, and lists some example problems for each algorithm. Key differences between BFS and DFS include their use of queues vs stacks and performance for problems where the target is closer vs farther from the source.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses two common graph search algorithms: breadth-first search (BFS) and depth-first search (DFS). It provides definitions of BFS and DFS, describes their processes and pseudocode, compares their advantages and disadvantages, and lists some example problems for each algorithm. Key differences between BFS and DFS include their use of queues vs stacks and performance for problems where the target is closer vs farther from the source.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    38 views15 pages

    Algorithm Presentation

    Uploaded by

    Aishwarya Rajesh
    The document discusses two common graph search algorithms: breadth-first search (BFS) and depth-first search (DFS). It provides definitions of BFS and DFS, describes their processes and pseudocode, compares their advantages and disadvantages, and lists some example problems for each algorithm. Key differences between BFS and DFS include their use of queues vs stacks and performance for problems where the target is closer vs farther from the source.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 15

    Data Structure &

    Algorithms

    Assigned by-Prof. Anoop Kumar Srivastava


    BFS and DFS
    Types of search
    algorithm
    BFS



    Breadth-First

    Search Algorithm
    Pseudocode 


    Advantages and Disadvantages of BFS

    Advantages: Disadvantages:
    BFS will provide a solution if any solution It requires lots of memory since each level
    exists. of the tree must be saved into memory to
    If there are more than one solutions for a expand the next level.
    given problem, then BFS will provide the BFS needs lots of time if the solution is far
    minimal solution which requires the least away from the root node.
    number of steps.
    Depth-first search is recursive
    DFS DFS-depth first search algorithm for traversing a tree or
    graph data structure.

    The algorithm starts at a node of a


    It is called the depth-first search graph and goes as far as possible in
    because it starts from the root node a given path, then backtracks until it
    and follow seach path to its greatest finds an unexplored path, and then
    depth node before moving to the explores the rest of it. The process is
    next path. repeatedly followed until all the
    nodes in the graph are explored.

    DFS uses a stack data structure for its The process of the DFS algorithm is
    implementation. similar to the BFS algorithm.
    Depth-First Search 

    Algorithm Pseudocode 


    Advantages and
    Disadvantages of
    DFS

    Advantages: Disadvantages:
    DFS requires very less memory There is the possibility that
    as it only needs to store a stack many states keep re-occurring
    of the nodes on the path from ,and there is no guarantee of
    root node to the current node. finding the solution.
    It takes less time to reach to the DFS algorithm goes for deep
    goal node than BFS algorithm down searching and
    (if it traverses in the right path). sometimes it may go to the
    infinite loop.
    Sr. Key BFS DFS
    No.

    Definition BFS, stands for Breadth First DFS, stands for Depth First
    1 Search. Search.

    Differences between Data structure BFS uses Queue to find the DFS uses Stack to find the

    BFS and DFS 2 shortest path. shortest path.

    Source BFS is better when target is DFS is better when target is far
    3 closer to Source. from source.

    Suitablity for As BFS considers all neighbour DFS is more suitable for
    decision tree so it is not suitable for decision decision tree. As with one
    tree used in puzzle games. decision, we need to traverse
    further to augment the
    decision. If we reach the
    4 conclusion, we won.

    5 Speed BFS is slower than DFS. DFS is faster than BFS.

    Time Complexity Time Complexity of BFS = Time Complexity of DFS is also


    O(V+E) where V is vertices and O(V+E) where V is vertices and
    6 E is edges. E is edges.
    Problems:

    Problem on BFS
    Problem on
    BFS
    Problem on DFS
    Problem on
    DFS

    You might also like