From Newsgroup: comp.lang.tcl

I am improving the docs in the Tcllib's struct::graph::op package.

I have never used graph algorithms myself so am not familiar with them.

However, as far as I can tell, Kruskal's algorithm and Prim's algorithm
are both supposed to compute the same thing. However, in a test program
they produce different outputs.

Is this difference correct/valid?

Here's the output I get:

Kruskal’s algorithm:
AA49 connects DFW LAX
AA523 connects MIA DFW
AA903 connects JFK MIA
NW35 connects BOS JFK
SW45 connects JFK SFO
UA877 connects ORD DFW
Prim’s algorithm:
AA49 connects DFW LAX
AA523 connects MIA DFW
AA903 connects JFK MIA
DL335 connects DFW ORD
NW35 connects BOS JFK
SW45 connects JFK SFO
UA877 connects ORD DFW

Notice that Prim’s algorithm produces an extra arc, DL335.

Here's the complete test program:

#!/usr/bin/env tclsh9

package require struct::graph 2
package require struct::graph::op

try { ;# Adapted from "Data Structures and Algorithms in Java"
::struct::graph flights
flights node insert SFO
flights node insert LAX
flights node insert ORD
flights node insert DFW
flights node insert JFK
flights node insert BOS
flights node insert MIA
flights arc insert JFK SFO SW45
flights arc setweight SW45 4152
flights arc insert JFK DFW AA1387
flights arc setweight AA1387 2235
flights arc insert JFK MIA AA903
flights arc setweight AA903 1756
flights arc insert BOS JFK NW35
flights arc setweight NW35 300
flights arc insert BOS MIA DL247
flights arc setweight DL247 2027
flights arc insert MIA DFW AA523
flights arc setweight AA523 1802
flights arc insert MIA LAX AA411
flights arc setweight AA411 3763
flights arc insert LAX ORD UA120
flights arc setweight UA120 2802
flights arc insert DFW LAX AA49
flights arc setweight AA49 1983
flights arc insert DFW ORD DL335
flights arc setweight DL335 1290
flights arc insert ORD DFW UA877
flights arc setweight UA877 1290
puts "Kruskal’s algorithm:"
foreach arc [lsort [struct::graph::op::kruskal flights]] {
set pad [expr {[string length $arc] == 4 ? " " : ""}]
puts " $arc$pad connects [flights arc nodes $arc]"
}
puts "Prim’s algorithm:"
foreach arc [lsort [struct::graph::op::prim flights]] {
set pad [expr {[string length $arc] == 4 ? " " : ""}]
puts " $arc$pad connects [flights arc nodes $arc]"
}
} finally {
flights destroy
}

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl



It might be correct since there are two nodes with the same weight of 1290? i.e. There may be more than one minimum spanning tree


Mark Summerfield <m.n.summerfield@gmail.com> posted:

I am improving the docs in the Tcllib's struct::graph::op package.

I have never used graph algorithms myself so am not familiar with them.

However, as far as I can tell, Kruskal's algorithm and Prim's algorithm
are both supposed to compute the same thing. However, in a test program
they produce different outputs.

Is this difference correct/valid?

Here's the output I get:

Kruskal’s algorithm:
AA49 connects DFW LAX
AA523 connects MIA DFW
AA903 connects JFK MIA
NW35 connects BOS JFK
SW45 connects JFK SFO
UA877 connects ORD DFW
Prim’s algorithm:
AA49 connects DFW LAX
AA523 connects MIA DFW
AA903 connects JFK MIA
DL335 connects DFW ORD
NW35 connects BOS JFK
SW45 connects JFK SFO
UA877 connects ORD DFW

Notice that Prim’s algorithm produces an extra arc, DL335.

Here's the complete test program:

#!/usr/bin/env tclsh9

package require struct::graph 2
package require struct::graph::op

try { ;# Adapted from "Data Structures and Algorithms in Java"
::struct::graph flights
flights node insert SFO
flights node insert LAX
flights node insert ORD
flights node insert DFW
flights node insert JFK
flights node insert BOS
flights node insert MIA
flights arc insert JFK SFO SW45
flights arc setweight SW45 4152
flights arc insert JFK DFW AA1387
flights arc setweight AA1387 2235
flights arc insert JFK MIA AA903
flights arc setweight AA903 1756
flights arc insert BOS JFK NW35
flights arc setweight NW35 300
flights arc insert BOS MIA DL247
flights arc setweight DL247 2027
flights arc insert MIA DFW AA523
flights arc setweight AA523 1802
flights arc insert MIA LAX AA411
flights arc setweight AA411 3763
flights arc insert LAX ORD UA120
flights arc setweight UA120 2802
flights arc insert DFW LAX AA49
flights arc setweight AA49 1983
flights arc insert DFW ORD DL335
flights arc setweight DL335 1290
flights arc insert ORD DFW UA877
flights arc setweight UA877 1290
puts "Kruskal’s algorithm:"
foreach arc [lsort [struct::graph::op::kruskal flights]] {
set pad [expr {[string length $arc] == 4 ? " " : ""}]
puts " $arc$pad connects [flights arc nodes $arc]"
}
puts "Prim’s algorithm:"
foreach arc [lsort [struct::graph::op::prim flights]] {
set pad [expr {[string length $arc] == 4 ? " " : ""}]
puts " $arc$pad connects [flights arc nodes $arc]"
}
} finally {
flights destroy
}

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.tcl

On Fri, 22 May 2026 03:17:31 GMT, eeyore wrote:

It might be correct since there are two nodes with the same weight of 1290? i.e. There may be more than one minimum spanning tree

Mark Summerfield <m.n.summerfield@gmail.com> posted:

I am improving the docs in the Tcllib's struct::graph::op package.

I have never used graph algorithms myself so am not familiar with them.

However, as far as I can tell, Kruskal's algorithm and Prim's algorithm
are both supposed to compute the same thing. However, in a test program
they produce different outputs.

[snip]

Thanks, that is a help.
--- Synchronet 3.22a-Linux NewsLink 1.2