Traversal meaning visiting all the nodes of a graph. Breadth first Search is also known as Breadth first traversal and is a recursive algorithm for searching all the nodes of a graph or tree data structure.
BFS algorithm
A standard BFS algorithm implementation puts each nodes of the graph or tree into one of two categories:
Visited and
Not Visited
The purpose of the algorithm is to mark each node as visited while avoiding cycles.
The algorithm works as follows:
The graph might have two different disconnected parts so to make sure that we cover every node, we can also run the BFS algorithm on every node
BFS example
Let's see how the BFS algorithm works with an example. We use an undirected graph with 5 nodes.
BFS algorithm
A standard BFS algorithm implementation puts each nodes of the graph or tree into one of two categories:
Visited and
Not Visited
The purpose of the algorithm is to mark each node as visited while avoiding cycles.
The algorithm works as follows:
- Start by putting any one of the graph's node at the back of a queue or array.
- Take the front node of the queue and add it to the visited list.
- Create a list of that node's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue.
- Keep repeating steps 2 and 3 until the queue is empty.
The graph might have two different disconnected parts so to make sure that we cover every node, we can also run the BFS algorithm on every node
BFS example
Let's see how the BFS algorithm works with an example. We use an undirected graph with 5 nodes.
We start from node 0, the BFS algorithm starts by putting it in the Visited list and putting all its adjacent nodes in the queue.
Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.
Node 2 has an unvisited adjacent node in 4, so we add that to the back of the queue and visit 3, which is at the front of the queue.
Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already visited. We visit it.
Since the queue is empty, we have completed the Depth First Traversal of the graph.
BFS pseudocode
create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u
BFS Java code
import java.io.*; import java.util.*; class Graph { private int numVertices; private LinkedListadjLists[]; private boolean visited[]; Graph(int v) { numVertices = v; visited = new boolean[numVertices]; adjLists = new LinkedList[numVertices]; for (int i=0; i i = adjLists[currVertex].listIterator(); while (i.hasNext()) { int adjVertex = i.next(); if (!visited[adjVertex]) { visited[adjVertex] = true; queue.add(adjVertex); } } } } public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal "+ "(starting from vertex 2)"); g.BFS(2); } }
Titsanium Dab Brush - 3-Inches for 1/4 inch/6 inches (4
ReplyDeleteTitsanium titanium block Dab Brush – 3-Inches for 1/4 ecm titanium inch/6 inches welding titanium (4 · titaum Titsanium Dab Brush – 3-Inches for 1/4 inch/6 inches titanium hair straightener (4