本文目录一览：
- 1、无向图最短主树生成程序 java
- 2、java 最小生成树
- 3、图的最小生成树算法？
- 4、求出如图二所示赋权图中的最小生成树（要求写出求解步骤），并求此 最小生成树的权．
- 5、最小生成树怎么求
- 6、数据结构算法 试题 急！ 试构造下图的最小生成树，要求分步给出构造过程。
无向图最短主树生成程序 java
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Random;
public class GAFrame extends JFrame {
private static final long serialVersionUID = 1L;
static TopologyPanel tpnl = new TopologyPanel();
private String[] ipop = new String[10]; // 染色体
private int gernation = 0; // 染色体代号
public static final int GENE = 9; // 基因数
public GAFrame(String title) {
super(title);
}
public static void main(String args[]) {
tpnl.setLayout(null);
GAFrame frame = new GAFrame("遗传算法寻找最优路径");
frame.setContentPane(tpnl);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(370, 330);
JButton button1 = new JButton();
button1.setText("生成参数");
button1.setBounds(5, 245, 90, 25);
button1.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
tpnl.refreshPanel1();
}
});
JButton button2 = new JButton();
button2.setText("生成路径");
button2.setBounds(245, 245, 90, 25);
button2.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
tpnl.refreshPanel2();
}
});
tpnl.add(button1);
tpnl.add(button2);
frame.setVisible(true);
}
}
class TopologyPanel extends JPanel {
private static int[][] params1 = new int[8][2];
private static int[] params2 = new int[13];
private static Random rnd = new Random();
public void paint(Graphics g) {
super.paint(g);
g.fillOval(30, 120, 10, 10);
g.fillOval(100, 30, 10, 10);
g.fillOval(80, 210, 10, 10);
g.fillOval(140, 130, 10, 10);
g.fillOval(210, 50, 10, 10);
g.fillOval(260, 120, 10, 10);
g.fillOval(160, 230, 10, 10);
g.fillOval(230, 190, 10, 10);
g.drawLine(35, 125, 105, 30);
g.drawLine(105, 35, 215, 55);
g.drawLine(215, 55, 265, 125);
g.drawLine(265, 125, 235, 195);
g.drawLine(235, 195, 165, 235);
g.drawLine(85, 215, 165, 235);
g.drawLine(35, 125, 85, 215);
g.drawLine(35, 125, 145, 135);
g.drawLine(85, 215, 235, 195);
g.drawLine(105, 35, 145, 135);
g.drawLine(215, 55, 145, 135);
g.drawLine(265, 125, 145, 135);
g.drawLine(85, 215, 145, 135);
g.drawString("A", 21, 120);
g.drawString("B", 92, 30);
g.drawString("C", 70, 220);
g.drawString("D", 225, 60);
g.drawString("E", 148, 148);
g.drawString("F", 160, 253);
g.drawString("G", 245, 202);
g.drawString("H", 270, 130);
g.drawString("( " + params1[0][0] + ", " + params1[0][1] + " )", 30,
120);// A
g.drawString("( " + params1[1][0] + ", " + params1[1][1] + " )", 100,
30);// B
g.drawString("( " + params1[2][0] + ", " + params1[2][1] + " )", 80,
210);// C
g.drawString("( " + params1[3][0] + ", " + params1[3][1] + " )", 140,
130);// E
g.drawString("( " + params1[4][0] + ", " + params1[4][1] + " )", 210,
50);// D
g.drawString("( " + params1[5][0] + ", " + params1[5][1] + " )", 255,
115);// H
g.drawString("( " + params1[6][0] + ", " + params1[6][1] + " )", 160,
230);// F
g.drawString("( " + params1[7][0] + ", " + params1[7][1] + " )", 230,
190);// G
g.drawString("" + params2[0], 70, 77);// A-B
g.drawString("" + params2[1], 160, 45);// BD
g.drawString("" + params2[2], 240, 90);// DH
g.drawString("" + params2[3], 250, 160);// GH
g.drawString("" + params2[4], 200, 215);// FG
g.drawString("" + params2[5], 125, 225);// CF
g.drawString("" + params2[6], 60, 170);// AC
g.drawString("" + params2[7], 90, 130);// AE
g.drawString("" + params2[8], 160, 205);// CG
g.drawString("" + params2[9], 125, 85);// BE
g.drawString("" + params2[10], 180, 95);// DE
g.drawString("" + params2[11], 205, 140);// EH
g.drawString("" + params2[12], 115, 175);// CE
}
public void refreshPanel1() {
for (int i = 0; i params1.length; i++) {
params1[i][0] = (rnd.nextInt(21) + 10) * 100;
params1[i][1] = rnd.nextInt(41) + 20;
}
for (int i = 0; i params2.length; i++)
params2[i] = ((rnd.nextInt(91)) + 10) * 10;
repaint();
}
public void refreshPanel2() {
// TopologyPanel tt = new TopologyPanel();
//
// tt.tenacc();
GAFrame.tpnl.tenacc();
}
String inialPop() {
Character s[] = new Character[9];
String[] a = new String[9];
a[0] = "1";
for (int i = 0; i s.length; i++) {
s[i] = '-';
}
if (Math.random() 1 / 3.0) {
s[0] = 'B';
} else if (Math.random() = 1.0 / 3.0 Math.random() 2.0 / 3.0) {
s[0] = 'C';
} else
s[0] = 'E';
switch (s[0]) {
case 'B': {// ss[0]选择B
a[1] = "1";
a[2] = a[6] = a[3] = "0";
if (Math.random() 0.5) {
s[1] = 'D';
} else {
s[1] = 'E';
}
switch (s[1]) {
case 'D': {
a[4] = "1";
a[5] = "0";
if (Math.random() 0.5) {
s[4] = 'H';
} else {
s[4] = 'E';
}
switch (s[4]) {
case 'H': {
a[7] = a[8] = "0";
}
break;
case 'E': {
a[7] = "1";
if (Math.random() 0.5) {
s[7] = 'H';
} else {
s[7] = 'C';
}
switch (s[7]) {
case 'H': {
a[8] = "0";
}
break;
case 'C': {
a[8] = "1";
if (Math.random() 0.5) {
s[8] = 'G';
} else {
s[8] = 'F';
}
}
}
}
}
}
break;
case 'E': {
a[4] = a[7] = "0";
a[5] = "1";
if (Math.random() 1 / 3.0) {
s[5] = 'H';
} else if (Math.random() = 1.0 / 3.0
Math.random() 2.0 / 3.0) {
s[5] = 'C';
} else
s[5] = 'D';
switch (s[5]) {
case 'H':
case 'D': {
a[8] = "0";
}
break;
case 'C': {
a[8] = "1";
if (Math.random() 0.5) {
s[8] = 'G';
} else {
s[8] = 'F';
}
}
}
}
}
}
break;
case 'E': {// s[0]选择E
a[2] = "1";
a[1] = a[3] = a[4] = a[5] = a[7] = a[6] = "0";
if (Math.random() 0.25) {
s[2] = 'B';
} else if (Math.random() = 0.25 Math.random() 0.5) {
s[2] = 'C';
} else if (Math.random() = 0.5 Math.random() 0.75) {
s[2] = 'D';
} else
s[2] = 'H';
switch (s[2]) {
case 'H':
case 'D':
case 'B': {
a[8] = "0";
}
break;
case 'C': {
a[8] = "1";
if (Math.random() 0.5) {
s[8] = 'G';
} else {
s[8] = 'F';
}
}
}
}
break;
case 'C': {// ss[0]选择C
a[1] = a[2] = a[4] = a[5] = a[7] = a[8] = "0";
a[3] = "1";
if (Math.random() 1 / 3.0) {
s[3] = 'G';
} else if (Math.random() = 1.0 / 3.0 Math.random() 2.0 / 3.0) {
s[3] = 'F';
} else
s[3] = 'E';
switch (s[3]) {
case 'G':
case 'F': {
a[6] = "0";
}
break;
case 'E': {
a[6] = "1";
if (Math.random() 1 / 3.0) {
s[6] = 'H';
} else if (Math.random() = 1.0 / 3.0
Math.random() 2.0 / 3.0) {
s[6] = 'D';
} else
s[6] = 'B';
}
}
}
}
String res = "";
StringBuffer bf = new StringBuffer();
for (int i = 0; i s.length; i++) {
bf.append(s[i]);
}
res = bf.toString();
return res;
}
String[] inialPops() {
String[] ipop = new String[10];
for (int i = 0; i 10; i++) {
ipop[i] = inialPop();
System.out.println(ipop[i]);
}
for (int i = 0; i params1.length; i++) {
System.out.print(params1[i][0] + " ");
}
return ipop;
}
double calcfit() {
int bw = 0;
int delay = 0;
int len = 0;
String ss = inialPop();
char[] s = ss.toCharArray();
switch (s[0]) {
case 'B': {// A-B
if (params1[0][0] params1[1][0]) {
bw = params1[1][0];
} else {
bw = params1[0][0];
}
delay = params1[0][1] + params1[1][1];
len += params2[0];
switch (s[1]) {
case 'D': {// ABD
if (params1[4][0] bw) {
bw = params1[4][0];
}
delay += params1[4][1];
len += params2[1];
switch (s[4]) {
case 'H': {// ABDH
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1];
len += params2[2];
}
break;
case 'E': {// ABDE
if (params1[3][0] bw) {
bw = params1[3][0];
}
delay += params1[3][1];
len += params2[9];
switch (s[7]) {
case 'H': {// ABDEH
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1];
len += params2[11];
}
break;
case 'C': {// ABDEC
if (params1[2][0] bw) {
bw = params1[5][0];
}
delay += params1[2][1];
len += params2[12];
switch (s[8]) {
case 'G': {// ABDECGH
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1];
len = len + params2[8] + params2[3];
}
break;
case 'F': {// ABDECFGH
if (params1[6][0] bw) {
bw = params1[6][0];
}
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1]
+ params1[6][1];
len = len + params2[5] + params2[4] + params2[3];
}
}
}
}
}
}
}
break;
case 'E': {// ABE
if (params1[3][0] bw) {
bw = params1[3][0];
}
delay += params1[3][1];
len += params2[9];
switch (s[5]) {
case 'H': {// ABEH
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1];
len += params2[11];
}
break;
case 'D': {// ABEDH
if (params1[4][0] bw) {
bw = params1[4][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1] + params1[4][1];
len += params2[10] + params2[2];
}
break;
case 'C': {// ABEC
if (params1[2][0] bw) {
bw = params1[2][0];
}
delay += params1[2][1];
len += params2[12];
switch (s[8]) {
case 'G': {// ABECGH
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1] + params1[7][1];
len += params2[8] + params2[3];
}
break;
case 'F': {
if (params1[6][0] bw) {
bw = params1[6][0];
}
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1]
+ params1[6][1];
len = len + params2[5] + params2[4] + params2[3];
}
}
}
}
}
}
}
break;
case 'E': {// AE
if (params1[0][0] params1[3][0]) {
bw = params1[0][0];
} else {
bw = params1[3][0];
}
delay = params1[0][1] + params1[3][1];
len = params2[7];
switch (s[2]) {
case 'H': {// AEH
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1];
len += params2[11];
}
break;
case 'D': {// AEDH
if (params1[4][0] bw) {
bw = params1[4][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1] + params1[4][1];
len += params2[10] + params2[2];
}
break;
case 'B': {// AEBDH
if (params1[1][0] bw) {
bw = params1[1][0];
}
if (params1[4][0] bw) {
bw = params1[4][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1] + params1[4][1] + params1[1][1];
len += params2[9] + params2[1] + params2[2];
}
break;
case 'C': {// AEC
if (params1[2][0] bw) {
bw = params1[5][0];
}
delay += params1[2][1];
len += params2[12];
switch (s[8]) {
case 'G': {// AECGH
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1];
len = len + params2[8] + params2[3];
}
break;
case 'F': {// AECFGH
if (params1[6][0] bw) {
bw = params1[6][0];
}
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1]
+ params1[6][1];
len = len + params2[5] + params2[4] + params2[3];
}
}
}
}
}
break;
case 'C': {// AC
if (params1[0][0] params1[2][0]) {
bw = params1[0][0];
} else {
bw = params1[2][0];
}
delay = params1[0][1] + params1[2][1];
len = params2[6];
switch (s[3]) {
case 'G': {// ACGH
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1];
len = len + params2[8] + params2[3];
}
break;
case 'F': {// ACFGH
if (params1[6][0] bw) {
bw = params1[6][0];
}
if (params1[7][0] bw) {
bw = params1[7][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay = delay + params1[5][1] + params1[7][1] + params1[6][1];
len = len + params2[5] + params2[4] + params2[3];
}
break;
case 'E': {// ACE
if (params1[3][0] bw) {
bw = params1[3][0];
}
delay += params1[3][1];
len += params2[12];
switch (s[6]) {
case 'H': {// ACEH
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1];
len += params2[11];
}
break;
case 'D': {// ACEDH
if (params1[4][0] bw) {
bw = params1[4][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1] + params1[4][1];
len += params2[10] + params2[2];
}
break;
case 'B': {// AEBDH
if (params1[1][0] bw) {
bw = params1[1][0];
}
if (params1[4][0] bw) {
bw = params1[4][0];
}
if (params1[5][0] bw) {
bw = params1[5][0];
}
delay += params1[5][1] + params1[4][1] + params1[1][1];
len += params2[9] + params2[1] + params2[2];
}
}
}
}
}
}
double fitness1 = ((bw - 2000) + (200 - delay) * 10);
double fitness = fitness1 / len;
return fitness;
}
private void cross() {
String temp1, temp2;
for (int i = 0; i 10; i++) {
if (Math.random() 0.25) {
double r = Math.random();
int pos = (int) (Math.round(r * 1000)) % 9;
if (pos == 0) {
pos = 1;
}
Object[] ipop = null;
temp1 = ((String) ipop[i]).substring(0, pos)
+ ((String) ipop[(i + 1) % 10]).substring(pos);
temp2 = ((String) ipop[(i + 1) % 10]).substring(0, pos)
+ ((String) ipop[i]).substring(pos);
ipop[i] = temp1;
ipop[(i + 1) / 10] = temp2;
}
}
}
private void mutation() {
for (int i = 0; i 4; i++) {
int num = (int) (Math.random() * 9 * 10 + 1);
int chromosomeNum = (int) (num / 9) + 1;
int mutationNum = num - (chromosomeNum - 1) * 9;
if (mutationNum == 0)
mutationNum = 1;
chromosomeNum = chromosomeNum - 1;
if (chromosomeNum = 10)
chromosomeNum = 9;
String temp;
Object[] ipop = null;
if (((String) ipop[chromosomeNum]).charAt(mutationNum - 1) == '0') {
if (mutationNum == 1) {
temp = "1" + ((String) ipop[chromosomeNum]).substring
(mutationNum);
} else {
if (mutationNum != 9) {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum -
1)
+ "1" + ((String) ipop
[chromosomeNum]).substring(mutationNum);
} else {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum - 1)
+ "1";
}
}
} else {
if (mutationNum == 1) {
temp = "0" + ((String) ipop[chromosomeNum]).substring
(mutationNum);
} else {
if (mutationNum != 9) {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum -
1)
+ "0" + ((String) ipop
[chromosomeNum]).substring(mutationNum);
} else {
temp = ((String) ipop[chromosomeNum]).substring(0,
mutationNum - 1)
+ "1";
}
}
}
ipop[chromosomeNum] = temp;
}
}
public String process() {
String str = "";
for (int i = 0; i 10000; i++) {
this.inialPop();
this.cross();
this.mutation();
}
return str;
}
double acc() {
double qwe = calcfit();
System.out.println(qwe);
return qwe;
}
private void tenacc() {
double[] ds = new double[10];
String[] ipop = new String[10];
for (int i = 0; i 10; i++) {
ipop[i] = inialPop();
ds[i] = calcfit();
// System.out.println(ipop[i]);
// System.out.println(ds[i]);
}
for (int i = 1; i ds.length; i++) {
if (ds[0] ds[i]) {
ipop[0] = ipop[i];
}
}
Graphics g = null;
g = getGraphics();
super.paint(g);
// g.clearRect(0, 0, 400, 400);
g.fillOval(30,120,10,10);
g.fillOval(100,30,10,10);
g.drawString("E",148,148);
g.drawString("F",160,253);
g.drawString("G",245,202);
g.drawString("H",270,130);
}
}
/*
* private void paintComponent(Graphics gg) { super.paintComponent(gg);
* Graphics2D g = (Graphics2D)gg; g.setStroke(new BasicStroke(10));
* g.drawOval(100,50,200,200); this.repaint(); }
*/
java 最小生成树
public class AbstractGraphV
{
public AbstractGraph(List?extends Edge edges, ListVvertices)
{
}
public static class Edge
{
}
}
public class WeightedGraph extends AbstractGraphFloat
{
public WeightedGraph(ListWeightedEdge edges, ListFloat vertices)
{
super(edges, vertices);
}
public static class WeightedEdge extends Edge
{
}
}
试试这种？
图的最小生成树算法？
图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树.
求出如图二所示赋权图中的最小生成树（要求写出求解步骤），并求此 最小生成树的权．
①将带权连通图G=n,m的各边按权从小到大依次排列，如e1,e2,…,em,其中e1的权最小，em的权最大，m为边数。
②取权最小的两条边构成边集T0，即T0={e1,e2},从e3起，按次序逐个将各边加进集合T0中去，若出现回路则将这条边排除（不加进去），按此法一直进行到em，最后得到n-1条边的集合T0={e1,e2,…,en-1}，则T0导出的子图就是图G的最小生成树。
最小生成树怎么求
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
当一条边（u，v）加入T时，必须保证T∪{(u，v)}仍是MST的子集，我们将这样的边称为T的安全边。
伪代码
GenerieMST(G){//求G的某棵MST
T〈-￠； //T初始为空，是指顶点集和边集均空
while T未形成G的生成树 do{
找出T的一条安全边（u，v）；//即T∪{(u，v)}仍为MST的子集
T=T∪{(u，v)}； //加入安全边，扩充T
}
return T； //T为生成树且是G的一棵MST
}
注意：
下面给出的两种求MST的算法均是对上述的一般算法的求精，两算法的区别仅在于求安全边的方法不同。
为简单起见，下面用序号0，1，…，n-1来表示顶点集，即是：
V(G)={0，1，…，n-1}，
G中边上的权解释为长度，并设T=(U，TE）。
求最小生成树的具体算法（pascal):
Prim算法
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点 k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]min) and (lowcost[j]0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k 加入生成树}
{生成树中增加一条新的边 k 到 closest[k]}
{修正各点的 lowcost 和 closest 值}
for j:=1 to n do
if cost[k,j]lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;
Kruskal算法
按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点 v 所在的集合}
var i:integer;
begin
i:=1;
while (i=n) and (not v in vset) do inc(i);
if i=n then find:=i else find:=0;
end;
procedure kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=i;{初始化定义 n 个集合，第 I个集合包含一个元素 I}
p:=n-1; q:=1; tot:=0; {p 为尚待加入的边数，q 为边集指针}
sort;
{对所有边按权值递增排序，存于 e中，e.v1 与 e.v2 为边 I 所连接的两个顶点的
序号，e.len 为第 I条边的长度}
while p0 do begin
i:=find(e[q].v1）;j:=find(e[q].v2）;
if ij then begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
C语言代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#includestdio.h
#includestdlib.h
#includeiostream.h
#defineMAX_VERTEX_NUM20
#defineOK1
#defineERROR0
#defineMAX1000
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];//节点数组
AdjMatrixarcs;//邻接矩阵
intvexnum,arcnum;//图的当前节点数和弧数
}MGraph;
typedefstructPnode//用于普利姆算法
{
charadjvex;//节点
doublelowcost;//权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
charch1;//节点1
charch2;//节点2
doublevalue;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
//-------------------------------------------------------------------------------
intCreateUDG(MGraphG,Dgevaluedgevalue);
intLocateVex(MGraphG,charch);
intMinimum(MGraphG,Closedgeclosedge);
voidMiniSpanTree_PRIM(MGraphG,charu);
voidSortdge(Dgevaluedgevalue,MGraphG);
//-------------------------------------------------------------------------------
intCreateUDG(MGraphG,Dgevaluedgevalue)//构造无向加权图的邻接矩阵
{
inti,j,k;
cout"请输入图中节点个数和边/弧的条数：";
cinG.vexnumG.arcnum;
cout"请输入节点：";
for(i=0;iG.vexnum;++i)
cinG.vexs[i];
for(i=0;iG.vexnum;++i)//初始化数组
{
for(j=0;jG.vexnum;++j)
{
G.arcs[i][j].adj=MAX;
}
}
cout"请输入一条边依附的定点及边的权值："endl;
for(k=0;kG.arcnum;++k)
{
cindgevalue[k].ch1dgevalue[k].ch2dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1）;
j=LocateVex(G,dgevalue[k].ch2）;
G.arcs[i][j].adj=dgevalue[k].value;
G.arcs[j][i].adj=G.arcs[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)//确定节点ch在图G.vexs中的位置
{
inta;
for(inti=0;iG.vexnum;i++)
{
if(G.vexs[i]==ch)
a=i;
}
returna;
}
voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成树
{
inti,j,k;
Closedgeclosedge;
k=LocateVex(G,u);
for(j=0;jG.vexnum;j++)
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;iG.vexnum;i++)
{
k=Minimum(G,closedge);
cout"("closedge[k].adjvex","G.vexs[k]","closedge[k].lowcost")"endl;
closedge[k].lowcost=0;
for(j=0;jG.vexnum;++j)
{
if(G.arcs[k][j].adjclosedge[j].lowcost)
{
closedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)//求closedge中权值最小的边，并返回其顶点在vexs中的位置
{
inti,j;
doublek=1000;
for(i=0;iG.vexnum;i++)
{
if(closedge[i].lowcost!=0closedge[i].lowcostk)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidMiniSpanTree_KRSL(MGraphG,Dgevaluedgevalue)//克鲁斯卡尔算法求最小生成树
{
intp1,p2,i,j;
intbj[MAX_VERTEX_NUM];//标记数组
for(i=0;iG.vexnum;i++)//标记数组初始化
bj[i]=i;
Sortdge(dgevalue,G);//将所有权值按从小到大排序
for(i=0;iG.arcnum;i++)
{
p1=bj[LocateVex(G,dgevalue[i].ch1）];
p2=bj[LocateVex(G,dgevalue[i].ch2）];
if(p1!=p2）
{
cout"("dgevalue[i].ch1","dgevalue[i].ch2","dgevalue[i].value")"endl;
for(j=0;jG.vexnum;j++)
{
if(bj[j]==p2）
bj[j]=p1;
}
}
}
}
voidSortdge(Dgevaluedgevalue,MGraphG)//对dgevalue中各元素按权值按从小到大排序
{
inti,j;
doubletemp;
charch1,ch2;
for(i=0;iG.arcnum;i++)
{
for(j=i;jG.arcnum;j++)
{
if(dgevalue[i].valuedgevalue[j].value)
{
temp=dgevalue[i].value;
dgevalue[i].value=dgevalue[j].value;
dgevalue[j].value=temp;
ch1=dgevalue[i].ch1;
dgevalue[i].ch1=dgevalue[j].ch1;
dgevalue[j].ch1=ch1;
ch2=dgevalue[i].ch2;
dgevalue[i].ch2=dgevalue[j].ch2;
dgevalue[j].ch2=ch2;
}
}
}
}
voidmain()
{
inti,j;
MGraphG;
charu;
Dgevaluedgevalue;
CreateUDG(G,dgevalue);
cout"图的邻接矩阵为："endl;
for(i=0;iG.vexnum;i++)
{
for(j=0;jG.vexnum;j++)
coutG.arcs[i][j].adj"";
coutendl;
}
cout"=============普利姆算法===============\n";
cout"请输入起始点：";
cinu;
cout"构成最小代价生成树的边集为：\n";
MiniSpanTree_PRIM(G,u);
cout"============克鲁斯科尔算法=============\n";
cout"构成最小代价生成树的边集为：\n";
MiniSpanTree_KRSL(G,dgevalue);
}
pascal算法
program didi;
var
a:array[0..100000] of record
s,t,len:longint;
end;
fa,r:array[0..10000] of longint;
n,i,j,x,y,z:longint;
tot,ans:longint;
count,xx:longint;
procedure quick(l,r:longint);
var
i,j,x,y,t:longint;
begin
i:=l;j:=r;
x:=a[(l+r) div 2].len;
repeat
while xa[i].len do inc(i);
while xa[j].len do dec(j);
if i=j then
begin
y:=a[i].len;a[i].len:=a[j].len;a[j].len:=y;
y:=a[i].s;a[i].s:=a[j].s;a[j].s:=y;
y:=a[i].t;a[i].t:=a[j].t;a[j].t:=y;
inc(i);dec(j);
end;
until ij;
if ir then quick(i,r);
if lj then quick(l,j);
end;
function find(x:longint):longint;
begin
if fa[x]x then fa[x]:=find(fa[x]);
find:=fa[x];
end;
procedure union(x,y:longint);{启发式合并}
var
t:longint;
begin
x:=find(x);
y:=find(y);
if r[x]r[y] then
begin
t:=x;x:=y;y:=t;
end;
if r[x]=r[y] then inc(r[x]);
fa[x]:=y;
end;
begin
readln(xx,n);
for i:=1 to xx do fa[i]:=i;
for i:=1 to n do
begin
read(x,y,z);
inc(tot);
a[tot].s:=x;
a[tot].t:=y;
a[tot].len:=z;
end;
quick（1,tot);{将边排序}
ans:=0;
count:=0;
i:=0;
while count=x-1 do{count记录加边的总数}
begin
inc(i);
with a[i] do
if find(s)find(t) then
begin
union(s,t);
ans:=ans+len;
inc(count);
end;
end;
write(ans);
end.
Prim
var
m,n:set of 1..100;
s,t,min,x,y,i,j,k,l,sum,p,ii:longint;
a:array[1..100,1..100]of longint;
begin
readln(p);
for ii:=1 to p do
begin
k:=0; sum:=0;
fillchar(a,sizeof(a),255);
readln(x);
m:=[1];
n:=[2..x];
for i:=1 to x do
begin
for j:=1 to x do
begin
read(a[i,j]);
if a[i,j]=0
then a[i,j]:=maxlongint;
end;
readln;
end;
for l:=1 to x-1 do
begin
min:=maxlongint;
for i:=1 to x do
if i in m
then begin
for j:=1 to x do
begin
if (a[i,j]min)and(j in n)
then begin
min:=a[i,j];
s:=i;
t:=j;
end;
end;
end;
sum:=sum+min;
m:=m+[t];
n:=n-[t];
inc(k);
end;
writeln(sum);
end;
end.
数据结构算法 试题 急！ 试构造下图的最小生成树，要求分步给出构造过程。
图 有如下参数:
边数=8 顶点数=5
顶点 顶点 边的权值
v1 v2 6
v1 v3 4
v1 v4 2
v2 v3 5
v2 v4 8
v2 v5 6
v3 v4 5
v4 v5 7
用Kruskal(克鲁斯卡尔)算法,求最小生成树.
先将所有边的权值按照从小到大排序:
顶点 顶点 边的权值
v1 v4 2
v1 v3 4
v2 v3 5
v3 v4 5
v1 v2 6
v2 v5 6
v4 v5 7
v2 v4 8
然后,每次提取权值最小边,逐步组成最小生成树:
(1) 取最小边(v1, v4, 2)
v1 -- v4
(2) 取边(v1, v3, 4),不会产生环路.
v1 -- v4
|
|
v3
(3) 取边(v2, v3, 5),不会产生环路.
v1 -- v4
|
|
v3 -- v2
(4) 如果取边(v3, v4, 5),会产生环路,所以不能取.
如果取边(v1, v2, 6),会产生环路,所以不能取.
取边(v2, v5, 6),不会产生环路.
v1 -- v4
|
|
v3 -- v2 -- v5
这就是最小生成树,连通了所有顶点,总权值最小.
顶点 边的权值
(v1, v4) 2
(v1, v3) 4
(v2, v3) 5
(v2, v5) 6
// C语言测试程序
// 最小生成树 Kruskal(克鲁斯卡尔)算法
#include "stdio.h"
#define MAXEDGE 20
#define MAXVEX 20
#define INF 65535
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef struct
{
int begin;
int end;
int weight;
}Edge; //对边集数组Edge结构的定义
//创建图
void CreateMGraph(MGraph *G)
{
int i, j;
G-numEdges=8; //边数
G-numVertexes=5; //顶点数
for (i = 0; i G-numVertexes; i++)//初始化图
{
for ( j = 0; j G-numVertexes; j++)
{
if (i==j)
G-arc[i][j]=0;
else
G-arc[i][j] = G-arc[j][i] = INF;
}
}
G-arc[0][1]=6;
G-arc[0][2]=4;
G-arc[0][3]=2;
G-arc[1][2]=5;
G-arc[1][3]=8;
G-arc[1][4]=6;
G-arc[2][3]=5;
G-arc[3][4]=7;
for(i = 0; i G-numVertexes; i++)
{
for(j = i; j G-numVertexes; j++)
{
G-arc[j][i] =G-arc[i][j];
}
}
}
//交换权值 以及头和尾
void Swapn(Edge *edges,int i, int j)
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
//对权值进行排序 (选择排序法)
void sort(Edge edges[],MGraph *G)
{
int i,j,min;
for ( i = 0; i (G-numEdges-1); i++)
{
min=i;
for ( j = i + 1; j G-numEdges; j++)
{
if (edges[min].weight edges[j].weight)
{
min=j;
}
}
if(i != min)
{
Swapn(edges, i, min);
}
}
printf("边的权值排序之后:\n");
for (i = 0; i G-numEdges; i++)
{
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
//查找连线顶点的尾部下标
int Find(int *parent, int f)
{
while ( parent[f] 0)
{
f = parent[f];
}
return f;
}
//生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
{
int i, j, n, m;
int k = 0;
int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环路
Edge edges[MAXEDGE]; //定义边集数组,edge的结构为begin,end,weight,均为整型
//用来构建边集数组并排序
for ( i = 0; i G.numVertexes-1; i++)
{
for (j = i + 1; j G.numVertexes; j++)
{
if (G.arc[i][j]INF)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
sort(edges, G); //从小到大排序
for (i = 0; i G.numVertexes; i++)
{
parent[i] = 0;
}
printf("打印最小生成树：\n");
for (i = 0; i G.numEdges; i++) //循环每一条边
{
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
if (n != m) //假如n与m不等，说明此边没有与现有的生成树形成环路
{
parent[n] = m; //将此边的结尾顶点放入下标为起点的parent中
//表示此顶点已经在生成树集合中
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int main(void)
{
MGraph G;
CreateMGraph(G);
MiniSpanTree_Kruskal(G);
return 0;
}
