Optimizing Property Connections with Essentials Around the area

Zillow wants to enhance its platform by providing users with detailed information about the proximity of properties to key amenities like schools, parks, and public transport stops. To achieve this, Zillow aims to create an optimal network of property connections. This network will help users easily identify the shortest paths between properties and these amenities, making it simpler for them to find homes that meet their lifestyle needs.

Design Technique

Using Kruskal’s algorithm, we can create a minimum spanning tree (MST) that connects all properties and amenities with the least total distance. This will help in efficiently determining the shortest paths between different essential properties like schools,hospitals and parks.

Learn more about Minimum Spanning Tree , Union-Find Datastructure - Article

Implementation

• Lets Represent properties and amenities as nodes in a graph.
• Lets Represent the connections (distances) between them as weighted edges.
• Use a list to store all edges.
• Use a union-find data structure to manage and merge disjoint sets.
• Sorting all edges in non-decreasing order of their weight (distance).
• Iterating through the sorted edges and add the edge to the MST if it doesn’t form a cycle (using union-find).
• Repeat until the MST includes all nodes or enough edges to connect the graph.
• Using the MST to provide detailed proximity essential places to the users.

algorithm Kruskal(G) is
    F:= ∅
    for each v in G.V do
        MAKE-SET(v)
    for each {u, v} in G.E ordered by weight({u, v}), increasing do
        if FIND-SET(u) ≠ FIND-SET(v) then
            F := F ∪ { {u, v} }
            UNION(FIND-SET(u), FIND-SET(v))
    return F

Time and Space Complexity.

• Time Complexity: O(E log E ) E:Edges in spanning Tree
• Space Complexity: O(V + E) V: Number of vertices(properties)

Here is the full code implementation Code