DS图—最小生成树（待验证）

题解

一.prim

1. prim算法的时间复杂度为O(n^2)&＃xff0c;与网中的边数无关&＃xff0c;适用于求边稠密的网的最小生成树。
2. prim算法中每次都要找一端在U中一端在V-U中的边中权值最小的边。这里U的实现可以通过设置一个visit数组&＃xff0c;如果在U里面就置为1&＃xff0c;而不是为U重新创建一个顶点集。找权值最小就可以先设置大初值变量minweight&＃xff0c;然后遍历所有符合条件的边&＃xff0c;如果权值比minweight小就赋给minweight。
3. prim循环结束的条件是U等于V&＃xff0c;对应到算法就是visit数组全为1。这里visit数组是否全为1不能作为判断条件直接写进while头&＃xff0c;所以可以为这段代码单独开一个isOver函数&＃xff0c;然后while头中用该函数就好了。
4. prim要求输出图最小生成树的边信息&＃xff0c;所以这里需要对边进行存储。边一共包含三个数据&＃xff0c;start顶点&＃xff0c;end顶点&＃xff0c;边的权值&＃xff0c;对其存储可以通过结构体数组、三个普通数组结合、三个队列或三个栈、邻接表或邻接矩阵&＃xff0c;前两者的缺点在于存入和输出时需要计数&＃xff0c;而用栈和队列就不需要计数&＃xff0c;这里采用结构体数组来存&＃xff08;注意startvex和endvex是代表对应顶点的下标&＃xff0c;而不是其内容&＃xff0c;因为下标操作起来更方便一些&＃xff09;。
5. 代码中Index函数的作用是根据传入数据的内容&＃xff0c;返回其在数组中对应的下标。对于数组而言&＃xff0c;知道下标很容易得到数组值&＃xff0c;而知道值要得到下标需要遍历整个数组&＃xff0c;并且常常用到这个操作&＃xff0c;所以干脆给数组定义一个Index函数。
6. 在网里面邻接矩阵的值不再是0和1&＃xff0c;而是将图中的1变为了权值&＃xff0c;而在prim中需要选择权值最小的边&＃xff0c;如果还是将没有边用0表示的话就会对其产生干扰&＃xff0c;所以这里初始化网用无穷。

二.kruskal

1. kruskal算法的时间复杂度为O(eloge)&＃xff0c;e为网中的边数&＃xff0c;适用于求解边稀疏的网的最小生成树。
2. kruskal算法中每次需要选择权值最小的边&＃xff0c;并且之前选择过的边不参加选择。其的实现可以通过用一个结构体数组来存无向网中的所有边&＃xff0c;并且以边权值的升序顺序存储&＃xff0c;这样每次就只要向后遍历该数组取边就可以了。实现权值升序可以先正常存&＃xff0c;然后针对其权值来个冒泡排序就可以了。
3. 每次选取了权值最小的边之后需要判断其的start顶点和end顶点是否位于同一连通分量。这里可以将位于同一连通分量的顶点视为一棵树&＃xff0c;它们有同一个根节点&＃xff0c;因此是否在同一连通分量就转化为顶点的根节点是否相同。根节点的实现可以设置一个parent数组&＃xff0c;初始每个顶点的parent都置为-1代表它们都是根节点&＃xff08;由于顶点下标0开始&＃xff0c;-1代表为根节点避免与0冲突&＃xff09;。这里需要对顶点进行找根操作&＃xff0c;可以定义一个FindRoot函数&＃xff08;不断迭代到parent为-1&＃xff09;。如果start和end顶点根节点不同&＃xff0c;就可以输出这条边了&＃xff08;这里最小生成树中的边不需要存储&＃xff0c;得到后直接输出就好了&＃xff09;&＃xff0c;然后让end顶点的parent值为start顶点下标就完成了统一根节点。
4. 这里结束函数的条件就在于是否找到并输出了vexnum-1条边。可以在对应的程序块中添加一个控制变量&＃xff0c;每次执行该段就&＃43;&＃43;&＃xff0c;当等于vexnum-1就return退出函数。

题目

问题 A: DS图—最小生成树
时间限制: 1 Sec 内存限制: 128 MB
提交: 1035 解决: 395
[提交][状态][讨论版]
题目描述
根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。&＃xff08;假设&＃xff1a;输入数据的最小生成树唯一。&＃xff09;输入
顶点数nn个顶点边数mm条边信息,格式为&＃xff1a;顶点1 顶点2 权值Prim算法的起点v输出
输出最小生成树的权值之和对两种算法&＃xff0c;按树的生长顺序&＃xff0c;输出边信息(Kruskal中边顶点按数组序号升序输出)样例输入
6
v1 v2 v3 v4 v5 v6
10
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
v1
样例输出
15
prim:
v1 v3 1
v3 v6 4
v6 v4 2
v3 v2 5
v2 v5 3
kruskal:
v1 v3 1
v4 v6 2
v2 v5 3
v3 v6 4
v2 v3 5


代码块

