import java.util.*;
public class Main {
public static void main(String[] args) {
System.out.println("Hello World");
int V = 9; // Total number of vertices (0 to 8)
HashMap<Integer, ArrayList<Integer>> adj = makeAdjList(V);
addEdge(0, 2, adj);
addEdge(0, 1, adj);
addEdge(2, 0, adj);
addEdge(2, 4, adj);
addEdge(1, 0, adj);
addEdge(3, 0, adj);
addEdge(4, 2, adj);
addEdge(0, 3, adj);
System.out.println(adj);
boolean[] vis = new boolean[V];
List<Integer> ans = new ArrayList<>();
dfs(0, adj, vis, ans);
System.out.println("The dfs traversal of the graph is:");
System.out.println(ans);
}
// DFS of graph
public static void dfs(int src, HashMap<Integer, ArrayList<Integer>> adj, boolean[] vis, List<Integer> ans) {
vis[src] = true;
ans.add(src);
for (int it : adj.get(src)) {
if (!vis[it]) {
dfs(it, adj, vis, ans);
}
}
}
// Make adjList
public static HashMap<Integer, ArrayList<Integer>> makeAdjList(int V) {
HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
for (int i = 0; i < V; i++) {
adj.put(i, new ArrayList<Integer>());
}
return adj;
}
// Add Edge
public static void addEdge(int src, int dest, HashMap<Integer, ArrayList<Integer>> adjList) {
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
No comments:
Post a Comment