Friday 19 April 2024

Simplified dfs traversal in a graph

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

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...