本文目录一览：
- 无向图最短主树生成程序 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() {
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[0][0];
} else {
bw = params1[1][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[2][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[2][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': {
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();
}
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.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);
}
java 最小生成树
public class AbstractGraphV {
public AbstractGraphV(List<? extends Edge> edges, List<V> vertices) {
}
public static class Edge {
}
}
public class WeightedGraph extends AbstractGraph<Float> {
public WeightedGraph(List<WeightedEdge> edges, List<Float> vertices) {
super(edges, vertices);
}
public static class WeightedEdge extends Edge {
}
}
试试这种？
图的最小生成树算法？
图的生成树和最小生成树生成树(SpanningTree):如果一个图的子图是一个包含图所有节点的树,那这个子图就称为生成树。
求出如图二所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权．
① 将带权连通图 G = n, m 的各边按权从小到大依次排列，如 e₁, e₂, ..., eₘ，其中 e₁ 的权最小，eₘ 的权最大，m 为边数。 ② 取权最小的两条边构成边集 T₀，即 T₀ = {e₁, e₂}，从 e₃ 起，按次序逐个将各边加进集合 T₀ 中去，若出现回路则将这条边排除（不加进去），按此法一直进行到 eₘ，最后得到 n-1 条边的集合 T₀ = {e₁, e₂, ..., eₙ₋₁}，则 T₀ 导出的子图就是图 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[i]) 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] := [i]; { 初始化定义 n 个集合，第 i 个集合包含一个元素 i }
p := n-1; q := 1; tot := 0; { p 为尚待加入的边数，q 为边集指针 }
sort; { 对所有边按权值递增排序，存于 e 中 }
while p > 0 do begin
i := find(e[q].v1);
j := find(e[q].v2);
if i <> j then begin
inc(tot, e[q].len);
vset[i] := vset[i] + vset[j];
vset[j] := [];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;
C语言代码
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define MAX 1000
typedef struct Arcell {
double adj;
} Arcell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 节点数组
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的当前节点数和弧数
} MGraph;
typedef struct Pnode // 用于普利姆算法
{
char adjvex; // 节点
double lowcost; // 权值
} Pnode, Closedge[MAX_VERTEX_NUM]; // 记录顶点集 U 到 V-U 的代价最小的边的辅助数组定义
typedef struct Knode // 用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
char ch1; // 节点1
char ch2; // 节点2
double value; // 权值
} Knode, Dgevalue[MAX_VERTEX_NUM];
int CreateUDG(MGraph *G, Dgevalue edgevalue);
int LocateVex(MGraph G, char ch);
int Minimum(MGraph G, Closedge closedge);
void MiniSpanTree_PRIM(MGraph G, char u);
void Sortdge(Dgevalue edgevalue,
