Breadth-first search in alogorithm
Download as PPTX, PDF1 like31 views
Breadth-first search (BFS) is a technique for traversing graphs where the algorithm starts at a root node and explores all neighboring nodes at the present depth prior to moving on to the nodes at the next depth level. BFS guarantees to find a solution if one exists and to find the shortest solution path. An example shows using BFS to find the shortest path between two nodes by exploring all adjacent nodes at each level before moving deeper in the graph. Applications of BFS include finding shortest paths and checking for bipartiteness in graphs.
More Related Content
More from Meherul1234 (8)
Recently uploaded (20)
Breadth-first search in alogorithm
- 1. Presentation topic Definition of Breadth-first search Feature of Breadth-first search Example of Breadth-first search Application of Breadth-first search 1
- 2. Breadth-first search Breadth-first search (BFS) is a general technique for traversing a graph. Some feature of BFS: Solution will definitely found out by BFS If there are some solution. If there are more than one solution then it will find solution with minimal steps. 2
- 3. Example Find the shortest path using BFS search 3
- 4. Solution First visit node 1 front rear Q: Visited: 个1 4
- 5. Solution Find the adjacency node 1. Q: Visited: 1 Then find the adjacency node 2 and deleted node 2 from the list Q: Visited: 1,2 Then find the adjacency node 4 and deleted node 4 from the list Q: Visited: 1,2,4 2 4 4 5 5 3 5
- 6. Solution Then find the adjacency node 5 but this node already visited so deleted node 5 from the list Q: Visited: 1,2,4,5 Then find the adjacency node 3 but this node already visited so deleted node 3 from the list Q: Visited: 1,2,4,5,3 3 个 6
- 7. Application of BFS 1.Finding Shortest Path. 2.Checking graph with bipertiteness. 7
- 8. End of the presentation Thank You 8