为了计算一个无方向的带权图的最小生成树，首先，我们要用表示图的基本抽象数据类型来表示带权图。同时，Prim算法还需要一种追踪顶点和边信息的方法。这就用到了MstVertex结构体：它用来为图中的顶点计算最小生成树。此结构包含5个成员：data是与顶点相关的数据；weight是到达该顶点的边的权值；color是顶点的颜色；key是顶点的键值；parent是最小生成树中顶点的父结点。
建立一个包含MstVertex结构体的图的过程几乎与建立一个包含其他类型的图的过程一样：要将一个顶点插入图中，调用graph_ins_vertex，并将MstVertex结构体传入data。类似地，要将一条边插入图中，调用函数graph_ins_edge，并将MstVertex结构体传入data1和data2。当插入一个顶点时，只设置MstVertex结构体的data成员。当插入一条边时，设置data1的data成员，data2的data和weight成员。在data2中，weight是边的权值，此边是data1中的顶点到data2中顶点的连接线。在实际中，权值通常用浮点数进行存储和计算。由于键值是由权值计算来的，因此键值也用浮点数表示。
mst操作首先初始化邻接表结构链表中的每个顶点。将每个顶点的键值初始化为DBL_MAX（除超始顶点外，超始顶点初始值为0.0）。在图的抽象数据类型中，图由一个邻接表结构链表来表示。每个邻接表包含一个顶点和一个相邻顶点的集合。用存储在邻接表结构中的顶点来维护顶点的色值、键值、和父结点。维护邻接表结构链表中信息的关键是能将这些信息存储起来，而不是仅仅列出与自己相邻的顶点。鉴于一个顶点可能会出现在众多的邻接表中，所以每个顶点只能在邻接表结构链表中出现一次。
Prim算法的核心是用一个单循环为图中的每个结点迭代一次。在每次迭代的过程中：
首先，在所有的白色顶点中选择键值最小的顶点。同时，在邻接表结构链表把此顶点涂黑。
接下来，遍历与所选顶点相邻的顶点。在遍历每个顶点时，检查它在邻接表结构链表中的颜色和键值。一旦获取了这些信息，就将它与所选顶点的颜色和键值进行比较。如果相邻顶点是白色，且其键值比所选顶点的小，就将所选顶点与相邻顶点之间边的权值设置为相邻顶点的键值；同时，将相邻顶点的父结点设置为所选顶点。
然后，更新存储在邻接表结构链表中相邻顶点的信息。
重复这个过程，直到所有顶点都涂黑。
一旦Prim算法中的主循环结束，最小生成树也就计算完成了。此时，将邻接表结构链表中的每个黑色MstVertex结构体插入到链表span中。在span中，父结点为NULL的顶点就是最小生成树的根结点。其他每个顶点的parent成员都指向span中位于该顶点之前的那个顶点。每个MstVertex结构体的成员weight并不经常使用，因为它只有在存储到邻接表中时才用的到。
下图显示了上面的示例图中计算最小生成树所返回的MstVertex结构体链表：
示例：图算法的头文件（含最小生成树、最短路径、旅行商问题三种实现所需函数定义的头文件）
/*graphalg.h*/ #ifndef GRAPHALG_H #define GRAPHALG_H #include "graph.h" #include "list.h" /*定义最小生成树中结点的数据结构*/ typedef struct MstVertex_ { void *data; double weight; VertexColor color; double kdy; struct MstVertex_ *parent; }MstVertex; /*定义最短路径中结点的数据结构*/ typedef struct PathVertex_ { void *data; double weight; VertexColor color; double d; struct PathVertex_ *parent; }PathVertex; /*定义旅行商问题中结点的数据结构*/ typedef struct TspVertex_ { void *data; double x,y; VertexColor color; }TspVertex; /*函数接口*/ int mst(Graph *graph, const MstVertex *start, List *span, int (*match)(const void *key1, const void *key2)); int shortest(Graph *graph, const PathVertex *start, List *paths, int(*match)(const void *key1, const void *key2)); int tsp(List *vertexs, const TspVertex *start, List *tour, int (match*)(const void *key1, const void *key2)); #endif // GRAPHALG_H