3 Prim算法的设计

此问题要求回答如何用算法实现以下四个操作：
1）创建无向图的邻接表存储；
2）输出邻接表；
3）广度优先遍历无向图；
4）用Prim算法构造无向图的最小生成树。

回答：

1）创建无向图的邻接表存储：
对于一个无向图G(V, E)，可以创建一个大小为V的向量adj，其中每个元素adj[i]都是一个链表，存储了顶点i相邻的顶点。

2）输出邻接表：
对于向量adj中的每个链表，依次输出链表中存储的顶点即可。

3）广度优先遍历无向图：
从任意一个顶点开始，先将该顶点入队，再按照队列的先进先出原则依次遍历相邻的所有顶点，并将它们入队，直到所有可达的节点都被遍历。

4）用Prim算法构造无向图的最小生成树：
从一个任意节点开始，将它标记为已被访问，然后将所有与它相邻的未访问节点加入到一个最小堆中。每次从最小堆中取出一个最小边的未访问节点，将其加入到已访问节点集合，并将其所有未访问的相邻节点加入到最小堆中。重复以上的操作直到所有节点都被访问，最终得到最小生成树。