1. Kruskal()：

/*	Kruskal：并查集实现，记录两点和距离，按距离升序排序，O (ElogE)*/struct Edge	{	int u, v, w;	bool operator < (const Edge &r) const {		return w < r.w;	}}edge[E];sort (edge+1, edge+1+m);if (!uf.same (x, y))	uf.Union (x, y), ans += w;

 

 

2. Prim：

O (n ^ 2)：

/*	Prim：Dijkstra思想，邻接矩阵实现，适合稠密图, O (n ^ 2)	不连通返回-1，或返回最小生成树长度(MST)*/int Prim(int s)	{	memset (vis, false, sizeof (vis));	memset (d, INF, sizeof (d));	d[s] = 0;	int ret = 0;	for (int i=1; i<=n; ++i)	{		int mn = INF, u = -1;		for (int i=1; i<=n; ++i)	{			if (!vis[i] && d[i] < mn)	mn = d[u=i];		}		if (u == -1)	return -1;		vis[u] = true;	ret += d[u];		for (int i=1; i<=n; ++i)	{			if (!vis[i] && d[i] > w[u][i])	{				d[i] = w[u][i];			}		}	}	return ret;}

 

O (ElogV)：

/*	Prim：Dijkstra思想，优先队列优化，适合稀疏图，O (ElogV)	不连通返回-1，或返回最小生成树长度(MST)*/int Prim(int s)	{	memset (vis, false, sizeof (vis));	memset (d, INF, sizeof (d));	priority_queue
     
       Q;	for (int i=head[s]; ~i; i=edge[i].nex)	{		int v = edge[i].v, w = edge[i].w;		if (d[v] > w)	{			d[v] = w;	Q.push (Edge (v, d[v]));		}	}	vis[s] = true;	d[s] = 0;	int ret = 0;	while (!Q.empty ())	{		int u = Q.top ().v;	Q.pop ();		if (vis[u])	continue;		vis[u] = true;	ret += d[u];		for (int i=head[u]; ~i; i=edge[i].nex)	{			int v = edge[i].v, w = edge[i].w;			if (!vis[v] && d[v] > w)	{				d[v] = w;	Q.push (Edge (v, d[v]));			}		}	}	return ret;}