卡利姆多护火者,8l9980,成人动漫画
关于图的几个概念定义:
下面介绍两种求最小生成树算法
此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
此算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。
由于不断向集合u中加点,所以最小代价边必须同步更新;需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中最小代价边信息,:
struct { char vertexdata //表示u中顶点信息 uint lowestcost //最小代价 }closedge[vexcounts]
/************************************************************************ csdn 勿在浮沙筑高台 http://blog.csdn.net/luoshixian099算法导论--最小生成树(prim、kruskal)2016年7月14日 ************************************************************************/ #include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; #define infinite 0xffffffff #define vertexdata unsigned int //顶点数据 #define uint unsigned int #define vexcounts 6 //顶点数量 char vextex[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; struct node { vertexdata data; unsigned int lowestcost; }closedge[vexcounts]; //prim算法中的辅助信息 typedef struct { vertexdata u; vertexdata v; unsigned int cost; //边的代价 }arc; //原始图的边信息 void adjmatrix(unsigned int adjmat[][vexcounts]) //邻接矩阵表示法 { for (int i = 0; i < vexcounts; i++) //初始化邻接矩阵 for (int j = 0; j < vexcounts; j++) { adjmat[i][j] = infinite; } adjmat[0][1] = 6; adjmat[0][2] = 1; adjmat[0][3] = 5; adjmat[1][0] = 6; adjmat[1][2] = 5; adjmat[1][4] = 3; adjmat[2][0] = 1; adjmat[2][1] = 5; adjmat[2][3] = 5; adjmat[2][4] = 6; adjmat[2][5] = 4; adjmat[3][0] = 5; adjmat[3][2] = 5; adjmat[3][5] = 2; adjmat[4][1] = 3; adjmat[4][2] = 6; adjmat[4][5] = 6; adjmat[5][2] = 4; adjmat[5][3] = 2; adjmat[5][4] = 6; } int minmum(struct node * closedge) //返回最小代价边 { unsigned int min = infinite; int index = -1; for (int i = 0; i < vexcounts;i++) { if (closedge[i].lowestcost < min && closedge[i].lowestcost !=0) { min = closedge[i].lowestcost; index = i; } } return index; } void minispantree_prim(unsigned int adjmat[][vexcounts], vertexdata s) { for (int i = 0; i < vexcounts;i++) { closedge[i].lowestcost = infinite; } closedge[s].data = s; //从顶点s开始 closedge[s].lowestcost = 0; for (int i = 0; i < vexcounts;i++) //初始化辅助数组 { if (i != s) { closedge[i].data = s; closedge[i].lowestcost = adjmat[s][i]; } } for (int e = 1; e <= vexcounts -1; e++) //n-1条边时退出 { int k = minmum(closedge); //选择最小代价边 cout << vextex[closedge[k].data] << "--" << vextex[k] << endl;//加入到最小生成树 closedge[k].lowestcost = 0; //代价置为0 for (int i = 0; i < vexcounts;i++) //更新v中顶点最小代价边信息 { if ( adjmat[k][i] < closedge[i].lowestcost) { closedge[i].data = k; closedge[i].lowestcost = adjmat[k][i]; } } } } void readarc(unsigned int adjmat[][vexcounts],vector<arc> &vertexarc) //保存图的边代价信息 { arc * temp = null; for (unsigned int i = 0; i < vexcounts;i++) { for (unsigned int j = 0; j < i; j++) { if (adjmat[i][j]!=infinite) { temp = new arc; temp->u = i; temp->v = j; temp->cost = adjmat[i][j]; vertexarc.push_back(*temp); } } } } bool compare(arc a, arc b) { return a.cost < b.cost ? true : false; } bool findtree(vertexdata u, vertexdata v,vector<vector<vertexdata> > &tree) { unsigned int index_u = infinite; unsigned int index_v = infinite; for (unsigned int i = 0; i < tree.size();i++) //检查u,v分别属于哪颗树 { if (find(tree[i].begin(), tree[i].end(), u) != tree[i].end()) index_u = i; if (find(tree[i].begin(), tree[i].end(), v) != tree[i].end()) index_v = i; } if (index_u != index_v) //u,v不在一颗树上,合并两颗树 { for (unsigned int i = 0; i < tree[index_v].size();i++) { tree[index_u].push_back(tree[index_v][i]); } tree[index_v].clear(); return true; } return false; } void minispantree_kruskal(unsigned int adjmat[][vexcounts]) { vector<arc> vertexarc; readarc(adjmat, vertexarc);//读取边信息 sort(vertexarc.begin(), vertexarc.end(), compare);//边按从小到大排序 vector<vector<vertexdata> > tree(vexcounts); //6棵独立树 for (unsigned int i = 0; i < vexcounts; i++) { tree[i].push_back(i); //初始化6棵独立树的信息 } for (unsigned int i = 0; i < vertexarc.size(); i++)//依次从小到大取最小代价边 { vertexdata u = vertexarc[i].u; vertexdata v = vertexarc[i].v; if (findtree(u, v, tree))//检查此边的两个顶点是否在一颗树内 { cout << vextex[u] << "---" << vextex[v] << endl;//把此边加入到最小生成树中 } } } int main() { unsigned int adjmat[vexcounts][vexcounts] = { 0 }; adjmatrix(adjmat); //邻接矩阵 cout << "prim :" << endl; minispantree_prim(adjmat,0); //prim算法,从顶点0开始. cout << "-------------" << endl << "kruskal:" << endl; minispantree_kruskal(adjmat);//kruskal算法 return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论