#include
using namespace std;class Edge
{int weight;int startvex, endvex;
public:Edge(){}~Edge(){}friend class Graph;
};class Graph
{
private:int vexnum;int edgenum;string *vertex;int **matrix;bool *visit;Edge *edge1;int *parent;Edge *edge2;int Index(string str);bool IsOver();int FindRoot(int vex);
public:Graph();~Graph();void MinSpanTree_Prim(string vex);void MinSpanTree_Kruskal();
};Graph::Graph()
{int i, j, weight;string startvex, endvex;//这里对顶点的表示用string而不是下标是因为输入或输出的形式所迫&＃xff0c;其他情况用下标&＃xff0c;这种形式想对它操作还要麻烦地用Index函数定位到下标。cin>>vexnum;vertex &＃61; new string[vexnum];matrix &＃61; new int*[vexnum];visit &＃61; new bool[vexnum];edge1 &＃61; new Edge[vexnum-1];parent &＃61; new int[vexnum];for(i&＃61;0; i<vexnum; i&＃43;&＃43;){cin>>vertex[i];matrix[i] &＃61; new int[vexnum];visit[i] &＃61; false;parent[i] &＃61; -1;for(j&＃61;0; j<vexnum; j&＃43;&＃43;)matrix[i][j] &＃61; 99999;//用无穷初始化邻接矩阵}cin>>edgenum;edge2 &＃61; new Edge[edgenum];for(i&＃61;0; i<edgenum; i&＃43;&＃43;){cin>>startvex>>endvex>>weight;edge2[i].endvex &＃61; Index(endvex);edge2[i].startvex &＃61; Index(startvex);edge2[i].weight &＃61; weight;matrix[Index(startvex)][Index(endvex)] &＃61; weight;matrix[Index(endvex)][Index(startvex)] &＃61; weight;//在无向图中注意要把对称的边也初始化。}Edge temp;for(i&＃61;0; i<edgenum-1; i&＃43;&＃43;){//针对结构体中weight进行冒泡排序for(j&＃61;0; j<edgenum-1-i; j&＃43;&＃43;){if(edge2[j].weight>edge2[j&＃43;1].weight){temp &＃61; edge2[j];edge2[j] &＃61; edge2[j&＃43;1];edge2[j&＃43;1] &＃61; temp;}}}
}Graph::~Graph()
{for(int i&＃61;0; i<vexnum; i&＃43;&＃43;)delete []matrix[i];delete []vertex;delete []matrix;delete []visit;delete []edge1;delete []parent;delete []edge2;
}int Graph::Index(string str)
{for(int i&＃61;0; i<vexnum; i&＃43;&＃43;){if(vertex[i]&＃61;&＃61;str)return i;}
}bool Graph::IsOver()
{for(int i&＃61;0; i<vexnum; i&＃43;&＃43;){if(!visit[i])return false;}return true;
}int Graph::FindRoot(int vex)
{while(parent[vex]!&＃61;-1){vex &＃61; parent[vex];}return vex;
}void Graph::MinSpanTree_Prim(string vex)
{int i, j, startvex, endvex;int weightsum &＃61; 0, pos &＃61; 0;visit[Index(vex)] &＃61; true;while(!IsOver()){int minweight &＃61; 99999;for(i&＃61;0; i<vexnum; i&＃43;&＃43;){//遍历所有符合条件的边&＃xff1a;先用for对所有边遍历&＃xff0c;然后for里面再用if筛选符合条件的情况。if(visit[i]){for(j&＃61;0; j<vexnum; j&＃43;&＃43;){if(!visit[j] && matrix[i][j]<minweight){minweight &＃61; matrix[i][j];startvex &＃61; i;endvex &＃61; j;}}}}visit[endvex] &＃61; true;weightsum &＃43;&＃61; minweight;edge1[pos].startvex &＃61; startvex;edge1[pos].endvex &＃61; endvex;edge1[pos].weight &＃61; minweight;pos&＃43;&＃43;;}cout<<weightsum<<endl;cout<<"prim:"<<endl;for(i&＃61;0; i<vexnum-1; i&＃43;&＃43;)cout<<vertex[edge1[i].startvex]<<&＃39; &＃39;<<vertex[edge1[i].endvex]<<&＃39; &＃39;<<edge1[i].weight<<endl;//注意这里的startvex和endvex只是下标&＃xff0c;输出要套上顶点数组。
}void Graph::MinSpanTree_Kruskal()
{int i, vex1, vex2;int num &＃61; 0;cout<<"kruskal:"<<endl;for(i&＃61;0; i<edgenum; i&＃43;&＃43;){vex1 &＃61; FindRoot(edge2[i].startvex);vex2 &＃61; FindRoot(edge2[i].endvex);if(vex1!&＃61;vex2){cout<<vertex[edge2[i].startvex]<<&＃39; &＃39;<<vertex[edge2[i].endvex]<<&＃39; &＃39;<<edge2[i].weight<<endl;parent[vex2] &＃61; vex1;num&＃43;&＃43;;if(num&＃61;&＃61;vexnum-1)return;}}
}int main(void)
{Graph myGraph;string vex;cin>>vex;myGraph.MinSpanTree_Prim(vex);myGraph.MinSpanTree_Kruskal();return 0;
}