Kruskal's Algorithm | Graaf lib (original) (raw)

Kruskal's algorithm finds the minimum spanning forest of an undirected edge-weighted graph. If the graph is connected, it finds a minimum spanning tree. The algorithm is implemented with disjoint set union and finding minimum weighted edges. Worst-case performance is O(|E|log|V|), where |E| is the number of edges and |V| is the number of vertices in the graph. Memory usage is O(V+E) for maintaining vertices (DSU) and edges.

Calculates the shortest path with the minimum edge sum.

In case of multiply edges with same weight leading to a vertex, prioritizing vertices with lesser vertex number.

std::sort(edges_to_process.begin(), edges_to_process.end(),
              [](detail::edge_to_process<E>& e1,
                 detail::edge_to_process<E>& e2) {
                       if (e1 != e2)
                           return e1.get_weight() < e2.get_weight();
          return e1.vertex_a < e2.vertex_a || e1.vertex_b < e2.vertex_b;
        });