Breath First Search
// Java Breath First Search // ------------------------ import java.util.*; public class BreathFirstSearch { int V; ArrayList<Integer> adj[]; BreathFirstSearch(int noofvertex) { V = noofvertex; adj = new ArrayList[noofvertex]; for (int i = 0; i < noofvertex; i++) { adj[i] = new ArrayList<>(); } } void edge(int x, int y) { adj[x].add(y); } void bfs(int sourcevertex) { boolean[] visited = new boolean[V]; ArrayList<Integer> a1 = new ArrayList<Integer>(); visited[sourcevertex] = true; a1.add(sourcevertex); while (!a1.isEmpty()) { sourcevertex = a1.remove(0); System.out.print(sourcevertex + ""); Iterator i = adj[sourcevertex].iterator(); while (i.hasNext()) { int n = (int) i.next(); if (!visited[n]) { visited[n] = true; a1.add(n); } } } } public static void main(String[] args) { BreathFirstSearch g1 = new BreathFirstSearch(6); g1.edge(0, 1); g1.edge(0, 2); g1.edge(0, 5); g1.edge(1, 0); g1.edge(1, 2); g1.edge(2, 0); g1.edge(2, 1); g1.edge(2, 3); g1.edge(2, 4); g1.edge(3, 2); g1.edge(4, 2); g1.edge(4, 5); g1.edge(5, 0); g1.bfs(0); } }
Breadth First Search
graph = { '5' : ['3','7'], '3' : ['2', '4'], '7' : ['8'], '2' : [], '4' : ['8'], '8' : [] } visited = [] # List for visited nodes. queue = [] #Initialize a queue def bfs(visited, graph, node): #function for BFS visited.append(node) queue.append(node) while queue: # Creating loop to visit each node m = queue.pop(0) print (m, end = " ") for neighbour in graph[m]: if neighbour not in visited: visited.append(neighbour) queue.append(neighbour) # Driver Code print("Following is the Breadth-First Search") bfs(visited, graph, '5') # function calling
Source: favtutor.com
Depth First Search Vs Breadth First Search
DFS uses a stack and bfs uses a queue