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

Welcome to Scribd!

  • 90 views

    BFS VS DFS

    Uploaded by

    PRASHANTH
    BFS and DFS are two algorithms for traversing or searching trees or graphs. BFS uses a queue data structure and searches all nodes at the current level before moving to the next level, making it suitable for finding shortest paths. DFS uses a stack data structure and searches as far as possible down each branch before backtracking, making it suitable for applications like game solving where exploring all paths is important. While both have the same time complexity of O(V+E), BFS requires more memory than DFS.

    Copyright:

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

    BFS VS DFS

    Uploaded by

    PRASHANTH
    90 views3 pages
    BFS and DFS are two algorithms for traversing or searching trees or graphs. BFS uses a queue data structure and searches all nodes at the current level before moving to the next level, making it suitable for finding shortest paths. DFS uses a stack data structure and searches as far as possible down each branch before backtracking, making it suitable for applications like game solving where exploring all paths is important. While both have the same time complexity of O(V+E), BFS requires more memory than DFS.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    BFS and DFS are two algorithms for traversing or searching trees or graphs. BFS uses a queue data structure and searches all nodes at the current level before moving to the next level, making it suitable for finding shortest paths. DFS uses a stack data structure and searches as far as possible down each branch before backtracking, making it suitable for applications like game solving where exploring all paths is important. While both have the same time complexity of O(V+E), BFS requires more memory than DFS.

    Copyright:

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

    BFS VS DFS

    Uploaded by

    PRASHANTH
    BFS and DFS are two algorithms for traversing or searching trees or graphs. BFS uses a queue data structure and searches all nodes at the current level before moving to the next level, making it suitable for finding shortest paths. DFS uses a stack data structure and searches as far as possible down each branch before backtracking, making it suitable for applications like game solving where exploring all paths is important. While both have the same time complexity of O(V+E), BFS requires more memory than DFS.

    Copyright:

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

    Differences between BFS & DFS

    S. No. Parameters BFS DFS

    BFS stands for Breadth First DFS stands for Depth First
    1. Stands for
    Search. Search.

    BFS(Breadth First Search) uses


    DFS(Depth First Search) uses
    2. Data Structure Queue data structure for finding
    Stack data structure.
    the shortest path.

    DFS is also a traversal approach


    BFS is a traversal approach in in which the traverse begins at
    which we first walk through all the root node and proceeds
    3. Definition
    nodes on the same level before through the nodes as far as
    moving on to the next level. possible until we reach the node
    with no unvisited nearby nodes.

    BFS can be used to find a single


    source shortest path in an
    In DFS, we might traverse
    unweighted graph because, in
    4. Technique through more edges to reach a
    BFS, we reach a vertex with a
    destination vertex from a source.
    minimum number of edges from
    a source vertex.

    Conceptual BFS builds the tree level by DFS builds the tree sub-tree by
    5.
    Difference level. sub-tree.

    It works on the concept of FIFO It works on the concept of LIFO


    6. Approach used
    (First In First Out). (Last In First Out).

    BFS is more suitable for


    DFS is more suitable when there
    7. Suitable for searching vertices closer to the
    are solutions away from source.
    given source.

    DFS is more suitable for game or


    BFS considers all neighbors puzzle problems. We make a
    Suitability for first and therefore not suitable decision, and the then explore all
    8.
    Decision-Trees for decision-making trees used paths through this decision. And
    in games or puzzles. if this decision leads to win
    situation, we stop.
    Differences between BFS & DFS
    S. No. Parameters BFS DFS

    The Time complexity of BFS is `The Time complexity of DFS is


    O(V + E) when Adjacency List also O(V + E) when Adjacency
    Time is used and O(V^2) when List is used and O(V^2) when
    9.
    Complexity Adjacency Matrix is used, Adjacency Matrix is used, where
    where V stands for vertices and V stands for vertices and E
    E stands for edges. stands for edges.

    Visiting of
    Here, siblings are visited before Here, children are visited before
    10. Siblings/
    the children. the siblings.
    Children

    Removal of Nodes that are traversed several The visited nodes are added to
    11. Traversed times are deleted from the the stack and then removed when
    Nodes queue. there are no more nodes to visit.

    DFS algorithm is a recursive


    In BFS there is no concept of
    12. Backtracking algorithm that uses the idea of
    backtracking.
    backtracking

    BFS is used in various DFS is used in various


    13. Applications applications such as bipartite applications such as acyclic
    graphs, shortest paths, etc. graphs and topological order etc.

    14. Memory BFS requires more memory. DFS requires less memory.

    BFS is optimal for finding the DFS is not optimal for finding
    15. Optimality
    shortest path. the shortest path.

    DFS has lesser space complexity


    In BFS, the space complexity is
    Space because at a time it needs to store
    16. more critical as compared to
    complexity only a single path from the root
    time complexity.
    to the leaf node.

    BFS is slow as compared to


    17. Speed DFS is fast as compared to BFS.
    DFS.
    Differences between BFS & DFS
    S. No. Parameters BFS DFS

    Tapping in In BFS, there is no problem of In DFS, we may be trapped in


    18,
    loops trapping into infinite loops. infinite loops.

    When the target is close to the When the target is far from the
    19. When to use?
    source, BFS performs better. source, DFS is preferable.

    You might also like