网站建设沙漠风,在线可以做翻译的网站,建设网站的和服务器,顺德装修网站建设5 最小生成树 构造连通网的最小代价生成树称为最小生成树#xff0c;即Minimum Cost Spanning Tree#xff0c;最小生成树通常是基于无向网/有向网构造的。 找连通网的最小生成树#xff0c;经典的有两种算法#xff0c;普里姆算法和克鲁斯卡尔算法。
5.1 普里姆#xff…5 最小生成树 构造连通网的最小代价生成树称为最小生成树即Minimum Cost Spanning Tree最小生成树通常是基于无向网/有向网构造的。 找连通网的最小生成树经典的有两种算法普里姆算法和克鲁斯卡尔算法。
5.1 普里姆Prim算法 普里姆算法即Prim算法大致实现过程如下 (1) 新建数组adjVex[n]初始值均为0新建数组lowCost[n]初始值均为infinity (2) 从第一个顶点X下标为0开始把它与各顶点连接的权记录下来放到lowCost数组里面然后找到权最小的那个顶点Y得到最小生成树的第一条边(X,Y)然后把lowCost数组里面Y对应的下标的元素设置为0 (3) 然后处理顶点Y把它与除X外的其他各顶点连接的权与lowCost数组下标相同的权比较将小的放入到lowCost里面并把较小的权对应的顶点的下标记录在adjVex数组里面也即adjVex[j]要么是Y要么是除X外的其他顶点 (4) 找到lowCost数组中权最小的那个显然不会是X也不会是Y得到最小生成树的第二条边(adjVex[j],j)然后把lowCost[j]设置为0 (5) 然后按(3)、(4)的规则处理第j个顶点直到所有顶点都被连接起来注意最小连通树是针对连通网的 下面我们会根据各种存储方式进行举例。
5.1.1 邻接矩阵的最小生成树 假设有以下无向网 我们定义两个数组一个X{}Y{V0、v1、v2、v3、v4、v5、v6、v7、v8}其中X表示已连通的顶点Y表示未连通的顶点。 先从第一个顶点v0开始把它加入X表示已连通这时X{v0}Y{v1、v2、v3、v4、v5、v6、v7、v8}。 接下来看X中的V0与其他顶点关联时权值情况发现(v0,v1)的权值最小因此认为v0和v1是最小生成树的一个边此时X{v0、v1}Y{v2、v3、v4、v5、v6、v7、v8} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V0,v5)之间的权值最小因此认为(V0,v5)是最小生成树的一条边此时X{v0、v1、v5}Y{v2、v3、v4、v6、v7、v8} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V1,v8)之间的权值最小因此认为(V1,v8)是最小生成树的一条边此时X{v0、v1、v5、v8}Y{v2、v3、v4、v6、v7} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V8,v2)之间的权值最小因此认为(V8,v2)是最小生成树的一条边此时X{v0、v1、v5、v8、v2}Y{v3、v4、v6、v7} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V1,v6)之间的权值最小因此认为(V1,v6)是最小生成树的一条边此时X{v0、v1、v5、v8、v2、v6}Y{v3、v4、v7} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V6,v7)之间的权值最小因此认为(V6,v7)是最小生成树的一条边此时X{v0、v1、v5、v8、v2、v6、v7}Y{v3、v4} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V7,v4)之间的权值最小因此认为(V7,v4)是最小生成树的一条边此时X{v0、v1、v5、v8、v2、v6、v7、v4}Y{v3} 然后再看X中的所有顶点与Y中的所有顶点的权值发现边现(V7,v3)之间的权值最小因此认为(V7,v3)是最小生成树的一条边此时X{v0、v1、v5、v8、v2、v6、v7、v4、v3}Y{} 这时Y已处理完毕所有顶点都连起来了形成了最小生成树。 观察一下我们在获取最小生成树的边时第一步是从arc[0][j]取权最小的取到了(v0,v1)第二步是从arc[0][j]和arc[1][j]中取权值最小的取到了(v0,v5)第三步是从arc[0][j]、arc[1][j]和arc[5][j]中取权最小的取到了(v1,v8)也即规则是 (1) 从arc[0][j]中取最小权对应的边(v0,v1)此时X{v0}把v1加入到X中 (2) 从arc[0][j]、arc[1][j]中取最小权对应的边(v0,v5)此时X{v0,v1}把v5加入到X中 (3) 从arc[0][j]、arc[1][j]、arc[5][j]中取最小权对应的边(v1,v8)此时X{v0,v1,v5}把v8加入到X中 (4) 从arc[0][j]、arc[1][j]、arc[5][j]…arc[x][j]中取最小权对应的边(vi,vk)然后判断vi和vk是否在X中不在则加入到X中 当在arc[0][j]、arc[1][j]、arc[5][j]…arc[x][j]中取最小的权时我们要比较x个一元数组的值我们再做一下优化 (1) 从arc[0][j]中取最小权对应的边(v0,v1)此时X{v0}把v1加入到X中 (2) 从arc[0][j]、arc[1][j]中取最小权对应的边(v0,v5)此时X{v0,v1}把v5加入到X中然后我们把arc[0][j]、arc[1][j]组合一下取出arc[0][j]、arc[1][j]中较小的权放到lowCost[j]里面同时使用一个数组adjVex[j]记录lowCost[j]对应的起始顶点下标同时标注lowCost[0]、lowCost[1]的值为负无穷大如下 (3) 这时只需要从lowCost[j]、arc[5][j]中取最小权对应的边就行了不用再迭代arc[0][j]和arc[1][j] 因此我们定义两个数组lowCost[n]表示已处理过的顶点跟其他顶点之间的权值最小值列表其中已处理过的顶点之间的权值设置为负无穷大adjVex[n]表示最小权值对应的起始顶点我们重新来看看上述无向网。 第一步定义lowCost[n]和adjVex[n]adjVex[n]默认值为0lowCost[n]默认值为负无穷大 接下来处理第一个顶点找到第一个顶点与其他顶点中权值最小的那条边自身除外具体做法是令adjVex[n]的元素均为0令lowCost[n]的元素值为arc[0][j]然后找到权值最小的arc[0][x]取边(adjVex[x],x)即(v0,v1) 接下来要比较的应是arc[0][j]和arc[1][j]中除arc[0][0]、arc[0][1]、arc[1][0]和arc[1][1]外的其他值取最小值因为我们要取的是“其他顶点与顶点v0、v1中权值最小的边”因此我们把arc[1][j]与lowCost[n]这时lowCost即为arc[0][j]比较把较小的写入到lowCost中同时把较小权对应对应的顶点下标写入到adjVex[n]中如下 如上可知arc[1][2]小于lowCost[2]因此令lowCost[2]arc[1][2]、adjVex[2]1arc[1][6]和arc[1][8]也相似处理。 然后我们取出其中的最小权得到下一条最小生成树的边即(v0,v5) 接下来是取得顶点v0、v1、v5与其他顶点的权中的最小值生成下一条边整体处理方式与上文类似 后续操作也类似直到所有顶点处理完毕得到最小生成树。 让我们来看有向网的处理按上述过程处理得到以下结果 即 但注意观察同样是连通B顶点弧B,A实际上比C,B权小所以最小生成树应该为 因此有向树的最小生成树生成过程中不仅要看“顶点X指向的顶点中权最小的”还要看“顶点X被指向的顶点中权最小的”。 因此寻找最低代码的边/弧的逻辑应是“找到该顶点指向的即该顶点被指向的顶点中代价最小的边或弧”对于无向网当然这两个概念是一样的但对于有向网则要进行双向处理因此上述有向网的处理逻辑有所不同。 以以上有向网为例第一步定义三个数组lowCost与无向网相同tailVex和headVex代替adjVex分别表示箭头的尾巴和头若为无向网则尾巴和头可以任意初始化tailVex和headVex为0lowCost为无穷大 然后使用arc[0][j]和arc[j][0]与lowCost比较取小的权并记录箭头的尾巴和头可取出最小的权对应的尾巴和头得到最小生成树的第一条弧0,3然后设置lowCost[0]和lowCost[3]为负无穷大表示这两个顶点已连通 然后取arc[3][j]和arc[j][3]重复上述处理得到下一条弧3,5然后设置lowCost[3]和lowCost[5]为负无穷大表示这两个顶点已连通 然后对arc[5][j]和arc[j][5]做类似处理一直到所有顶点都连通。 代码实现如下所示
/*** 生成最小生成树** param visitedVal 已访问的顶点被标记的值* return 最小生成树的边或弧列表* author Korbin* date 2023-02-07 15:23:14**/
SuppressWarnings(unchecked)
public ListString minimumCostSpanningTree(W visitedVal) {ListString result new ArrayList();if (type.equals(BusinessConstants.GRAPH_TYPE.UNDIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED)) {// 最小生成树只针对网return null;}// 用于存储“当前检查的顶点X与顶点j的权W(X,j)”及“顶点tailVex[j]到顶点headVex[j]的权W(adj[j],j)”中较优如果是数值的话就是较小的那个权W[] lowCost (W[]) Array.newInstance(infinity.getClass(), vertexNum);for (int i 0; i vertexNum; i) {lowCost[i] infinity;}// 用于存储箭头的尾和头int[] tailVex new int[vertexNum];int[] headVex new int[vertexNum];// 取权最小的即第一个顶点与其他顶点之间权最小的顶点int index 0;int connectedNum 0;boolean[] visited new boolean[vertexNum];while (connectedNum vertexNum) {// 其他顶点是与lowCost比较取小的W minWeight null;int newIndex index;for (int i 0; i vertexNum; i) {if (i ! index !lowCost[i].equals(visitedVal) arc[index][i].compareTo(lowCost[i]) 0) {lowCost[i] arc[index][i];tailVex[i] index;headVex[i] i;}if (type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED_NETWORK)) {// 有向网还需要处理指向本顶点的顶点if (i ! index !lowCost[i].equals(visitedVal) arc[i][index].compareTo(lowCost[i]) 0) {lowCost[i] arc[i][index];tailVex[i] i;headVex[i] index;}}// 取出最小的权// 忽略自身// 忽略lowCost[j]为已访问过的顶点if (i ! index !lowCost[i].equals(visitedVal)) {if (null minWeight || minWeight.compareTo(lowCost[i]) 0) {minWeight lowCost[i];newIndex i;}}}index newIndex;// 打印取到的边switch (type) {case DIRECTED_NETWORK: {String val tailVex[index] , headVex[index] ;result.add(val);break;}case UNDIRECTED_NETWORK: {String val ( tailVex[index] , headVex[index] );result.add(val);break;}}// 设置已连通的顶点数if (!visited[tailVex[index]]) {visited[tailVex[index]] true;connectedNum;}// 设置该顶点已处理if (!visited[headVex[index]]) {visited[headVex[index]] true;connectedNum;}// 设置lowCost[index]为已访问lowCost[tailVex[index]] visitedVal;lowCost[headVex[index]] visitedVal;}return result;}5.1.2 邻接表的最小生成树 邻接表和逆邻接表的处理方式也是类似只是需要找到指向的和被指向的顶点的权进行比较另外邻接表和逆邻接表的处理方式也会有差异
/*** 生成最小生成树** param visitedVal 已访问的顶点被标记的值* return 最小生成树的边或弧列表* author Korbin* date 2023-02-07 15:23:14**/
SuppressWarnings(unchecked)
public ListString minimumCostSpanningTree(W visitedVal) {ListString result new ArrayList();if (type.equals(BusinessConstants.GRAPH_TYPE.UNDIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED)) {// 最小生成树只针对网return null;}// 用于存储“当前检查的顶点X与顶点j的权W(X,j)”及“顶点adjVex[j]到顶点j的权W(adj[j],j)”中较优如果是数值的话就是较小的那个权W[] lowCost (W[]) Array.newInstance(infinity.getClass(), vertexNum);for (int i 0; i vertexNum; i) {lowCost[i] infinity;}// 用于存储箭头的尾和头int[] tailVex new int[vertexNum];int[] headVex new int[vertexNum];boolean[] visited new boolean[vertexNum];int connectedNum 0;int index 0;while (connectedNum vertexNum) {for (int i 0; i vertexNum; i) {VertexNodeT, W vertexNode vertexes[i];EdgeNodeW edgeNode vertexNode.getFirstEdge();while (null ! edgeNode) {int refIndex edgeNode.getIndex();W weight edgeNode.getWeight();// 邻接表if (i index !lowCost[refIndex].equals(visitedVal) weight.compareTo(lowCost[refIndex]) 0) {// 本顶点指向的if (!reverseAdjacency) {tailVex[refIndex] i;headVex[refIndex] refIndex;lowCost[refIndex] weight;} else {tailVex[refIndex] refIndex;headVex[refIndex] i;lowCost[refIndex] weight;}} else if (refIndex index !lowCost[i].equals(visitedVal) weight.compareTo(lowCost[i]) 0) {if (!reverseAdjacency) {// 指向本顶点的tailVex[i] i;headVex[i] refIndex;lowCost[i] weight;} else {tailVex[i] refIndex;headVex[i] i;lowCost[i] weight;}}edgeNode edgeNode.getNext();}}// 取lowCost中最小的那个W minWeight null;for (int i 0; i vertexNum; i) {// 忽略自身// 忽略lowCost[j]为已访问过的顶点if (i ! index !lowCost[i].equals(visitedVal)) {if (null minWeight || minWeight.compareTo(lowCost[i]) 0) {minWeight lowCost[i];index i;}}}// 打印取到的边switch (type) {case DIRECTED_NETWORK: {String val tailVex[index] , headVex[index] ;result.add(val);// 用于测试System.out.println(val);break;}case UNDIRECTED_NETWORK: {String val ( tailVex[index] , headVex[index] );result.add(val);// 用于测试System.out.println(val);break;}}// 设置已连通的顶点数if (!visited[tailVex[index]]) {visited[tailVex[index]] true;connectedNum;}// 设置该顶点已处理if (!visited[headVex[index]]) {visited[headVex[index]] true;connectedNum;}// 设置lowCost[index]为已访问lowCost[tailVex[index]] visitedVal;lowCost[headVex[index]] visitedVal;// 用于测试StringBuilder builder new StringBuilder(lowCost is [);StringBuilder builder2 new StringBuilder(tailVex is [);StringBuilder builder3 new StringBuilder(headVex is [);for (int i 0; i vertexNum; i) {builder.append(lowCost[i]).append(,);builder2.append(tailVex[i]).append(,);builder3.append(headVex[i]).append(,);}builder.append(]);builder2.append(]);System.out.println(builder);System.out.println(builder2);System.out.println(builder3);}return result;}5.1.3 十字链表的最小生成树 十字链表记录了每个顶点的in和out因此十字链表的处理较为简单。
/*** 生成最小生成树** param visitedVal 已访问的顶点被标记的值* return 最小生成树的边或弧列表* author Korbin* date 2023-02-07 15:23:14**/
SuppressWarnings(unchecked)
public ListString minimumCostSpanningTree(W visitedVal) {ListString result new ArrayList();if (type.equals(BusinessConstants.GRAPH_TYPE.UNDIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED)) {// 最小生成树只针对网return null;}// 用于存储“当前检查的顶点X与顶点j的权W(X,j)”及“顶点adjVex[j]到顶点j的权W(adj[j],j)”中较优如果是数值的话就是较小的那个权W[] lowCost (W[]) Array.newInstance(infinity.getClass(), vertexNum);for (int i 0; i vertexNum; i) {lowCost[i] infinity;}// 用于存储箭头的尾和头int[] tailVex new int[vertexNum];int[] headVex new int[vertexNum];boolean[] visited new boolean[vertexNum];int connectedNum 0;int index 0;while (connectedNum vertexNum) {AcrossLinkVertexNodeT, W vertexNode vertexes[index];// 处理指向自己的AcrossLinkEdgeNodeW inEdge vertexNode.getFirstIn();while (null ! inEdge) {// 自身是headint tailIndex inEdge.getTailIndex();W weight inEdge.getWeight();if (!lowCost[tailIndex].equals(visitedVal) weight.compareTo(lowCost[tailIndex]) 0) {lowCost[tailIndex] weight;tailVex[tailIndex] tailIndex;headVex[tailIndex] index;}inEdge inEdge.getNextTail();}// 处理指向的AcrossLinkEdgeNodeW outEdge vertexNode.getFirstOut();while (null ! outEdge) {// 自身是tailint headIndex outEdge.getHeadIndex();W weight outEdge.getWeight();if (!lowCost[headIndex].equals(visitedVal) weight.compareTo(lowCost[headIndex]) 0) {lowCost[headIndex] weight;tailVex[headIndex] index;headVex[headIndex] headIndex;}outEdge outEdge.getNextHead();}// 取lowCost中最小的那个W minWeight null;for (int i 0; i vertexNum; i) {// 忽略自身// 忽略lowCost[j]为已访问过的顶点if (i ! index !lowCost[i].equals(visitedVal)) {if (null minWeight || minWeight.compareTo(lowCost[i]) 0) {minWeight lowCost[i];index i;}}}// 打印取到的边switch (type) {case DIRECTED_NETWORK: {String val tailVex[index] , headVex[index] ;result.add(val);// 用于测试System.out.println(val);break;}case UNDIRECTED_NETWORK: {String val ( tailVex[index] , headVex[index] );result.add(val);// 用于测试System.out.println(val);break;}}// 设置已连通的顶点数if (!visited[tailVex[index]]) {visited[tailVex[index]] true;connectedNum;}// 设置该顶点已处理if (!visited[headVex[index]]) {visited[headVex[index]] true;connectedNum;}// 设置lowCost[index]为已访问lowCost[tailVex[index]] visitedVal;lowCost[headVex[index]] visitedVal;// 用于测试StringBuilder builder new StringBuilder(lowCost is [);StringBuilder builder2 new StringBuilder(tailVex is [);StringBuilder builder3 new StringBuilder(headVex is [);for (int i 0; i vertexNum; i) {builder.append(lowCost[i]).append(,);builder2.append(tailVex[i]).append(,);builder3.append(headVex[i]).append(,);}builder.append(]);builder2.append(]);System.out.println(builder);System.out.println(builder2);System.out.println(builder3);}return result;}5.1.4 邻接多重表的最小生成树 邻接多重表是对无向网的优化因此我们不考虑有向网而在无向网中通过iVex、iLink、jVex、jLink可以直接定位到某顶点关联的所有顶点因此代码实现如下所示
/*** 生成最小生成树** param visitedVal 已访问的顶点被标记的值* return 最小生成树的边或弧列表* author Korbin* date 2023-02-07 15:23:14**/
SuppressWarnings(unchecked)
public ListString minimumCostSpanningTree(W visitedVal) {ListString result new ArrayList();if (type.equals(BusinessConstants.GRAPH_TYPE.UNDIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED_NETWORK)) {// 最小生成树只针对无向网return null;}// 用于存储“当前检查的顶点X与顶点j的权W(X,j)”及“顶点adjVex[j]到顶点j的权W(adj[j],j)”中较优如果是数值的话就是较小的那个权W[] lowCost (W[]) Array.newInstance(infinity.getClass(), vertexNum);for (int i 0; i vertexNum; i) {lowCost[i] infinity;}// 用于存储箭头的尾和头int[] tailVex new int[vertexNum];int[] headVex new int[vertexNum];boolean[] visited new boolean[vertexNum];int connectedNum 0;int index 0;while (connectedNum vertexNum) {AdjacencyMultiVertexNodeT, W vertexNode vertexes[index];AdjacencyMultiEdgeNodeW edgeNode vertexNode.getFirstEdge();boolean firstEdge true;while (null ! edgeNode) {int refIndex index;int iVex edgeNode.getIVex();int jVex edgeNode.getJVex();W weight edgeNode.getWeight();if (firstEdge) {refIndex jVex;edgeNode edgeNode.getILink();firstEdge false;} else {if (iVex index) {refIndex jVex;} else if (jVex index) {refIndex iVex;}edgeNode edgeNode.getJLink();}if (!lowCost[refIndex].equals(visitedVal) weight.compareTo(lowCost[refIndex]) 0) {lowCost[refIndex] weight;tailVex[refIndex] iVex;headVex[refIndex] jVex;}}// 取lowCost中最小的那个W minWeight null;for (int i 0; i vertexNum; i) {// 忽略自身// 忽略lowCost[j]为已访问过的顶点if (i ! index !lowCost[i].equals(visitedVal)) {if (null minWeight || minWeight.compareTo(lowCost[i]) 0) {minWeight lowCost[i];index i;}}}// 打印取到的边switch (type) {case DIRECTED_NETWORK: {String val tailVex[index] , headVex[index] ;result.add(val);// 用于测试System.out.println(val);break;}case UNDIRECTED_NETWORK: {String val ( tailVex[index] , headVex[index] );result.add(val);// 用于测试System.out.println(val);break;}}// 设置已连通的顶点数if (!visited[tailVex[index]]) {visited[tailVex[index]] true;connectedNum;}// 设置该顶点已处理if (!visited[headVex[index]]) {visited[headVex[index]] true;connectedNum;}// 设置lowCost[index]为已访问lowCost[tailVex[index]] visitedVal;lowCost[headVex[index]] visitedVal;// 用于测试StringBuilder builder new StringBuilder(lowCost is [);StringBuilder builder2 new StringBuilder(tailVex is [);StringBuilder builder3 new StringBuilder(headVex is [);for (int i 0; i vertexNum; i) {builder.append(lowCost[i]).append(,);builder2.append(tailVex[i]).append(,);builder3.append(headVex[i]).append(,);}builder.append(]);builder2.append(]);System.out.println(builder);System.out.println(builder2);System.out.println(builder3);}return result;}5.5.5 边集数组的最小生成树 边集数组的最小生成树实现代码如下所示
/*** 生成最小生成树** param visitedVal 已访问的顶点被标记的值* return 最小生成树的边或弧列表* author Korbin* date 2023-02-07 15:23:14**/
SuppressWarnings(unchecked)
public ListString minimumCostSpanningTree(W visitedVal) {ListString result new ArrayList();if (type.equals(BusinessConstants.GRAPH_TYPE.UNDIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED)) {// 最小生成树只针对网return null;}// 用于存储“当前检查的顶点X与顶点j的权W(X,j)”及“顶点adjVex[j]到顶点j的权W(adj[j],j)”中较优如果是数值的话就是较小的那个权W[] lowCost (W[]) Array.newInstance(infinity.getClass(), vertexNum);for (int i 0; i vertexNum; i) {lowCost[i] infinity;}// 用于存储箭头的尾和头int[] tailVex new int[vertexNum];int[] headVex new int[vertexNum];boolean[] visited new boolean[vertexNum];int connectedNum 0;int index 0;while (connectedNum vertexNum) {for (int i 0; i edgeNum; i) {EdgeListEdgeNodeW edgeNode arc[i];int begin edgeNode.getBegin();int end edgeNode.getEnd();W weight edgeNode.getWeight();if (begin index !lowCost[end].equals(visitedVal) weight.compareTo(lowCost[end]) 0) {lowCost[end] weight;tailVex[end] begin;headVex[end] end;} else if (end index !lowCost[begin].equals(visitedVal) weight.compareTo(lowCost[begin]) 0) {lowCost[begin] weight;tailVex[begin] begin;headVex[begin] end;}}// 取lowCost中最小的那个W minWeight null;for (int i 0; i vertexNum; i) {// 忽略自身// 忽略lowCost[j]为已访问过的顶点if (i ! index !lowCost[i].equals(visitedVal)) {if (null minWeight || minWeight.compareTo(lowCost[i]) 0) {minWeight lowCost[i];index i;}}}// 打印取到的边switch (type) {case DIRECTED_NETWORK: {String val tailVex[index] , headVex[index] ;result.add(val);// 用于测试System.out.println(val);break;}case UNDIRECTED_NETWORK: {String val ( tailVex[index] , headVex[index] );result.add(val);// 用于测试System.out.println(val);break;}}// 设置已连通的顶点数if (!visited[tailVex[index]]) {visited[tailVex[index]] true;connectedNum;}// 设置该顶点已处理if (!visited[headVex[index]]) {visited[headVex[index]] true;connectedNum;}// 设置lowCost[index]为已访问lowCost[tailVex[index]] visitedVal;lowCost[headVex[index]] visitedVal;// 用于测试StringBuilder builder new StringBuilder(lowCost is [);StringBuilder builder2 new StringBuilder(tailVex is [);StringBuilder builder3 new StringBuilder(headVex is [);for (int i 0; i vertexNum; i) {builder.append(lowCost[i]).append(,);builder2.append(tailVex[i]).append(,);builder3.append(headVex[i]).append(,);}builder.append(]);builder2.append(]);System.out.println(builder);System.out.println(builder2);System.out.println(builder3);}return result;}5.2 克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔的官方描述是“假设N(V,{E})是连通网则令最小生成树的初始状态为只有n个顶点而无边的非连通图T(V,{})图中每个顶点自成一个连通分量。在E中选择代价最小的边若该边依附的顶点落在T中不同的连通分量上则将此边加入到T中否则舍去此边选择下一条代价最小的边。依此类推直到T中所有顶点都在同一连通分量上为止”。 克鲁斯卡尔算法针对的是边因此我们用边集数组来进行克鲁斯卡尔算法的实现描述以以下边集数组为例 首先我们定义一个数组connected来存储已连通的分量长度为顶点长度默认值均为无穷大表示所有顶点均为连通 这里面的规则是如果connected[i]j,connected[j]x,connected[x]∞\infty∞则表示顶点i、j、x是连通的。 然后我们把边集数组按权由小到大排序 迭代边集数组首先是arc[0]begin4end7connected[4]∞\infty∞connected[7]∞\infty∞这两个顶点未连通我们把它们连通起来输出第一个连通分量的第一条边(4,7)同时令connected[4]7表示这两个顶点已连通 然后是arc[1]begin2end8connected[2]∞\infty∞connected[8]∞\infty∞这两个顶点未连通我们把它们连通起来输出第二个连通分量的第一条边(2,8)同时令connected[2]8表示这两个顶点已连通 后续arc[2]处理方式同上 然后看arc[3]begin0end5注意到connected[0]1表示第0和第1个顶点是已经连通的第0个顶点已在一个连通分量内我们继续看这个连通分量里面有哪些顶点connected[0]1connected[1]∞\infty∞按上面定的规则表示这个连通分量里面只有0和1两个顶点connected[5]∞\infty∞表示顶点5没有在任何一个连通分量内这时我们令connected[1]5表示顶点0、1、5在同一个连通分量内并输出(0,5)表示这个边是这个连通分量的一条边 然后看arc[4]begin1end8因connected[1]5connected[5]0connected[8]∞\infty∞表示顶点1和顶点5在同一个连通分量内但这个连通分量不包含顶点8因此令connected[5]8并输出边(1,8)将顶点8也加入到这个连通分量内 接下来arc[5]和arc[6]的处理方式类似 来看arc[7]begin5end6此时connected[5]8connected[8]6connected[6]0即顶点5、8、6在一个连通分量内即begin和end都在一个连通分量内不需要处理跳过。 arc[8]与arc[7]一致相关顶点都在同一个连通分量内不需要处理跳过。 继续迭代arc按如上规则处理能得到最终的最小生成树。 代码实现如下所示
/*** 生成最小生成树克鲁斯卡尔算法** return 最小生成树的边或弧列表* author Korbin* date 2023-02-13 15:09:58**/
public ListString minimumCostSpanningTree() {ListString result new ArrayList();if (type.equals(BusinessConstants.GRAPH_TYPE.UNDIRECTED) ||type.equals(BusinessConstants.GRAPH_TYPE.DIRECTED)) {// 最小生成树只针对网return null;}// 对边集数组按权从小到大进行排序sortArc(0, edgeNum);// 定义一个数组并初始化为infinity用于表示连通分量int[] connected new int[vertexNum];for (int i 0; i vertexNum; i) {connected[i] -1;}// 迭代边集数组for (int i 0; i edgeNum; i) {EdgeListEdgeNodeW edgeNode arc[i];int begin edgeNode.getBegin();int end edgeNode.getEnd();// 寻找begin对应的连通分量int beginComponent begin;while (connected[beginComponent] ! -1) {beginComponent connected[beginComponent];}// 寻找end对应的连通分量int endComponent end;while (connected[endComponent] ! -1) {endComponent connected[endComponent];}// 如果不在同一个连通分量if (beginComponent ! endComponent) {connected[beginComponent] end;switch (type) {case UNDIRECTED_NETWORK: {String val ( begin , end );result.add(val);break;}case DIRECTED_NETWORK: {String val begin , end ;result.add(val);break;}}}}return result;
}5.3 总结 普里姆Prim算法从一个顶点出发X取其他所有顶点与X连通的权中最小权对应的那个顶点Y放入连通分量TE中然后取其他所有顶点与X和Y连通的权中最小权对应的那个顶点Z放入连通分量中直到所有的顶点都在连通分量中时最小生成树生成。 克鲁斯卡尔Kruskal算法把所有的边放到一个数组中按权从小到大排序然后从第一条边开始迭代判断begin和end是否在同一个连通分量若不在则把他们连通起来直到所有边都处理完毕。 相对来讲克鲁斯卡算法更适用于边集数组而普里姆虽然各类存储结构都可以实现但时间复杂度不同
存储结构普里姆算法克鲁斯卡尔算法适用性最差时间复杂度适用性最差时间复杂度邻接矩阵适用O(n2) 不适用--邻接表适用O(n3)不适用--十字链表适用O(n2) 不适用--邻接多重表适用O(n2) 不适用--边集数组适用O(n2) 适用O(nlog(n)) 注本文为程 杰老师《大话数据结构》的读书笔记其中一些示例和代码是笔者阅读后自行编制的。
