/Assignment3-DAA

Primary LanguageJava

Analytical Report: Optimization of a City Transportation Network

Student: Yerassyl Unerbek
Group: SE-2402

1. Summary of Input Data and Algorithm Results

This report analyzes the performance of Prim’s and Kruskal’s algorithms for finding the Minimum Spanning Tree (MST) of two sample city transportation networks. The input data and performance results are summarized below.

Input Data

  • Graph 1: A network of 5 districts (vertices) and 7 potential roads (edges).
  • Graph 2: A network of 4 districts (vertices) and 5 potential roads (edges).

Algorithm Results

The algorithms were executed on both graphs, and the following metrics were recorded.
Note: Execution times are based on the provided ass_3_output (1).json file.

Graph ID Algorithm Vertices (V) Edges (E) MST Total Cost Operations Count Execution Time (ms)
1 Prim’s 5 7 16 42 1.52
1 Kruskal’s 5 7 16 37 1.28
2 Prim’s 4 5 6 29 0.87
2 Kruskal’s 4 5 6 31 0.92

Both algorithms correctly produced the same total cost for the MST in both test cases, confirming their correctness.

2. Comparison of Prim’s and Kruskal’s Algorithms

Theoretical Efficiency (Time Complexity)

  • Prim’s Algorithm:

    • Using adjacency matrix / simple array: $O(V^2)$
    • Using binary heap (PriorityQueue): $O(E \log V)$
    • Using Fibonacci heap: $O(E + V \log V)$

  • Kruskal’s Algorithm:

    • Sorting all $E$ edges: $O(E \log E)$
    • Union-Find operations: $O(E \cdot \alpha(V))$ (≈ linear in practice)
    • Total: $O(E \log E)$

Performance Analysis (Based on Results)

  • Graph 1 (V=5, E=7):
    Kruskal’s algorithm was faster (1.28 ms vs. 1.52 ms) and required fewer operations (37 vs. 42). The graph is sparse, so sorting few edges was cheaper than maintaining Prim’s priority queue.

  • Graph 2 (V=4, E=5):
    Prim’s algorithm was slightly faster (0.87 ms vs. 0.92 ms). The difference is negligible and may be due to runtime factors such as JVM warm-up.

Both graphs are sparse ($E$ close to $V$, not $V^2$), so Kruskal’s efficiency advantage is expected.

Implementation Complexity

  • Prim’s Algorithm:
    Requires a min-heap (PriorityQueue) and an adjacency list. It incrementally “grows” the MST, making it intuitive but more stateful.

  • Kruskal’s Algorithm:
    Simpler main loop (sort edges, union if no cycle).
    Depends on a Disjoint Set (Union-Find) structure, which requires careful implementation (path compression, union by rank).

3. Conclusions: Which Algorithm is Preferable?

The choice depends on graph density:

  1. Sparse Graphs (like city networks):

    • ✅ Kruskal’s Algorithm is preferred.
    • $E \approx O(V)$ ⇒ $O(E \log E)$ is highly efficient.
    • Involves one sort vs. many heap operations in Prim’s.

  2. Dense Graphs (fully connected networks):

    • ✅ Prim’s Algorithm is preferred.
    • For $E \approx O(V^2)$, Prim’s array-based $O(V^2)$ implementation can outperform Kruskal’s $O(E \log E)$.

Final Recommendation:
For real-world city transportation networks (which are sparse), Kruskal’s Algorithm is more efficient and straightforward to use.

4. Build and Execution Commands

This project uses Apache Maven for build and dependency management.

Build

Run from the project root:

mvn clean package

This creates target/city-mst-optimizer-1.0.0-jar-with-dependencies.jar

Execution

Run the program with two arguments:

  • Path to the input JSON file
  • Path to the output JSON file

Example:

java -jar target/city-mst-optimizer-1.0.0-jar-with-dependencies.jar "ass_3_input (1).json" "ass_3_output (1).json"