首页 > 代码库 > 数据结构之图应用最小生成树
数据结构之图应用最小生成树
数据结构之图应用最小生成树
最小生成树说白了就是用最少的边把所有的顶点连接起来。最小生成树是不唯一的，但是最小生成树满足边的数量比点的数量少1.最小生成树不关心边的长度也不需要找到最短的路径，而是要找到最少数量的边，创建最小生成树的算法与图的搜索算法几乎相同。下边的例子是基于深度优先搜索算法实现的，在执行深度搜索的时候记录走过的边，就可以创建一个最小的生成树。
代码：
//最小生成树的算法 public void mst() { //从0开始 vertexs[0].wasVisited = true; //把这个点压入栈中 myStack.push(0); while(!myStack.isEmpty()) { int v1 = myStack.peek(); int v = getAdjUnvisitedVertex(v1); if(v == -1) { myStack.pop(); }else{ vertexs[v].wasVisited = true; myStack.push(v); displayVertex(v1); displayVertex(v); System.out.print(" "); } } //如果栈已经为空就结束 for(int i = 0;i<currentVertexs;i++) { vertexs[i].wasVisited = false; } }
最小生成树比较容易从深度优先搜索得到，这是因为DFS访问所有的点只访问了一次，因此DFS走过的路径必定是最小生成树。
数据结构之图应用最小生成树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。