圖的最小生成樹java代碼（最小生成樹演算法java實現）

1、無向圖最短主樹生成程序 java
2、java 最小生成樹
3、圖的最小生成樹演算法？
4、求出如圖二所示賦權圖中的最小生成樹（要求寫出求解步驟），並求此最小生成樹的權．
5、最小生成樹怎麼求
6、數據結構演算法試題急！試構造下圖的最小生成樹，要求分步給出構造過程。

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” + ((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 –

+ “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(); }

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;

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語言代碼

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;

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;

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

(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;

}

原創文章，作者：CFRXX，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/126973.html

圖的最小生成樹java代碼（最小生成樹演算法java實現）

相關推薦

發表回復