algorithm - What's the purpose of BFS and DFS? -

algorithm - What's the purpose of BFS and DFS? -

i've learned how these algorithms work, used for?

do utilize them to:

find node in graph or to find shortest path or to find cycle in graph

?

both of them visit nodes , mark them visited, , don't see point of doing that.

i sort of lost here learning.

bfs , dfs graph search algorithms can used variety of different purposes.

one mutual application of 2 search techniques identify nodes reachable given starting node. example, suppose have collection of computers each networked handful of other computers. running bfs or dfs given node, find other computers in network original computer capable of straight or indirectly talking to. these computers come marked.

bfs can used find shortest path between 2 nodes in unweighted graph. suppose, example, want send packet 1 computer in network another, , computers aren't straight connected 1 another. along route should send packet arrive @ destination possible? if run bfs , @ each iteration have each node store pointer "parent" node, end finding route start node each other node in graph minimizes number of links have traversed reach destination computer.

dfs used subroutine in more complex algorithms. example, tarjan's algorithm computing strongly-connected components based on depth-first search. many optimizing compiler techniques run dfs on appropriately-constructed graph in order determine in order apply specific series of operations. depth-first search can used in maze generation: taking grid of nodes , linking each node neighbors, can build graph representing grid. running random depth-first search on graph produces maze has 1 solution.

this no means exhaustive list. these algorithms have sorts of applications, , start explore more advanced algorithms find relying on dfs , bfs building blocks. it's similar sorting - sorting isn't interesting, beingness able sort list of values enormously useful subroutine in more complex algorithms.

hope helps!

algorithm graph depth-first-search breadth-first-search