# Minimum Spanning Tree
**URL:** https://discourse.julialang.org/t/minimum-spanning-tree/35845
**Category:** General Usage
**Created:** [March 11, 2020, 4:29pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845 "2020-03-11T16:29:01Z")
**Posts on this page:** 10
**Page:** 1
### Author:  [@JosenildoFerreira](https://discourse.julialang.org/u/JosenildoFerreira)
#### Post date: [March 11, 2020, 4:29pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/1 "2020-03-11T16:29:01Z")
Hi everyone, I want the vectors combination of a minimum spanning tree. I don’t think that I was very clear, but its like the following example, I have this array, generated by the function kruskal\_mst from the LightGraphs package:
`12-element Array{Array{Int64,1},1}:`
` [1, 2] `
`[2, 3] `
`[3, 4] `
`[3, 8] `
`[4, 5] `
`[4, 6] `
`[6, 7] `
`[8, 9] `
`[9, 10] `
` [10, 11]`
`[11, 12]`
` [12, 13]`
But the result I want is this one (some of the combinations that I saw):
`[1, 2, 3, 4, 5]`
`[1, 2, 3, 8, 9, 10, 11, 12, 13]`
`[1, 2, 3, 4, 6, 7]`
`[7, 6, 4, 3, 8, 9, 10, 11, 12, 13]`
What I coded until now is a great mess that only combine, sometimes wrongly, some of the vertices of the initial array, so I’m asking if anyone knows anything that can do what I want.
---
### Author:  [@anon94023334](https://discourse.julialang.org/u/anon94023334)
#### Post date: [March 11, 2020, 5:00pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/2 "2020-03-11T17:00:08Z")
Just off the top of my head (and if I’m understanding the problem correctly), what you want to do is create the subgraph with those array elements as edges, and then use something like dfs to pull out all the paths. That’s going to be very expensive, I think, and I don’t have a quick solution in code for this right now. (The new 1.4.0 / 2.0.0 code should make this easier but it’s not ready for prime time yet.)
---
### Author:  [@JosenildoFerreira](https://discourse.julialang.org/u/JosenildoFerreira)
#### Post date: [March 11, 2020, 5:33pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/3 "2020-03-11T17:33:01Z")
Yes, even though i was trying to make it hard, you do get it, I was wanting a array with all possible paths.
Thanks for the information.
---
### Author:  [@anon94023334](https://discourse.julialang.org/u/anon94023334)
#### Post date: [March 11, 2020, 6:27pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/4 "2020-03-11T18:27:14Z")
So, something to try:
```julia
h = DiGraph(nv(g))
for e in kruskal_mst(g)
add_edge!(h, e)
end
f = floyd_warshall_shortest_paths(h)
p = enumerate_paths(f)
```
and then see what you can do with that output.
---
### Author:  [@jbytecode](https://discourse.julialang.org/u/jbytecode)
#### Post date: [April 23, 2024, 6:02pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/5 "2024-04-23T18:02:05Z")
The package [OperationsResearchModels.jl](https://github.com/jbytecode/OperationsResearchModels.jl) also implements the `Minimum Spanning Tree` with a more clear interface. Here is the usage:
```julia
julia> using OperationsResearchModels
julia> conns = Connection[
Connection(1, 2, 10),
Connection(2, 3, 10),
Connection(3, 4, 10),
Connection(1, 4, 10)
]
4-element Vector{Connection}:
Connection(1, 2, 10, "x12")
Connection(2, 3, 10, "x23")
Connection(3, 4, 10, "x34")
Connection(1, 4, 10, "x14")
julia> result = mst(conns)
MstResult(Connection[Connection(3, 4, 10, "x34"), Connection(1, 4, 10, "x14"), Connection(2, 3, 10, "x23")], 30.0)
julia> result.distance
30.0
julia> result.connections
3-element Vector{Connection}:
Connection(3, 4, 10, "x34")
Connection(1, 4, 10, "x14")
Connection(2, 3, 10, "x23")
```
The `Connection` struct shows the distance between nodes so `Connection(1, 2, 30)` means that the distance between nodes 1 and 2 is 30.
---
### Author:  [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)
#### Post date: [April 24, 2024, 9:22am UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/6 "2024-04-24T09:22:31Z")
What algorithm is used to construct this spanning tree? Thx.
---
### Author:  [@jbytecode](https://discourse.julialang.org/u/jbytecode)
#### Post date: [April 24, 2024, 9:28am UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/7 "2024-04-24T09:28:26Z")
It implements [Prim’s Algorithm](https://en.wikipedia.org/wiki/Prim%27s_algorithm). Starts with a random node and continuously adds a node with minimum distance to tree in each single iteration.
---
### Author:  [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)
#### Post date: [April 24, 2024, 9:34am UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/8 "2024-04-24T09:34:33Z")
Cool! Does the implementation carry over to parallel decomposed graphs?
---
### Author:  [@jbytecode](https://discourse.julialang.org/u/jbytecode)
#### Post date: [April 24, 2024, 4:32pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/9 "2024-04-24T16:32:31Z")
I did nothing for special kind of problems, just as described in Taha’s Operations Research book. The main aim of developing such a package was educational purposes only for the undergrad and grad students which take OR and related courses.
---
### Author:  [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)
#### Post date: [April 24, 2024, 4:35pm UTC](https://discourse.julialang.org/t/minimum-spanning-tree/35845/10 "2024-04-24T16:35:22Z")
Cool! Congrats.