Find if Path Exists in Graph

class DisjointSet {
    vector<int> parent, size;
public:
    DisjointSet(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void union_sets(int x, int y) {
        int rootX = find(x), rootY = find(y);
        
        if (rootX != rootY) {
            if (size[rootX] > size[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }
};

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int start, int end) {
        DisjointSet ds(n);

        for (auto& edge : edges) {
            ds.union_sets(edge[0], edge[1]);
        }
        
        return ds.find(start) == ds.find(end);
    }
};

The solution implements the "Find if Path Exists in Graph" problem using a C++ program that utilizes the Disjoint Set (or Union-Find) data structure to determine if two vertices in a graph are connected. Here's a breakdown of the implementation:

• DisjointSet Class:

  • Data Members: Two vectors, parent and size, for tracking each element's root parent and the size of the tree for each root.
  • Constructor: Initializes each element to be its own parent and sets the size of each element to 1.
  • Find Method: Performs path compression to find the root parent of a vertex x.
  • Union Method: Merges two sets containing x and y using union by size, ensuring smaller trees are added under the root of larger trees to optimize the structure.

• Solution Class:

  • validPath Method: This method leverages the DisjointSet to check if there is a path between the start and end vertices.
    • First, it creates a Disjoint Set for n vertices.
    • Then, it iterates through each edge in the graph, performing a union operation on the vertices connected by the edge.
    • Finally, it checks if the root parent of the start vertex is the same as the root parent of the end vertex. If they are the same, this indicates that a path exists between the two.

The program employs the DisjointSet operations to efficiently manage and merge sets of connected components, making use of path compression and union by size to ensure that the operations are close to constant time, which is particularly beneficial for large graphs. This makes the approach well-suited for checking connectivity in dynamic networks or incrementally constructed graphs. The approach guarantees an answer through the connected nature of the vertices if they share the same representative or root in the disjoint set.

class DisjointSet {
    private int[] parent;
    private int[] size;
    public DisjointSet(int n) {
        this.parent = new int[n];
        this.size = new int[n];
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
    }   
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    public void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (size[rootX] > size[rootY]) {
                int tmp = rootX;
                rootX = rootY;
                rootY = tmp;
            }
            parent[rootX] = rootY;
            size[rootY] += size[rootX];
        }
    }
}

class PathValidator {
    public boolean hasPath(int n, int[][] connections, int start, int end) {
        DisjointSet ds = new DisjointSet(n);

        for (int[] connection : connections) {
            ds.union(connection[0], connection[1]);
        }

        return ds.find(start) == ds.find(end);
    }
}

The given Java program uses the Disjoint Set (or Union-Find) data structure to determine if a path exists between two nodes in an undirected graph. This program comprises two classes: DisjointSet and PathValidator.

• The DisjointSet class is designed to keep track of the union and find operations efficiently:

  • parent: An array where the index represents each node, and the value at each index represents the leader (or parent) of that node.
  • size: An array used for tracking the size of each tree in the forest, aiding in the union by rank.
  • find: A method employing path compression technique to find the root of each node, thus flattening the structure of the forest for quicker future operations.
  • union: A method to merge two subsets into a single subset. It attaches the tree of lesser rank under the root of the higher rank tree to keep the depth of trees smaller.

• The PathValidator class contains the method hasPath to check if a direct or indirect path exists between two given nodes:

  • It initializes a new instance of DisjointSet.
  • The method iterates through each connection (edge) and performs union operations to connect nodes.
  • Ultimately, it compares the roots (using the find method) of the start and end nodes. If these roots are the same, a path exists between the nodes, returning true. Otherwise, it returns false.

This structure and approach efficiently handle connectivity queries and manipulation of the disjoint sets, making it particularly suitable for problems related to network connectivity, like checking if a path exists between two nodes in a graph.

class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size
    def locate(self, element):
        if self.parent[element] != element:
            self.parent[element] = self.locate(self.parent[element])
        return self.parent[element]
    def merge(self, element1, element2):
        root1, root2 = self.locate(element1), self.locate(element2)
        if root1 != root2:
            if self.size[root1] < self.size[root2]:
                root1, root2 = root2, root1
            self.parent[root2] = root1
            self.size[root1] += self.size[root2]

class PathChecker:
    def hasPath(self, vertex_count: int, connections: List[List[int]], start: int, end: int) -> bool:
        ds = DisjointSet(vertex_count)

        for from_node, to_node in connections:
            ds.merge(from_node, to_node)

        return ds.locate(start) == ds.locate(end)

The solution provided uses a Disjoint Set (or Union-Find) data structure to determine if a path exists between two nodes in a graph. Here's how the implementation works:

• Disjoint Set Initialization:

  • Inside the DisjointSet class, during initialization:
    • A parent list is created where each element is initially its own parent, thus representing its own unique set.
    • A size list is initialized to keep track of the size of each set. Initially, each set (each vertex) has a size of 1.

• Locating the Root of an Element:

  • The locate method recursively finds the root of the given element and employs path compression. Path compression is a technique used to flatten the structure of the tree whenever locate is called so that all nodes directly point to the root, thereby speeding up future operations.

• Merging Two Sets:

  • The merge method unites the sets of two elements. It determines the roots of both elements, and if they are different, it merges the smaller tree under the root of the larger tree, thus balancing the tree and optimizing performance.

• Checking Path Between Two Nodes:

  • The PathChecker class defines the hasPath method, which:
    • Initializes the DisjointSet with the number of vertices in the graph.
    • Iterates through all connections (edges) in the graph, merging sets that are connected by an edge.
    • After all merges, it checks if the start and end vertices belong to the same set (i.e., have the same root), indicating that a path exists between them.

This approach ensures an efficient way to determine connectivity between any two nodes in the graph based on the edges provided, utilizing the union-find structure's ability to dynamically handle unions and finds in nearly constant time. By implementing path compression and union by size, the operations remain optimal and can handle large graphs efficiently.