GraphTraversal
Mon Aug 07 2023 04:31:41 GMT+0000 (Coordinated Universal Time)
package Graph; import java.util.ArrayList; import java.util.*; public class GraphTraversal { public static class Edge{ int src; int dest; Edge(int src , int dest){ this.dest=dest; this.src =src; } } static void creategraph(ArrayList<Edge> g []){ for(int i=0;i<g.length;i++){ g[i] = new ArrayList<>(); } g[0].add(new Edge(0,1)); g[0].add(new Edge(0,2)); g[1].add(new Edge(1,0)); g[1].add(new Edge(1,3)); g[2].add(new Edge(2,0)); g[2].add(new Edge(2,4)); g[3].add(new Edge(3,1)); g[3].add(new Edge(3,4)); g[3].add(new Edge(3,5)); g[4].add(new Edge(4,2)); g[4].add(new Edge(4,3)); g[4].add(new Edge(4,5)); g[5].add(new Edge(5,3)); g[5].add(new Edge(5,4)); g[5].add(new Edge(5,6)); g[6].add(new Edge(6,5)); } //DFS Traversal public static void dfs(ArrayList<Edge> list[], boolean[] visited, int curr){ if(visited[curr]){ return; } System.out.println(curr); visited[curr] = true; for(int i=0;i<list[curr].size();i++){ Edge e = list[curr].get(i); dfs(list,visited,e.dest); } } //BFS Traversal public static void bfs(ArrayList<Edge> list[]){ Queue<Integer> q = new LinkedList<>(); boolean visited[] = new boolean[list.length]; q.add(0); while(!q.isEmpty()){ int curr = q.remove(); if(!visited[curr]) { System.out.println(curr); visited[curr] = true; for (int i = 0; i < list[curr].size(); i++) { Edge e = list[curr].get(i); q.add(e.dest); } } } } //Finding all possible paths from one point to another point public static void ALlpaths(ArrayList<Edge> list[],boolean[] visited,int src,int d,String path){ if(src==d){ System.out.println(path); return; } for (int i = 0; i < list[src].size(); i++) { Edge e = list[src].get(i); if (!visited[e.dest]) { visited[e.dest] = true; ALlpaths(list, visited, e.dest, d, path + e.dest); visited[e.dest] = false; } } } public static void main(String[] args) { int V =7; ArrayList<Edge> list [] = new ArrayList[V]; creategraph(list); boolean b [] = new boolean[V]; int src =0; b[src]=true; // dfs(list,b,0); ALlpaths(list,b,src,5,""+src); } }
Comments