您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

普利姆算法(图文)

第十三双眼睛2023-10-23【数据结构与算法】人已围观

简介普利姆算法

普利姆算法

package com.xingchen.day017;
import java.util.Arrays;
public class Prim {

public static void main(String[] args) {
char[] data = {'A','B','C','D','E','F','G'};
int vertex = data.length;
int[][] weight = {
{1000,5,7,1000,1000,1000,2},
{5,1000,1000,9,1000,1000,3},
{7,1000,1000,1000,8,1000,1000},
{1000,9,1000,1000,1000,4,1000},
{1000,1000,8,1000,1000,5,4},
{1000,1000,1000,4,5,1000,6},
{2,3,1000,1000,4,6,1000},
};
MGraph mGraph = new MGraph(vertex);
MinTree minTree = new MinTree();
minTree.createGraph(mGraph, vertex,data,weight);
minTree.show(mGraph);
minTree.prim(mGraph,0);
}
}
class MinTree {
public void createGraph(MGraph mGraph, int vertex,char[] data,int[][] weight) {
for (int i = 0; i<vertex ;i ++) {
mGraph.data[i] = data[i];
for (int j= 0 ;j<vertex; j++) {
mGraph.weight[i][j] = weight[i][j];
}
}
}
public void show(MGraph mGraph) {
for (int[] link : mGraph.weight) {
System.out.println(Arrays.toString(link));
}
}
public void prim(MGraph mGraph, int v) {
//标记顶点是否被访问过
int[] visited = new int[mGraph.vertex];
//把当前节点标记为已访问
visited[v] = 1;
int h1 = -1;
int h2 = -1;
int minWeight = 1000;
for (int k = 1; k<mGraph.vertex; k++) { //运行完毕后，会有vertex- 1条边
for (int i = 0;i<mGraph.vertex; i ++) {
for (int j = 0;j<mGraph.vertex; j ++) {
//寻找访问过的和未访问过的节点之间权值最小的边
if (visited[i] == 1 && visited[j] ==0 && mGraph.weight[i][j] < minWeight) {
minWeight = mGraph.weight[i][j];
h1 = i;
h2 = j;
}
}
}
System.out.println("边" + mGraph.data[h1] + "" + mGraph.data[h2] +"权值:" + minWeight);
visited[h2] = 1;
minWeight = 1000;
}
}
}
class MGraph {
public int vertex;
char[] data;//表示节点数据
int[][] weight;//存放边
public MGraph(int vertex) {
this.vertex = vertex;
this.data = new char[vertex];
weight = new int[vertex][vertex];
}
}

Tags：

很赞哦！ ()

上一篇：贪心算法(图文)

下一篇：克鲁斯卡尔算法(图文)