Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
KruskalGraph Algos | PrimGraph Algos | |
|---|---|---|
| Use case | Minimum spanning tree/forest when edges are given as a list. | Minimum spanning tree grown from a start vertex using adjacency lists. |
| Requirements | Sorted edge list and a Union-Find structure. | Adjacency list or matrix and a min-heap keyed by edge weight. |
| Time complexity | O(E log E) for the sort; near-constant per union/find. | O(E log V) with a heap; O(V^2) with an array, which is best for dense graphs. |
| Space complexity | O(V) for Union-Find plus the edge list. | O(V + E) for adjacency plus the heap. |
| Strengths | Simple with a DSU; works on disconnected graphs (produces a forest); edges can stream in sorted order. | Feels like Dijkstra; O(V^2) array version is optimal for dense/complete graphs; no sorting. |
| Weaknesses | Must sort all edges up front; slower on dense graphs where E ~ V^2. | Only spans the component of the start vertex; heap with lazy deletion is easy to get subtly wrong. |
| Example problems | Min cost to connect all points (sparse), redundant connection, clustering by cutting largest edges. | Min cost to connect all points (dense/complete graph), network cabling, maze generation. |
| Choose this when | Choose Kruskal when the input is an edge list, the graph is sparse, or it may be disconnected. | Choose Prim when the graph is dense (especially complete graphs of points) or you already have an adjacency structure. |