<p>Yes, there are many such algorithms. Two of the easiest are</p>
<p>(1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort the edges by which pair of supervertices they connect, and then scan the sorted list to find blocks of edges connecting the same pair of supervertices and keep only the minimum-weight edge from each block. The time adds in a recurrence like <span class="math-container">$T(n)=O(n^2)+T(n/2)$</span> which solves to <span class="math-container">$O(n^2)$</span>.</p>
<p>(2) Use Jarník's algorithm, where you build a tree one edge at a time using a priority queue of the remaining vertices outside of the tree, prioritized by the shortest edge connecting each vertex to the tree. Only instead of using anything as sophisticated as a binary heap for your priority queue, just use an unsorted collection of vertex-priority pairs. To find the minimum priority vertex, scan the collection in time <span class="math-container">$O(n)$</span>. Then, when adding a vertex to the tree, look at all its neighboring edges and, for each neighbor that is not already in the tree, check whether the new connection to that neighbor is better than what you already had as its priority, and if so decrease the priority in its pair. There are <span class="math-container">$n$</span> scans with time <span class="math-container">$O(n)$</span>, and <span class="math-container">$O(n^2)$</span> neighbor checks with time <span class="math-container">$O(1)$</span>, so the total time is <span class="math-container">$O(n^2)$</span>.</p>
<p>Randomization (which can achieve linear expected time for sparser graphs) is not needed here.</p>

CC BY-SA 4.0
2021-10-16T14:05:35.403Z
I wasn't thinking straight when I made my earlier comment (which I removed to not confuse potential readers). In the dense graph regime algorithms that run in $O(m + n \log n)$ time become $O(m)$ when $m = \Omega(n \log n)$. One can do away with priority queues etc as David notes above if we only want $O(n^2)$.
Chandra Chekuri
CC BY-SA 4.0
2021-10-18T00:17:20.463Z
Amazing! .......
ErroR
CC BY-SA 4.0
2021-10-18T05:37:13.633Z
What could be more elating to see - A teacher, an author of DS answering for DS!
Ravi Tiwari
CC BY-SA 4.0
2021-10-16T07:26:37.090Z
2021-10-16T07:26:37.090Z
David Eppstein
<p>Given completed metric weighted graph <span class="math-container">$G=(V,E)$</span> that have <span class="math-container">$n$</span> vertices. Are there an algorithm that find MST of <span class="math-container">$G$</span> in <span class="math-container">$O(n^2)$</span>?</p>
<p>I read abstract of <a href="https://link.springer.com/article/10.1007/BF02579168" rel="nofollow noreferrer">this paper</a> that mentioned an algorithm with running time <span class="math-container">$O(n^2\log\log^*n)$</span>. But i want know that, <span class="math-container">$O(n^2\log\log^*n)$</span> is lower bound or there is efficient algorithm that run in <span class="math-container">$O(n^2)$</span>.</p>

<ds.algorithms><graph-theory><graph-algorithms>
Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?
ErroR
# Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

(Asked by: username_0 on 2021-10-15)

Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$?

I read abstract of [this paper](https://link.springer.com/article/10.1007/BF02579168) that mentioned an algorithm with running time $O(n^2\log\log^\*n)$. But i want know that, $O(n^2\log\log^\*n)$ is lower bound or there is efficient algorithm that run in $O(n^2)$.

**Tags:** ds.algorithms, graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2021-10-16. Score: 5 | Accepted answer

Yes, there are many such algorithms. Two of the easiest are

(1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort the edges by which pair of supervertices they connect, and then scan the sorted list to find blocks of edges connecting the same pair of supervertices and keep only the minimum-weight edge from each block. The time adds in a recurrence like $T(n)=O(n^2)+T(n/2)$ which solves to $O(n^2)$.

(2) Use Jarník's algorithm, where you build a tree one edge at a time using a priority queue of the remaining vertices outside of the tree, prioritized by the shortest edge connecting each vertex to the tree. Only instead of using anything as sophisticated as a binary heap for your priority queue, just use an unsorted collection of vertex-priority pairs. To find the minimum priority vertex, scan the collection in time $O(n)$. Then, when adding a vertex to the tree, look at all its neighboring edges and, for each neighbor that is not already in the tree, check whether the new connection to that neighbor is better than what you already had as its priority, and if so decrease the priority in its pair. There are $n$ scans with time $O(n)$, and $O(n^2)$ neighbor checks with time $O(1)$, so the total time is $O(n^2)$.

Randomization (which can achieve linear expected time for sparser graphs) is not needed here.

> **Comments:**
> **username_2**: I wasn't thinking straight when I made my earlier comment (which I removed to not confuse potential readers). In the dense graph regime algorithms that run in $O(m + n \log n)$ time become $O(m)$ when $m = \Omega(n \log n)$. One can do away with priority queues etc as David notes above if we only want $O(n^2)$.  
> **username_0**: Amazing! .......  
> **username_3**: What could be more elating to see - A teacher, an author of DS answering for DS!  

---

