Kruskal

加边法求最小生成树

void Kruskal(MatGraph *g)
{
	int i, j, k;
	int u1, v1;
	int sn1, sn2;
	Edge E[MAXV];
	int vset[MAXV];
	k = 0;
	for (i = 0; i < g->n; i++)
	{
		for (j = 0; j <= i; j++)
		{
			if (g->edges[i][j] > 0)
			{
				E[k].u = i;
				E[k].v = j;
				E[k].w = g->edges[i][j];
				k++;
			}
		}
	}
	sort(E, g->e);
	for (i = 0; i < g->n; i++)
		vset[i] = i;
	k = 1;
	j = 0;
	while (k < g->n)
	{
		u1 = E[j].u;
		v1 = E[j].v;
		sn1 = vset[u1];
		sn2 = vset[v1];
		if (sn1 != sn2)
		{
			printf("(%d,%d):%d\n", u1, v1, E[j].w);
			k++;
			for (i = 0; i < g->n; i++)
			{
				if (vset[i] == sn2)
					vset[i] = sn1;
			}
		}
		j++;
	}
}

  

上一篇:securecrt终端显示乱码问题


下一篇:SecureCRT 选择Courier New等其他字体.