Mastering Algorithms with C

Name

mst

Synopsis

int mst(Graph *graph, const MstVertex *start, List *span, int (*match) 
   (const void *key1, const void *key2));

Return Value

0 if computing the minimum spanning tree is successful, or -1 otherwise.

Description

Computes a minimum spanning tree for an undirected, weighted graph specified by graph. The minimum spanning tree is computed starting from the vertex specified by start. The operation modifies graph, so a copy should be made before calling the operation, if necessary. Each vertex in graph must contain data of type MstVertex. Assign a weight to each edge by setting the weight member of the MstVertex structure passed as data2 to graph_ins_edge. Use the data member of each MstVertex structure to store data associated with the vertex, such as an identifier. The match function for graph, which is set by the caller when initializing the graph with graph_init, should compare only the data members of MstVertex structures. This is the same function that should be passed as the match argument to mst. Once computed, information about the minimum spanning tree is returned in span, which is a list of MstVertex structures. In span, the vertex whose parent is set to NULL is the vertex at the root of the minimum spanning tree. The parent member of every other vertex points to the vertex that precedes it in the span. The vertices in span point to actual vertices in graph, so the caller must ensure that the storage in graph remains valid as long as span is being accessed. Use list_destroy ...