02-07-2013, 02:52 PM
BREADTH FIRST SEARCH ALGORITHM
BREADTH FIRST.pptx (Size: 1.37 MB / Downloads: 18)
Breadth First Search (BFS)
In graph theory, it is a graph search algorithm that begins at the root node and explores all the neighboring nodes.
Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
How it works
It is an uninformed search method that aims to expand and examine all nodes of a graph or combination of sequences by systematically searching through every solution.
From the standpoint of the algorithm, all child nodes obtained by expanding a node are added to a FIFO (i.e., First In, First Out) queue.
In typical implementations, nodes that have not yet been examined for their neighbors are placed in some container (such as a queue or linked list) called "open" and then once examined are placed in the container "closed".
SPACE COMPLEXITY
When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space complexity can be expressed as where is the cardinality of the set of vertices
If the graph is represented by an Adjacency list it occupies Θ space in memory, while an Adjacency matrix representation occupies
Advantages of Breadth-First Search
Breadth first search will never get trapped exploring the useless path forever.
If there is a solution, BFS will definitely find it out.
If there is more than one solution then BFS can find the minimal one that requires less number of steps.