void Kruskal(Graph* g) { int i, j, k = 0; struct { ElementType head; ElementType tail; EdgeType cost; }edge[MaxVexNum],t; int vexSet[MaxVexNum]; for (i = 0; i < g->vexNum; i++) { //遍历矩阵的下三角元素 for (j = 0; j < i; j++) { if (g->edge[i][j] != INFINITY) { edge[k].head = i; edge[k].tail = j; edge[k++].cost = g->edge[i][j]; } } } for (i = 0; i < g->vexNum; i++) vexSet[i] = i; //各个顶点自成一个连通分量 for (i = 0; i < g->edgeNum-1; i++) { for (j = g->edgeNum-1; j >= i + 1; j--) { if (edge[j].cost < edge[j - 1].cost) { t = edge[j-1]; edge[j-1] = edge[j]; edge[j] = t; } } } for (i = 0; i < g->edgeNum; i++) { int vs1, vs2; vs1 = vexSet[edge[i].head]; vs2 = vexSet[edge[i].tail]; if (vs1 != vs2) { printf("(%c,%c)", g->vex[edge[i].tail], g->vex[edge[i].head]); for (j = 0; j < g->edgeNum; j++) { if (vexSet[j] == vs2) vexSet[j] = vs1; } } } }

这是一个基于Kruskal算法实现的最小生成树算法。其思路是先将图中的所有边按照权值排序，然后从小到大依次加入边，如果加入的边不会形成环，则将其加入最小生成树中，否则舍弃该边。具体实现过程如下：

1. 定义一个结构体数组edge，记录每条边的起点、终点和权值；
2. 定义一个数组vexSet，记录每个顶点所属的连通分量，初始状态下每个顶点自成一个连通分量；
3. 将所有边按照权值从小到大排序；
4. 依次遍历每条边，如果该边的起点和终点不在同一个连通分量中，则将其加入最小生成树中，并将其起点所在的连通分量的所有顶点都归为终点所在的连通分量中。

其中，关键的部分就是如何判断一个边的起点和终点是否在同一个连通分量中。这里使用了一个数组vexSet来记录每个顶点所属的连通分量，初始状态下每个顶点自成一个连通分量。在遍历边的过程中，每当遇到一条边的起点和终点不在同一个连通分量中时，就将起点所在的连通分量中的所有顶点都归为终点所在的连通分量中，即将vexSet数组中所有值为起点所在连通分量的顶点都改为终点所在的连通分量的编号。这样，就可以很方便地判断起点和终点是否在同一个连通分量中了。

最后，遍历完所有边后，就得到了最小生成树。

相关问题

void Kruskal(MatGraph g) { int i,j,u1,v1,sn1,sn2,k; int vset[MAXV]; Edge E[MAXV]; k=0; for(i=0;i<g.n;i++) if(g.edges[i][j]!=0 && g.edges[i][j]!=INF) { E[k].u=i; E[k].v=j; E[k].w=g.edges[i][j]; k++; } InsertSort(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++; } }

这是一个基于 Kruskal 算法实现的最小生成树算法，其中 `MatGraph` 是图的邻接矩阵表示。下面对代码进行解释：

1. `Edge E[MAXV]` 定义了一个数组，用于存储所有边的信息，包括起点、终点和权值。`k` 用于记录边的数量。

2. `InsertSort(E,g.e)` 对边进行排序，这里使用的是插入排序，`g.e` 是边的数量。

3. `vset[MAXV]` 定义了一个数组，用于记录每个顶点所在的集合，初始状态下每个顶点都是独立的一个集合。

4. `k=1` 表示已经选择了一个顶点，`j=0` 表示当前处理的边的下标。

5. `while(k<g.n)` 表示还没有选择完所有的顶点，即还有顶点没有被加入最小生成树中。

6. `u1=E[j].u` 和 `v1=E[j].v` 表示当前处理的边的起点和终点。

7. `sn1=vset[u1]` 和 `sn2=vset[v1]` 表示 `u1` 和 `v1` 所在的集合。

8. 如果 `sn1!=sn2`，表示 `u1` 和 `v1` 不在同一个集合中，那么将它们加入同一个集合中，并输出当前边。

9. `j++` 表示处理下一条边。

下面是 C++ 代码实现：

void Kruskal(MatGraph g) {
    int i, j, u1, v1, sn1, sn2, k;
    int vset[MAXV];
    Edge E[MAXV];
    k = 0;
    for (i = 0; i < g.n; i++)
        for (j = 0; j < g.n; j++)
            if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
                E[k].u = i;
                E[k].v = j;
                E[k].w = g.edges[i][j];
                k++;
            }
    InsertSort(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++;
    }
}

已知图结构定义：typedef struct GraphAdjMatrix { elementType Data[MaxVerNum+1]; cellType AdjMatrix[MaxVerNum+1][MaxVerNum+1]; int VerNum; int ArcNum; GraphKind gKind; } Graph;可调用以下函数：int LocateVertex(Graph &G, elementType v)；int firstAdj(Graph &G,int v)；int nextAdj(Graph &G,int v,int w)；试写出下列问题的代码：1、对给定的图G及出发点v0，设计算法从V0出发深度优先遍历图G，并构造出相应的生成树或生成森林。2、对给定的图G及出发点v0，设计算法从V0出发广度优先遍历图G，并构造出相应的生成树或生成森林。3、实现Prim算法，求解下列给定图G的最小生成树。4、实现Kruskal算法，求解下列给定图G的最小生成树。

1、从出发点v0开始深度优先遍历图G的代码如下：

void DFS(Graph &G, int v, bool visited[], int parent[]) {
visited[v] = true; // 标记v已访问
for (int w = firstAdj(G, v); w >= 0; w = nextAdj(G, v, w)) { // 遍历v的所有邻接点
if (!visited[w]) { // 若w未被访问
parent[w] = v; // 记录v是w的父亲节点
DFS(G, w, visited, parent); // 递归访问w
}
}
}

void DFSTraverse(Graph &G, int v0, bool visited[], int parent[]) {
for (int i = 1; i <= G.VerNum; i++) {
visited[i] = false; // 初始化visited数组
parent[i] = -1; // 初始化parent数组
}
DFS(G, v0, visited, parent); // 从出发点v0开始深度优先遍历
}

2、从出发点v0开始广度优先遍历图G的代码如下：

void BFSTraverse(Graph &G, int v0, bool visited[], int parent[]) {
queue<int> Q; // 定义队列
visited[v0] = true; // 标记v0已访问
Q.push(v0); // 将v0入队
while (!Q.empty()) { // 队列不为空时
int v = Q.front(); // 取队首元素v
Q.pop(); // 将v出队
for (int w = firstAdj(G, v); w >= 0; w = nextAdj(G, v, w)) { // 遍历v的所有邻接点
if (!visited[w]) { // 若w未被访问
visited[w] = true; // 标记w已访问
parent[w] = v; // 记录v是w的父亲节点
Q.push(w); // 将w入队
}
}
}
}

3、Prim算法的代码如下：

typedef struct {
elementType adjvex; // 存储v到U的最短边的邻接点
int lowcost; // 存储v到U的最短边的权值
} closedge[MaxVerNum+1];

void Prim(Graph &G, int v, closedge ce[]) {
for (int i = 1; i <= G.VerNum; i++) { // 初始化closedge数组
if (i != v) {
ce[i].adjvex = v;
ce[i].lowcost = G.AdjMatrix[v][i];
}
}
ce[v].lowcost = -1; // 标记v已加入U中
for (int i = 1; i < G.VerNum; i++) { // 循环n-1次
int min = INF, w;
for (int j = 1; j <= G.VerNum; j++) { // 选取closedge中lowcost最小的边
if (ce[j].lowcost != -1 && ce[j].lowcost < min) {
min = ce[j].lowcost;
w = j;
}
}
ce[w].lowcost = -1; // 标记w已加入U中
for (int j = 1; j <= G.VerNum; j++) { // 更新closedge数组
if (ce[j].lowcost != -1 && G.AdjMatrix[w][j] < ce[j].lowcost) {
ce[j].adjvex = w;
ce[j].lowcost = G.AdjMatrix[w][j];
}
}
}
}

4、Kruskal算法的代码如下：

typedef struct {
int a; // 边的一个顶点
int b; // 边的另一个顶点
int w; // 边的权值
} Edge;

bool cmp(Edge e1, Edge e2) { // 边按权值从小到大排序的比较函数
return e1.w < e2.w;
}

int Find(int parent[], int v) { // 查找v所在的集合
while (parent[v] > 0) {
v = parent[v];
}
return v;
}

void Union(int parent[], int r1, int r2) { // 合并r1和r2所在的集合
int t = parent[r1] + parent[r2];
if (parent[r1] > parent[r2]) {
parent[r1] = r2;
parent[r2] = t;
} else {
parent[r2] = r1;
parent[r1] = t;
}
}

void Kruskal(Graph &G, Edge T[]) {
Edge E[MaxEdgeNum];
int parent[MaxVerNum+1];
int k = 0;
for (int i = 1; i <= G.VerNum; i++) { // 初始化parent数组
parent[i] = -1;
}
for (int i = 1; i <= G.VerNum; i++) { // 提取所有边
for (int j = i+1; j <= G.VerNum; j++) {
if (G.AdjMatrix[i][j] != INF) {
E[k].a = i;
E[k].b = j;
E[k].w = G.AdjMatrix[i][j];
k++;
}
}
}
sort(E, E+k, cmp); // 将边按权值从小到大排序
int cnt = 0; // 统计T中已选边数
for (int i = 0; i < k; i++) { // 遍历所有边
int r1 = Find(parent, E[i].a);
int r2 = Find(parent, E[i].b);
if (r1 != r2) { // 若两个顶点不在同一个集合中
T[cnt++] = E[i]; // 选取该边
Union(parent, r1, r2); // 合并两个集合
if (cnt == G.VerNum-1) { // 已选n-1条边，即可退出循环
break;
}
}
}
}