algorithms6GraphAlgorithms

1package pkg4algorithms;2 3/*4 * algorithms6GraphAlgorithms.java5 * --------------------6 * Dijkstra (shortest path), topological sort (Kahn's), and cycle detection7 * in a directed graph.8 *9 * COMPLEXITY: Dijkstra O((V+E) log V) with a heap; topo sort & cycle O(V+E).10 */11import java.util.*;12 13public class algorithms6GraphAlgorithms {14 15    // Dijkstra: shortest distances from src in a weighted graph with non-negative edges.16    static int[] dijkstra(int n, int[][] edges, int src) {17        List<int[]>[] adj = buildWeighted(n, edges);18        int[] dist = new int[n];19        Arrays.fill(dist, Integer.MAX_VALUE);20        dist[src] = 0;21        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));22        pq.offer(new int[]{src, 0});23        while (!pq.isEmpty()) {24            int[] cur = pq.poll();25            int u = cur[0], d = cur[1];26            if (d > dist[u]) continue;                 // stale entry27            for (int[] e : adj[u]) {28                int v = e[0], w = e[1];29                if (dist[u] + w < dist[v]) {30                    dist[v] = dist[u] + w;31                    pq.offer(new int[]{v, dist[v]});32                }33            }34        }35        return dist;36    }37 38    // Topological sort via Kahn's algorithm (BFS on in-degrees). Returns empty if cyclic.39    static List<Integer> topoSort(int n, int[][] edges) {40        List<Integer>[] adj = buildDirected(n, edges);41        int[] indeg = new int[n];42        for (int[] e : edges) indeg[e[1]]++;43        Queue<Integer> q = new LinkedList<>();44        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);45        List<Integer> order = new ArrayList<>();46        while (!q.isEmpty()) {47            int u = q.poll();48            order.add(u);49            for (int v : adj[u]) if (--indeg[v] == 0) q.offer(v);50        }51        return order.size() == n ? order : List.of();   // cycle if not all included52    }53 54    // Detect a cycle in a directed graph using DFS colors.55    static boolean hasCycle(int n, int[][] edges) {56        List<Integer>[] adj = buildDirected(n, edges);57        int[] color = new int[n];   // 0=white,1=gray(in stack),2=black(done)58        for (int i = 0; i < n; i++) if (color[i] == 0 && dfsCycle(i, adj, color)) return true;59        return false;60    }61    static boolean dfsCycle(int u, List<Integer>[] adj, int[] color) {62        color[u] = 1;63        for (int v : adj[u]) {64            if (color[v] == 1) return true;            // back edge -> cycle65            if (color[v] == 0 && dfsCycle(v, adj, color)) return true;66        }67        color[u] = 2;68        return false;69    }70 71    @SuppressWarnings("unchecked")72    static List<int[]>[] buildWeighted(int n, int[][] edges) {73        List<int[]>[] adj = new List[n];74        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();75        for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]});76        return adj;77    }78    @SuppressWarnings("unchecked")79    static List<Integer>[] buildDirected(int n, int[][] edges) {80        List<Integer>[] adj = new List[n];81        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();82        for (int[] e : edges) adj[e[0]].add(e[1]);83        return adj;84    }85 86    public static void main(String[] args) {87        // Weighted directed graph: {from, to, weight}88        int[][] wedges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}};89        System.out.println("Dijkstra from 0: " + Arrays.toString(dijkstra(4, wedges, 0)));90 91        // DAG for topo sort: {from, to}92        int[][] dag = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}};93        System.out.println("Topological order: " + topoSort(6, dag));94 95        int[][] acyclic = {{0, 1}, {1, 2}};96        int[][] cyclic = {{0, 1}, {1, 2}, {2, 0}};97        System.out.println("hasCycle(acyclic): " + hasCycle(3, acyclic));98        System.out.println("hasCycle(cyclic):  " + hasCycle(3, cyclic));99    }100}