org.graphstream.algorithm

## Class Prim

• All Implemented Interfaces:
Algorithm, SpanningTree

```public class Prim
extends Kruskal```
Compute a spanning tree using the Prim algorithm.

Prim's algorithm is an algorithm which allows to find a minimal spanning tree in a weighted connected graph. More informations on Wikipedia.

## Example

The following example generates a graph with the Dorogovtsev-Mendes generator and then compute a spanning-tree using the Prim algorithm. The generator creates random weights for edges that will be used by the Prim algorithm. If no weight is present, algorithm considers that all weights are set to 1. When an edge is in the spanning tree, the algorithm will set its "ui.class" attribute to "intree", else the attribute is set to "notintree". According to the css stylesheet that is defined, spanning will be displayed with thick black lines while edges not in the spanning tree will be displayed with thin gray lines.
``` import org.graphstream.graph.Graph;
import org.graphstream.graph.implementations.DefaultGraph;

import org.graphstream.algorithm.Prim;
import org.graphstream.algorithm.generator.DorogovtsevMendesGenerator;

public class PrimTest {

public static void main(String... args) {
DorogovtsevMendesGenerator gen = new DorogovtsevMendesGenerator();
Graph graph = new DefaultGraph("Prim Test");

String css = "edge .notintree {size:1px;fill-color:gray;} "
+ "edge .intree {size:3px;fill-color:black;}";

graph.display();

gen.setEdgeAttributesRange(1, 100);
gen.begin();
for (int i = 0; i < 100 && gen.nextEvents(); i++)
;
gen.end();

Prim prim = new Prim("ui.class", "intree", "notintree");

prim.init(graph);
prim.compute();
}
}
```
`AbstractSpanningTree`
Computational Complexity:
0(m + n log n), where m is the number of edges and n is the number of nodes in the graph
Scientific Reference:
R. C. Prim: Shortest connection networks and some generalizations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401

• ### Fields inherited from class org.graphstream.algorithm.Kruskal

`DEFAULT_WEIGHT_ATTRIBUTE`
• ### Constructor Summary

Constructors
Constructor and Description
`Prim()`
Create a new Prim's algorithm.
```Prim(java.lang.String flagAttribute, java.lang.Object flagOn, java.lang.Object flagOff)```
Create a new Prim's algorithm.
```Prim(java.lang.String weightAttribute, java.lang.String flagAttribute)```
Create a new Prim's algorithm.
```Prim(java.lang.String weightAttribute, java.lang.String flagAttribute, java.lang.Object flagOn, java.lang.Object flagOff)```
Create a new Prim's algorithm.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`java.lang.String` `defaultResult()`
• ### Methods inherited from class org.graphstream.algorithm.Kruskal

`clear, getTreeEdgesStream, getTreeWeight, getWeightAttribute, setWeightAttribute`
• ### Methods inherited from class org.graphstream.algorithm.AbstractSpanningTree

`compute, getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOn`
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### Prim

`public Prim()`
Create a new Prim's algorithm. Uses the default weight attribute and does not tag the edges.
• #### Prim

```public Prim(java.lang.String weightAttribute,
java.lang.String flagAttribute)```
Create a new Prim's algorithm. The value of the flag attribute is `true` for the tree edges and false for the non-tree edges.
Parameters:
`weightAttribute` - attribute used to compare edges
`flagAttribute` - attribute used to set if an edge is in the spanning tree
• #### Prim

```public Prim(java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)```
Create a new Prim's algorithm. Uses the default weight attribute.
Parameters:
`flagAttribute` - attribute used to set if an edge is in the spanning tree
`flagOn` - value of the flagAttribute if edge is in the spanning tree
`flagOff` - value of the flagAttribute if edge is not in the spanning tree
• #### Prim

```public Prim(java.lang.String weightAttribute,
java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)```
Create a new Prim's algorithm.
Parameters:
`weightAttribute` - attribute used to compare edges
`flagAttribute` - attribute used to set if an edge is in the spanning tree
`flagOn` - value of the flagAttribute if edge is in the spanning tree
`flagOff` - value of the flagAttribute if edge is not in the spanning tree
• ### Method Detail

• #### defaultResult

`public java.lang.String defaultResult()`
Overrides:
`defaultResult` in class `Kruskal`