Assumption : Given Graph is connected.
PS : For Traversal in Disconnected Graph, refer the post of Detecting Cycle in Graph
PS : For Traversal in Disconnected Graph, refer the post of Detecting Cycle in Graph
import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; class TGraph { int v; ArrayList<Integer>[] alist; boolean[] visited; TGraph(int v) { this.v = v; this.alist = new ArrayList[v]; this.visited = new boolean[v]; } public void initList(){ for(int i=0;i<alist.length;i++) alist[i] = new ArrayList<Integer>(); } public void addEdge(int u,int v) { alist[u].add(v); } public void BFS(int u) { Queue<Integer> q = new LinkedList<Integer>(); q.add(u); while(!q.isEmpty()) { int v = q.poll(); visited[v] = true; for(int i=0;i<alist[v].size();i++) { int n = alist[v].get(i); if(!visited[n]) q.add(n); } System.out.print(v + " "); } } public void DFS(int u) { visited[u] = true; System.out.print(u + " "); for(int i=0;i<alist[u].size();i++) { int v = alist[u].get(i); if(!visited[v]) DFS(v); } } public static void main(String[] args) { TGraph g= new TGraph(4); g.initList(); 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("Breadth First Traversal (starting from vertex 2)"); g.BFS(2); System.out.println(); System.out.println("Depth First Traversal (starting from vertex 2)"); TGraph g1 = new TGraph(4); g1.initList(); g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 2); g1.addEdge(2, 0); g1.addEdge(2, 3); g1.addEdge(3, 3); g1.DFS(2); } }
No comments:
Post a Comment