1
$\begingroup$

I need to describe (even in words) an algorithm that gets a connected, undirected, weighted graph so that the weight of each edge is either 1,2 or 3; and returns MST of that graph is time complexity O(|V|+|E|).

I thought to take kruskal algorithm and change the sorting algorithm to be counting sort (O(|E|) instead of comparison based sort (O|ElogE|) however this doesn't give well enough time complexity because of the "cost" of the set data-stracture (makeset,findset,union). Maybe some modification of the Prim's algorithm can work although I can't think of anything.

I'd love to get some help with this; I am struggling to find anything that would work in the required time complexity.

Thank you in advance!

$\endgroup$

1 Answer 1

2
$\begingroup$

You should use Prim's algorithm instead of Kruskal's algorithm.

Given a weighted undirected graph $G = (V, E, f)$ with $f(E) \subseteq \{1, 2, 3\}$ as an adjacency lists array, the following should work:

  • Let $W$ be a boolean array of length $n = |V|$, with all values set to false, except $W[0]$ set to true.
  • Let $T$ be a graph (as an adjacency lists array) with $n$ vertices and no edge.
  • Let $E_1$ (resp. $E_2$ and $E_3$) be the sets (or linked lists, as your prefer) of edges incident to the vertex $0$ of weight $1$ (resp. 2 and 3).
  • While $T$ has less than $n-1$ edges:
    • pick $\{u, v\}$ an edge in $E_1$ or $E_2$ or $E_3$ in this order, stopping with the first non empty set;
    • assume WLOG that $W[u]$ is true. If $\neg W[v]$ then:
      • add $\{u, v\}$ to $T$;
      • $W[v]\leftarrow $ true;
      • add to $E_1$ (resp. $E_2$ and $E_3$) all edges incident to the vertex $v$ of weight $1$ (resp. 2 and 3).

This is exactly Prim's algorithm, but the extraction of the minimum weight edge is done using $E_1$, $E_2$ and $E_3$, so it is done in constant time. Each edge is added and extracted from $E_i$ sets at most twice (one for each of its extremities). If an edge $\{u, v\}$ such that $W[u] \land W[v]$ is extracted, it is just ignored. All other operations in the loop are in constant time, so the overall complexity is indeed in $\mathcal{O}(|V| + |E|)$.

$\endgroup$
1
  • $\begingroup$ Thank you very much! $\endgroup$
    – DR_2001
    Commented Jan 16, 2023 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.