做php网站教程视频教程,返回链接 网站惩罚检查 错误检查,什么网站做美食最好最专业,企业网站的特点是什么总结一下#xff1a;
如果选 0为起点#xff0c;low_cost[i]表示以 0这个起点到i 这个终点的权值#xff0c;我们找最小的权值的终点i#xff0c;然后以i为起点#xff0c;去更新low_cost[]这个数组#xff0c;如果与i相连的数是j#xff0c;现在有两种情况#xff0c…总结一下
如果选 0为起点low_cost[i]表示以 0这个起点到i 这个终点的权值我们找最小的权值的终点i然后以i为起点去更新low_cost[]这个数组如果与i相连的数是j现在有两种情况j与0相连j与i相连但不与0相连。如果j也与0相连我们找0到j和i到j这两者的最小距离然后用这个最小的距离更新low_cost[j]。如果j不与0相连那么就直接填上low_cost[j]
代码分析一下
matrix[i][j]m意思是以i为起点j为终点的权值为m path[i]a,意思是i起点连的是a终点 由此我们可见数组可以表达的意思可以是那几个变量之间的相关性
visit数组存的是目前最小生成树上已经有的结点我们最小生成树最终是要有所有的结点的
先找一个起点然后把与起点相连的路径都存到low_cost里
找一个终点起点到他的权值最小将这个终点进行标记证明已经将其加入到最小生成树里面了并且记录最小路径和的sum要加上他的权值
由于low_cost目前只存了与起点相连的路径现在最小生成树里面加入了一个新的结点那么我们就需要更新low_cost数组把与这个新的结点相连的路径加入到low_cost数组里路径就要考虑终点这个终点一定不是在最小生成树里的所以要用到visit数组然后如果matrix[min_cost_index][j]就是这个新节点到某一终点的权值比low_cost[j]小的话就更新low_cost[j]
#include iostreamusing namespace std;int matrix[100][100]; // 邻接矩阵
bool visited[100]; // 标记数组
int low_cost[100]; // 边的权值
int path[100]; // 记录生成树的路径
int source; // 指定生成树的起点
int vertex_num; // 顶点数
int edge_num; // 边数
int sum; // 生成树权和void Prim(int source)
{memset(visited, 0, sizeof(visited));visited[source] true;for (int i 0; i vertex_num; i){low_cost[i] matrix[source][i];path[i] source;}int min_cost; // 权值最小int min_cost_index; // 权值最小的下标sum 0;for (int i 1; i vertex_num; i) // 除去起点还需要找到另外 vertex_num-1 个点{min_cost INT_MAX;for (int j 0; j vertex_num; j){if (visited[j] false low_cost[j] min_cost) // 找到权值最小{min_cost low_cost[j];min_cost_index j;}}visited[min_cost_index] true; // 该点已找到进行标记sum low_cost[min_cost_index]; // 更新生成树权和for (int j 0; j vertex_num; j) // 从找到的最小下标更新 low_cost 数组{if (visited[j] false matrix[min_cost_index][j] low_cost[j]){low_cost[j] matrix[min_cost_index][j];path[j] min_cost_index;}}}
}int main()
{cout 请输入图的顶点数100;cin vertex_num;cout 请输入图的边数;cin edge_num;for (int i 0; i vertex_num; i)for (int j 0; j vertex_num; j)matrix[i][j] INT_MAX; // 初始化 matrix 数组cout 请输入边的信息\n;int u, v, w;for (int i 0; i edge_num; i){cin u v w;matrix[u][v] matrix[v][u] w;}cout 请输入起点 vertex_num ;cin source;Prim(source);cout 最小生成树权和为 sum endl;cout 最小生成树路径为\n;for (int i 0; i vertex_num; i)if (i ! source)cout i ---- path[i] endl;return 0;
}
/*
请输入图的顶点数1005
请输入图的边数7
请输入边的信息
0 1 8
0 2 3
0 3 2
1 3 3
3 2 4
2 4 1
3 4 5
请输入起点50
最小生成树权和为9
最小生成树路径为
1----3
2----0
3----0
4----2
*/
不过上面这个适合理解不适合去作为模板 因为往往下标从一开始 这有一个模板
#include iostream
#include cstdio
#include cstring
using namespace std;
#define N 150
#define INF 99999999
int ma[N][N];
long long d[N],vis[N];
int n;
long long prim(int s)
{memset(vis,0,sizeof(vis));for(int i1; in; i)d[i]is?0:ma[s][i];vis[s]1;long long ans0;for(int i1; in; i){int maxnINF,v;for(int j1; jn; j)if(!vis[j]maxnd[j]){maxnd[j];vj;}vis[v]1;ansmaxn;for(int j1; jn; j)if(!vis[j]ma[v][j]d[j])d[j]ma[v][j];}return ans;
}main那里面
先输入数组ma
然后
long long ansprim(1);printf(%lld\n,ans);
