| Calling Sequence | MST(A)
| |||||||||
| Parameters |
| |||||||||
| Return Type | Graph | |||||||||
| Synopsis | The input to this algorithm is an undirected graph. It computes the minimum spanning tree according to Prim's algorithm. The implementation has a time complexity of O(|V|^2*log(|V|)), whereas the theoretical minimum is O(|E|). Therefore, this implementation is relatively good when working with dense graphs, in which case |E| is O(|V^2|). | |||||||||
| Examples | > hex := HexahedronGraph(); hex := Graph(Edges(Edge(0,1,2),Edge(0,1,4),Edge(0,1,5),Edge(0,2,3),Edge(0,2,6),E dge(0,3,4),Edge(0,3,7),Edge(0,4,8),Edge(0,5,6),Edge(0,5,8),Edge(0,6,7),Edge(0,7, 8)),Nodes(1,2,3,4,5,6,7,8)) > MST(hex); Graph(Edges(Edge(0,1,2),Edge(0,2,3),Edge(0,1,4),Edge(0,1,5),Edge(0,2,6),Edge(0,3 ,7),Edge(0,4,8)),Nodes(1,2,3,4,5,6,7,8)) | |||||||||
| See also | BipartiteGraph, Clique, DrawGraph, Edge, EdgeComplement, Edges, FindConnectedComponents, Graph, Graph_Rand, InduceGraph, MaxCut, MaxEdgeWeightClique, Nodes, Path, RegularGraph, ShortestPath, TetrahedronGraph, VertexCover | |||||||||