【算法和数据结构】1.10--图的最小生成树之Kruskal算法(C++实现)

3/8/2017来源:ASP.NET技巧人气:842

      在前面两节图和图的最小生成树之PRim算法的基础上,这里给出另外一种求解MST(最小生成树)的算法—–Kruskal算法

       Kruskal算法可以概括为:

取出连通无向图G的所有边。 从第一步形成的边集合中选取权值最小的边,加入最小生成树边集合T中。 求出第二步中选出边的两端顶点,判断他们所在顶点集的关系以确认是否存在回路。若不存在回路,则确认将此最小边加入T中,若存在回路,则丢弃。

       同Prim算法,我们用下面这一连通无向图作为示例: 这里写图片描述

       下面给出实现代码以及测试代码:(在图以及Prim算法的基础上增加而来,若读者觉得阅读有困难,可参看前两节文章)

#include<iostream> #include<cstdlib> #include<vector> using namespace std; /*节点类*/ class Node { public: Node(char identifier = 0); char m_identifier; //顶点编号 bool m_isVisited; //顶点访问标志位:true表示已经被访问 }; Node::Node(char identifier) { m_identifier = identifier; m_isVisited = false; } /*边类,用于辅助实现生成最小生成树*/ class Edge { public: Edge(int NodeIndexA = 0, int NodeIndexB = 0, int WeightValue = 0); int m_NodeIndexA, m_NodeIndexB; //边的两端点(索引),这里以无向图为例 int m_weightValue; //边的权值 bool m_selected; //选择标志位,true表示已被选择 }; Edge::Edge(int NodeIndexA, int NodeIndexB, int WeightValue) { m_NodeIndexA = NodeIndexA; m_NodeIndexB = NodeIndexB; m_weightValue = WeightValue; m_selected = false; //初始时未被选择 } /*图类*/ class Graph { public: Graph(int capacity); ~Graph(); int getGraphSize(); //获取当前图的大小 void resetNode(); //重置所有顶点的访问标志位为false,未访问 bool addNode(Node *pNode); //添加新顶点 bool addEdgeForUndirectedGraph(int row, int col, int val = 1); //添加边以构造无向图,val表示权值,默认权值1 bool addEdgeForDirectedGraph(int row, int col, int val = 1); //添加边以构造有向图,val表示权值,默认权值1 void printMatrix(); //打印邻接矩阵 void depthFirstTraverse(int nodeIndex); //深度优先遍历,指定第一个点 void widthFirstTraverse(int nodeIndex); //广度优先遍历,指定第一个点 void MSTPrim(int nodeIndex); //Prim算法求最小生成树,指定第一个点 void MSTKruskal(); //Kruskal算法求最小生成树,指定第一个点 private: bool getValueOfEdge(int row, int col, int &val); //获取边权值 void widthFirstTraverseImplement(vector<int> preVec); //利用vector实现广度优先遍历 int getMinEdge(vector<Edge> edgeVec); //最小生成树算法辅助函数,用于在边集中选择权值最小的边 bool isInSet(vector<int> nodeSet, int target); //Kruskal辅助函数,用于判断指定顶点是否在给定点集中 void mergeNodeSets(vector<int> &nodeSetA, vector<int> nodeSetB); //Kruscal辅助函数,用于合并两个点集 int m_iCapacity; //图容量,即申请的数组空间最多可容纳的顶点个数 int m_iNodeCount; //图的现有顶点个数 Node *m_pNodeArray; //存放顶点的数组 int *m_pMatrix; //为了方便,用一维数组存放邻接矩阵 Edge *m_pEgde; //边指针,存储最小生成树的边 }; Graph::Graph(int capacity) { m_iCapacity = capacity; m_iNodeCount = 0; m_pNodeArray = new Node[m_iCapacity]; m_pMatrix = new int[m_iCapacity*m_iCapacity]; for (int i = 0;i < m_iCapacity*m_iCapacity;i++) //初始化邻接矩阵 { m_pMatrix[i] = 0; } m_pEgde = new Edge[m_iCapacity - 1]; //最小生成树节点和边数量关系 } Graph::~Graph() { delete []m_pNodeArray; delete []m_pMatrix; delete []m_pEgde; } int Graph::getGraphSize() { return m_iNodeCount; } void Graph::resetNode() { for (int i = 0;i < m_iNodeCount;i++) { m_pNodeArray[i].m_isVisited = false; } } bool Graph::addNode(Node *pNode) { if (pNode == NULL) return false; m_pNodeArray[m_iNodeCount].m_identifier = pNode->m_identifier; m_iNodeCount++; return true; } bool Graph::addEdgeForUndirectedGraph(int row, int col, int val) { if (row < 0 || row >= m_iCapacity) return false; if (col < 0 || col >= m_iCapacity) return false; m_pMatrix[row*m_iCapacity + col] = val; m_pMatrix[col*m_iCapacity + row] = val; return true; } bool Graph::addEdgeForDirectedGraph(int row, int col, int val) { if (row < 0 || row >= m_iCapacity) return false; if (col < 0 || col >= m_iCapacity) return false; m_pMatrix[row*m_iCapacity + col] = val; return true; } void Graph::printMatrix() { for (int i = 0;i < m_iCapacity;i++) { for (int k = 0;k < m_iCapacity;k++) cout << m_pMatrix[i*m_iCapacity + k] << " "; cout << endl; } } void Graph::depthFirstTraverse(int nodeIndex) { int value = 0; //访问第一个顶点 cout << m_pNodeArray[nodeIndex].m_identifier << " "; m_pNodeArray[nodeIndex].m_isVisited = true; //访问其他顶点 for (int i = 0;i < m_iCapacity;i++) { getValueOfEdge(nodeIndex, i, value); if (value != 0) //当前顶点与指定顶点连通 { if (m_pNodeArray[i].m_isVisited == true) //当前顶点已被访问 continue; else //当前顶点没有被访问,则递归 { depthFirstTraverse(i); } } else //没有与指定顶点连通 { continue; } } } void Graph::widthFirstTraverse(int nodeIndex) { //访问第一个顶点 cout << m_pNodeArray[nodeIndex].m_identifier << " "; m_pNodeArray[nodeIndex].m_isVisited = true; vector<int> curVec; curVec.push_back(nodeIndex); //将第一个顶点存入一个数组 widthFirstTraverseImplement(curVec); } void Graph::widthFirstTraverseImplement(vector<int> preVec) { int value = 0; vector<int> curVec; //定义数组保存当前层的顶点 for (int j = 0;j < (int)preVec.size();j++) //依次访问传入数组中的每个顶点 { for (int i = 0;i < m_iCapacity;i++) //传入的数组中的顶点是否与其他顶点连接 { getValueOfEdge(preVec[j], i, value); if (value != 0) //连通 { if (m_pNodeArray[i].m_isVisited==true) //已经被访问 { continue; } else //没有被访问则访问 { cout << m_pNodeArray[i].m_identifier << " "; m_pNodeArray[i].m_isVisited = true; //保存当前点到数组 curVec.push_back(i); } } } } if (curVec.size()==0) //本层次无被访问的点,则终止 { return; } else { widthFirstTraverseImplement(curVec); } } bool Graph::getValueOfEdge(int row, int col, int &val) { if (row < 0 || row >= m_iCapacity) return false; if (col < 0 || col >= m_iCapacity) return false; val = m_pMatrix[row*m_iCapacity + col]; return true; } void Graph::MSTPrim(int nodeIndex) { int value = 0; //存储当前边的权值 int edgeCount = 0; //已选出的边数量,用以判断算法终结 vector<int> nodeVec; //存储点(索引)集的数组 vector<Edge> edgeVec; //存储边的数组 cout << m_pNodeArray[nodeIndex].m_identifier << endl; nodeVec.push_back(nodeIndex); m_pNodeArray[nodeIndex].m_isVisited = true; while (edgeCount < m_iCapacity - 1) { int temp = nodeVec.back(); //将当前顶点索引复制给temp for (int i = 0;i < m_iCapacity;i++) //循环判断每一个顶点与当前顶点连接情况 { getValueOfEdge(temp, i, value); if (value != 0) //连通 { if (m_pNodeArray[i].m_isVisited == true) //已经被访问 continue; else //未被访问,则将边放入被选边集合 { Edge edge(temp, i, value); edgeVec.push_back(edge); } } } /*选择最小边*/ int edgeIndex = getMinEdge(edgeVec); if (edgeIndex == -1) { cout << "获取最小边失败,请重置后再试!" << endl; break; } edgeVec[edgeIndex].m_selected = true; //设置选择标志位为true,已被选择 cout << edgeVec[edgeIndex].m_NodeIndexA << "---" << edgeVec[edgeIndex].m_NodeIndexB<<" "; cout << edgeVec[edgeIndex].m_weightValue << endl; m_pEgde[edgeCount] = edgeVec[edgeIndex]; edgeCount++; /*寻找当前选择的最小边相连的下一个顶点*/ int nextNodeIndex = edgeVec[edgeIndex].m_NodeIndexB; nodeVec.push_back(nextNodeIndex); m_pNodeArray[nextNodeIndex].m_isVisited = true; cout << m_pNodeArray[nextNodeIndex].m_identifier << endl; } cout << "最小生成树计算完毕,如上所示!"; } void Graph::MSTKruskal() { int value = 0; //存储当前边的权值 int edgeCount = 0; //已选出的边数量 /*存放节点集合的数组,不同于Prim,Kruskal算法过程中可能出现多个点集*/ vector<vector<int>> nodeSets; /*取出所有边*/ vector<Edge> edgeVec; for (int i = 0;i < m_iCapacity;i++) //去邻接矩阵的右上角的三角部分,不含对角线。无向图邻接矩阵对称 { for (int k = i + 1;k < m_iCapacity;k++) { getValueOfEdge(i, k, value); if (value != 0) { Edge edge(i, k, value); edgeVec.push_back(edge); } } } /*循环寻找最小生成树的边*/ while (edgeCount < m_iCapacity - 1) { int minEdgeIndex = getMinEdge(edgeVec); edgeVec[minEdgeIndex].m_selected = true; //选出最小边,并标记为已选 int nodeAIndex = edgeVec[minEdgeIndex].m_NodeIndexA; int nodeBIndex = edgeVec[minEdgeIndex].m_NodeIndexB; //找出最小边两端顶点 bool nodeAIsInSet = false; //标记某个顶点是否在指定点集中 bool nodeBIsInSet = false; int nodeAInSetLabel = -1; //某个顶点所在点集的索引 int nodeBInSetLabel = -1; for (int i = 0;i < (int)nodeSets.size();i++) //寻找A顶点所在点集 { nodeAIsInSet = isInSet(nodeSets[i], nodeAIndex); if (nodeAIsInSet) { nodeAInSetLabel = i; //保存当前点集索引 } } for (int i = 0;i < (int)nodeSets.size();i++) //寻找B顶点所在点集 { nodeBIsInSet = isInSet(nodeSets[i], nodeBIndex); if (nodeBIsInSet) { nodeBInSetLabel = i; //保存当前点集索引 } } /*根据结果做相应处理*/ if (nodeAInSetLabel == -1 && nodeBInSetLabel == -1) //两顶点均不在已有点集中 { //建立新的点集 vector<int> vec; vec.push_back(nodeAIndex); vec.push_back(nodeBIndex); nodeSets.push_back(vec); } else if (nodeAInSetLabel == -1 && nodeBInSetLabel != -1) //某顶点在已有点集中 { //将另外一个节点加入已有点集 nodeSets[nodeBInSetLabel].push_back(nodeAIndex); } else if (nodeAInSetLabel != -1 && nodeBInSetLabel == -1) { nodeSets[nodeAInSetLabel].push_back(nodeBIndex); } else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel != nodeBInSetLabel) //两个顶点在不同的点集中 { //合并两个集合,到前一参数点集,并将顶点从第二个参数点集删除 mergeNodeSets(nodeSets[nodeAInSetLabel], nodeSets[nodeBInSetLabel]); for (int k = nodeBInSetLabel;k < (int)nodeSets.size()-1;k++) { nodeSets[k] = nodeSets[k + 1]; } } else if (nodeAInSetLabel != -1 && nodeBInSetLabel != -1 && nodeAInSetLabel == nodeBInSetLabel) //两个顶点在同一点集 { //存在回路,放弃当前边 continue; } m_pEgde[edgeCount] = edgeVec[minEdgeIndex]; edgeCount++; cout << edgeVec[minEdgeIndex].m_NodeIndexA << "---" << edgeVec[minEdgeIndex].m_NodeIndexB << " "; cout << edgeVec[minEdgeIndex].m_weightValue << endl; } } int Graph::getMinEdge(vector<Edge> edgeVec) { int minWeight = 0; //用于辅助选择最小权值边 int edgeIndex = 0; //用于存储最小边索引 int i = 0; /*找出第一条未被选择的边*/ for (;i < (int)edgeVec.size();i++) { if (edgeVec[i].m_selected == false) //当前边未被选择 { minWeight = edgeVec[i].m_weightValue; edgeIndex = i; break; } } if (minWeight == 0) //边集所有边被访问 { return -1; } for (;i < (int)edgeVec.size();i++) { if (edgeVec[i].m_selected == true) continue; else { if (minWeight > edgeVec[i].m_weightValue) { minWeight = edgeVec[i].m_weightValue; edgeIndex = i; } } } return edgeIndex; } bool Graph::isInSet(vector<int> nodeSet, int target) { for (int i = 0;i < (int)nodeSet.size();i++) { if (nodeSet[i] == target) return true; } return false; } void Graph::mergeNodeSets(vector<int> &nodeSetA, vector<int> nodeSetB) { for (int i = 0;i < (int)nodeSetB.size();i++) { nodeSetA.push_back(nodeSetB[i]); } } int main() { Graph *pGraph = new Graph(6); cout << "初始化顶点中……" << endl; Node *pNodeA = new Node('A'); Node *pNodeB = new Node('B'); Node *pNodeC = new Node('C'); Node *pNodeD = new Node('D'); Node *pNodeE = new Node('E'); Node *pNodeF = new Node('F'); cout << "添加顶点至图中……" << endl; pGraph->addNode(pNodeA); pGraph->addNode(pNodeB); pGraph->addNode(pNodeC); pGraph->addNode(pNodeD); pGraph->addNode(pNodeE); pGraph->addNode(pNodeF); pGraph->addEdgeForUndirectedGraph(0, 1, 6); pGraph->addEdgeForUndirectedGraph(0, 4, 5); pGraph->addEdgeForUndirectedGraph(0, 5, 1); pGraph->addEdgeForUndirectedGraph(1, 5, 2); pGraph->addEdgeForUndirectedGraph(1, 2, 3); pGraph->addEdgeForUndirectedGraph(2, 5, 8); pGraph->addEdgeForUndirectedGraph(2, 3, 7); pGraph->addEdgeForUndirectedGraph(3, 5, 4); pGraph->addEdgeForUndirectedGraph(3, 4, 2); pGraph->addEdgeForUndirectedGraph(4, 5, 9); cout << "邻接矩阵如下:" << endl; pGraph->printMatrix(); cout << endl << endl; cout << "深度优先遍历:" << endl; pGraph->depthFirstTraverse(0); cout << endl << endl; pGraph->resetNode(); cout << "广度优先遍历:" << endl; pGraph->widthFirstTraverse(0); cout << endl << endl; pGraph->resetNode(); cout << "最小生成树为:" << endl; pGraph->MSTKruskal(); cout << endl; system("pause"); }

       测试结果如下: 这里写图片描述

       在文章开始对Kruskal算法的描述中,涉及到循环的每一次都要寻找最小边的问题。我们可以换一种思路,作如下描述:

对G的边以飞降序权重排序。 对于排序表中的每条边,如果现在把它加入T不会形成回路,则将其加入T集合中,否则丢弃。

      有兴趣的读者可以自己用这一种算法描述来改进Krukal算法,这样就不需要每进行一次循环就需要调用getMinEdge()函数,可以减少算法时间开销。这样一来,若G含有m条边,则其算法时间复杂度为O(m * log m)。