我想用java写一个prim的算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18009158/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
I want to write a prim's algorithm in java
提问by JustSt
actually, I want to know the meaning of the prim and Dijkstra algorithm. and I appreciate if someone could teach how to write it in JAVA. I try to understand someone's code of prim's algorithm, but I stuck at someplace.
其实，我想知道prim和Dijkstra算法的含义。如果有人可以教如何用 JAVA 编写它，我很感激。我试图理解某人的 prim 算法代码，但我卡在了某个地方。
The code showing below is a random matrix. and I want to proceed to write prim's algorithm. is there anybody can help?
下面显示的代码是一个随机矩阵。我想继续编写 prim 的算法。有人可以帮忙吗？
import java.util.*;
class RandomGraph
{
public static Scanner br = new Scanner(System.in);
static int w [][];
static int n;
static int i, j;
public static void main (String[] args)
{
System.out.println("Find the shortest edge");
System.out.println("\nEnter the number of the vertices: ");
n = br.nextInt();
w = new int[n+1][n+1];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if((i!=j))
{
w[i][j] = w[j][i]= 1+(int)(Math.random()*9);
}
else if(i == j)
{
w[i][j] = w[j][i] = 0;
}
}
Graph();
}
static void Graph()
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
System.out.print(" "+w[i][j]+" ");
}
System.out.println();
}
}
}
采纳答案by Ankur Lathi
Prims Algorithms Implementation In Java - Minimum Cost Spanning Tree
public class Prim {
int weightArray[][] = new int[20][20];
int visited[] = new int [20];
int d[] = new int[20];
int p[] = new int[20];
int verticeCount, edgeCount;
int nodeA, nodeB, weight;
int current, total, mincost;
public static void main(String args[]) throws IOException {
// Instantiate the graph based on input
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("\nEnter number of vertices: ");
verticeCount = Integer.parseInt(buf.readLine());
System.out.print("\nEnter number of edges: ");
edgeCount = Integer.parseInt(buf.readLine());
for (int i = 1; i <= verticeCount; i++) {
for(int j = 1; j <= verticeCount; j++) {
weightArray[i][j] = 0;
}
}
for (int i = 1; i <= verticeCount; i++) {
p[i] = visited[i] = 0;
d[i] = 32767;
}
for (int i = 1; i <= edgeCount; i++) {
System.out.print("\nEnter edge nodeA, nodeB and weightArray weight: ");
nodeA=Integer.parseInt(in.readLine());
nodeB=Integer.parseInt(in.readLine());
weight=Integer.parseInt(in.readLine());
weightArray[nodeA][nodeB] = weightArray[nodeB][nodeA] = weight;
}
// End of graph instantiation
current = 1;
d[current] = 0;
total = 1;
visited[current] = 1;
while( total != verticeCount) {
for (int i = 1; i <= verticeCount; i++) {
if ( weightArray[current][i] != 0) {
if( visited[i] == 0) {
if (d[i] > weightArray[current][i]) {
d[i] = weightArray[current][i];
p[i] = current;
}
}
}
}
mincost=32767;
for (int i = 1 ; i <= verticeCount; i++) {
if (visited[i] == 0) {
if (d[i] < mincost) {
mincost = d[i];
current = i;
}
}
}
visited[current]=1;
total++;
}
mincost=0;
for(i=1;i<=verticeCount;i++)
mincost=mincost+d[i];
System.out.print("\n Minimum cost="+mincost);
System.out.print("\n Minimum Spanning tree is");
for(i=1;i<=verticeCount;i++)
System.out.print("\n vertex" +i+"is connected to"+p[i]);
}
}
回答by Hariharan
Prim's algorithm:
Prim 算法：
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
Prim 算法是一种贪心算法，它为连通的加权无向图寻找最小生成树。这意味着它会找到形成包含每个顶点的树的边的子集，其中树中所有边的总权重最小。
Definition:
定义：
- Create a tree containing a single vertex, chosen arbitrarily from the graph
- Create a set containing all the edges in the graph
Loop until every edge in the set connects two vertices in the tree
- Remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
Add that edge to the tree
- 创建一个包含单个顶点的树，从图中任意选择
- 创建一个包含图中所有边的集合
循环直到集合中的每条边都连接树中的两个顶点
- 从集合中移除连接树中顶点与树中顶点的最小权重边
将该边添加到树中
Wiki link - http://en.wikipedia.org/wiki/Prim's_algorithm
维基链接 - http://en.wikipedia.org/wiki/Prim's_algorithm
Example link:
示例链接：
http://sourcecodesforfree.blogspot.in/2013/05/10-prims-algorithm.html
http://sourcecodesforfree.blogspot.in/2013/05/10-prims-algorithm.html
