Chapter 39: Graphs (Part 5)

"Mastering Graph Algorithms: Cheapest Flights, Connecting Cities, and More in Java"

---

Introduction

In this chapter, we delve deeper into the fascinating world of graphs, focusing on practical applications related to finding optimal paths and connections. Graphs are vital data structures that model relationships and connections between entities. Our exploration will cover algorithms and concepts such as finding the cheapest flight within a limited number of stops, connecting cities, the Disjoint Set Union (DSU) for managing connected components, and more.

1. Cheapest Flight Within K Stops

One of the most common graph problems is determining the cheapest flight between two cities while allowing for a maximum number of stops. This problem can be visualized using a directed weighted graph, where nodes represent cities and edges represent the cost of flights.

To solve this problem, we can use a variation of Dijkstra's algorithm or a breadth-first search (BFS) approach while keeping track of the number of stops. Below is the code implementation:

Code Implementation

import java.util.*;

public class CheapestFlights {
    static class Flight {
        String destination;
        int price;

        Flight(String destination, int price) {
            this.destination = destination;
            this.price = price;
        }
    }

    public int findCheapestPrice(int n, int[][] flights, String src, String dst, int k) {
        Map<String, List<Flight>> graph = new HashMap<>();
        for (int[] flight : flights) {
            String u = String.valueOf(flight[0]);
            String v = String.valueOf(flight[1]);
            int price = flight[2];
            graph.putIfAbsent(u, new ArrayList<>());
            graph.get(u).add(new Flight(v, price));
        }

        PriorityQueue<Object[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> (int) o[1]));
        pq.offer(new Object[]{src, 0, 0}); // {city, cost, stops}

        while (!pq.isEmpty()) {
            Object[] curr = pq.poll();
            String city = (String) curr[0];
            int cost = (int) curr[1];
            int stops = (int) curr[2];

            if (city.equals(dst)) {
                return cost;
            }

            if (stops > k) continue;

            for (Flight flight : graph.getOrDefault(city, new ArrayList<>())) {
                pq.offer(new Object[]{flight.destination, cost + flight.price, stops + 1});
            }
        }

        return -1; // return -1 if destination is unreachable within k stops
    }
}

2. Connecting Cities

The problem of connecting cities can be approached similarly to the Minimum Spanning Tree (MST) problem, where the goal is to connect all cities with the minimum total cost. This can be achieved using algorithms like Kruskal's or Prim's algorithm.

Code Implementation

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;

        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

3. Disjoint Set Union (DSU)

The Disjoint Set Union (DSU) is a data structure that keeps track of elements partitioned into disjoint (non-overlapping) subsets. It supports efficient union and find operations.

Key Operations:

• Find: Determine which subset a particular element is in.

• Union: Join two subsets into a single subset.

4. Kruskal's Algorithm

Kruskal's algorithm is used to find the minimum spanning tree of a graph. It works by sorting all the edges of the graph in non-decreasing order of their weight and adding them one by one to the MST, ensuring that no cycles are formed.

Code Implementation

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }

    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class KruskalMST {
    public List<Edge> kruskal(int n, List<Edge> edges) {
        Collections.sort(edges);
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();

        for (Edge edge : edges) {
            if (uf.union(edge.src, edge.dest)) {
                mst.add(edge);
            }
        }

        return mst;
    }
}

5. Flood Fill Algorithm

The Flood Fill algorithm is used to determine the area connected to a given node in a multi-dimensional array. It is commonly used in paint bucket tools in graphics software.

Code Implementation

public class FloodFill {
    public void floodFill(int[][] image, int sr, int sc, int newColor) {
        int originalColor = image[sr][sc];
        if (originalColor == newColor) return;
        dfs(image, sr, sc, originalColor, newColor);
    }

    private void dfs(int[][] image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.length || y < 0 || y >= image[0].length || image[x][y] != originalColor) {
            return;
        }
        image[x][y] = newColor;
        dfs(image, x + 1, y, originalColor, newColor);
        dfs(image, x - 1, y, originalColor, newColor);
        dfs(image, x, y + 1, originalColor, newColor);
        dfs(image, x, y - 1, originalColor, newColor);
    }
}

6. Solved Practice Set Questions

To solidify your understanding, here are some practice problems related to this chapter:

---