您的位置:

图的最小生成树java代码(最小生成树算法java实现)

本文目录一览:

无向图最短主树生成程序 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;

}