数据结构_图的应用

最小生成树

Prim算法

int AMGraph::sum(string v)
{int start, totalW, cnt, minW, u, vv, i, j;start = LocateVex(v); // 获取起始顶点编号memset(visited, false, sizeof(visited)); // 初始化访问状态visited[start] = true;totalW = 0; // 最小生成树的总权重cnt = 1; // 当前生成树包含的顶点数while (cnt < vexnum){minW = INT_MAX; // 当前最小边权值u = -1; // 最小边的两个端点vv = -1;for (i = 0; i < vexnum; i++){// 遍历已加入生成树的顶点if (visited[i]){for (j = 0; j < vexnum; j++){if (!visited[j] && arcs[i][j] < minW){minW = arcs[i][j];u = i; // 起始点vv = j; // 终点}}}}// 无法继续扩展生成树if (vv == -1){break;}visited[vv] = true; // 将v加入生成树totalW += minW; // 累加权值cnt++; // 增加生成树的顶点计数}return totalW;
}

Kruskal算法

void AMGraph::kruskal()
{int i, j;for (i = 0; i < arcnum; i++) // 将所有的边按照从小到大排序{for (j = i + 1; j < arcnum; j++){if ((edges[i].w > edges[j].w) || (edges[i].w == edges[j].w && edges[i].u > edges[j].u)){Edge temp = edges[i];edges[i] = edges[j];edges[j] = temp;}}}for (i = 0; i < vexnum; i++) // 初始化{Vexset[i] = i;}for (i = 0; i < arcnum; i++) // 遍历所有的边{int v1 = edges[i].u; // 边的始点的下标int v2 = edges[i].v; // 边的终点的下标int vs1 = Vexset[v1]; // 连通分量int vs2 = Vexset[v2];// 如果两个节点不在同一棵树中，说明这条边可以添加到最小生成树中if (vs1 != vs2){if (edges[i].u < edges[i].v){cout << vexs[edges[i].u] << " " << vexs[edges[i].v] << " " << edges[i].w << endl;}else{cout << vexs[edges[i].v] << " " << vexs[edges[i].u] << " " << edges[i].w << endl;}// 合并两个分量for (j = 0; j < arcnum; j++){if (Vexset[j] == vs2){Vexset[j] = vs1;}}}}
}

两种算法比较