mstvisual.java

最小生成树的算法演示

package color;

import javax.swing.*;
import javax.swing.event.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.io.*;
import java.io.IOException;

class Edge {

  public Edge(String sNode, String eNode, int weight) {
    this.sNode = sNode;
    this.eNode = eNode;
    this.weight = weight;
  }

  public Edge() {}

  String sNode;
  String eNode;
  int weight;
}

public class MSTVisual
    extends JPanel
    implements Runnable {
  public MSTVisual() {

    this.setLayout(null);
    process.setBounds(650, 500, 100, 30);

    process.addActionListener(new ActionListener() {
      public void actionPerformed(ActionEvent event) {
        //按钮的事件处理，当点击时演示生成MST的处理过程
        findMSTEdge = true;
        MST_Process();
        start();
        repaint();
      }
    }
    );

    process.addKeyListener(key);
    this.add(process);
    this.addMouseListener(mouse);
    this.addMouseMotionListener(mouseM);

    this.setBackground(Color.white);

  }

  //演示线程的开始
  public void start() {
    iD = -1;
    main_thread = new Thread(this);
    main_thread.start();
  }

  //演示线程的结束
  public void stop() {
    iD = -1;
    main_thread = null;
  }

  public void run() {
    while (Thread.currentThread() == main_thread) {
      repaint();
      try {
        //延时后继续选择下一条边
        Thread.sleep(1500);
        iD++;
      }
      catch (InterruptedException e) {
        break;
      }
    }
  }

  //MST生成算法
  public void MST_Process() {
    Vector set = new Vector();

    paintResult = false;
    repaint();

    sMSTEdgeV.clear();
    eMSTEdgeV.clear();
    isSelect.clear();
    MST.clear();
    edge.clear();

    for (int i = 0; i < nodeName.size(); i++) {
      Make_set(set, (String) nodeName.get(i));
    }
    /*
         for (int i = 0; i < set.size(); i++) {
      for (int j = 0; j < ( (Vector) set.get(i)).size(); j++) {
        String s = (String) ( ( (Vector) set.get(i)).get(j));
        System.out.println("set " + i + " :  " + s);
      }
         }*/
    for (int i = 0; i < startNode.size() && i < endNode.size(); i++) {
      String s = (String) nodeName.get( ( (Integer) startNode.get(i)).intValue());
      String e = (String) nodeName.get( ( (Integer) endNode.get(i)).intValue());
      int w = ( (Integer) weight.get(i)).intValue();
      edge.add(new Edge(s, e, w));
    }

    Insert_sort(edge);

    /*System.out.println("After sort: ");
         for (int i = 0; i < edge.size(); i++) {
      String s = ( (Edge) edge.get(i)).sNode;
      String e = ( (Edge) edge.get(i)).eNode;
      int w = ( (Edge) edge.get(i)).weight;
      System.out.println("sNode: " + s + "  eNode: " + e + "  weight: " + w);
         }*/

    for (int i = 0; i < edge.size(); i++) {

      String s = ( (Edge) edge.get(i)).sNode;
      String e = ( (Edge) edge.get(i)).eNode;

      int m = Find_set(set, s);
      int n = Find_set(set, e);

      sMSTEdge = nodeName.indexOf(s);
      eMSTEdge = nodeName.indexOf(e);

      sMSTEdgeV.add(new Integer(sMSTEdge));
      eMSTEdgeV.add(new Integer(eMSTEdge));

      nodeName.indexOf(e);
      if (m != n) {
        findMSTEdge = true;
        isSelect.add(new Boolean(true));
        MST.add( (Edge) edge.get(i));
        Union(set, m, n);
      }
      else {
        isSelect.add(new Boolean(false));
      }
    }
    //打印最终的MST
    System.out.println("The mst is: ");
    for (int i = 0; i < MST.size(); i++) {
      String s = ( (Edge) MST.get(i)).sNode;
      String e = ( (Edge) MST.get(i)).eNode;
      int w = ( (Edge) MST.get(i)).weight;

      System.out.println("sNode: " + s + "  eNode: " + e + "  weight: " + w);
    }
  }

  //对各边以权重的大小排序
  public void Insert_sort(Vector array) {
    int i, j;
    Edge key = new Edge();
    for (j = 1; j < array.size(); j++) {

      key.sNode = ( (Edge) array.get(j)).sNode;
      key.eNode = ( (Edge) array.get(j)).eNode;
      key.weight = ( (Edge) array.get(j)).weight;

      i = j - 1;
      while (i >= 0 && ( (Edge) array.get(i)).weight > key.weight) {
        ( (Edge) array.get(i + 1)).sNode = ( (Edge) array.get(i)).sNode;
        ( (Edge) array.get(i + 1)).eNode = ( (Edge) array.get(i)).eNode;
        ( (Edge) array.get(i + 1)).weight = ( (Edge) array.get(i)).weight;
        i = i - 1;
      }
      ( (Edge) array.get(i + 1)).sNode = key.sNode;
      ( (Edge) array.get(i + 1)).eNode = key.eNode;
      ( (Edge) array.get(i + 1)).weight = key.weight;
    }
  }

  //将各个结点划分到不同的集合
  public void Make_set(Vector set, String v) {
    Vector temp = new Vector();
    temp.add(v);
    set.add(temp);
  }

  //寻找结点V属于哪一个集合，并将集合下标返回
  public int Find_set(Vector set, String v) {
    for (int i = 0; i < set.size(); i++) {
      for (int j = 0; j < ( (Vector) set.get(i)).size(); j++) {
        if ( ( (Vector) set.get(i)).get(j) == v) {
          return i;
        }
      }
    }
    return -1;
  }

  //将两个属于不同集合的结点连接起来
  public void Union(Vector set, int m, int n) {
    for (int i = 0; i < ( (Vector) set.get(n)).size(); i++) {
      ( (Vector) set.get(m)).add( ( (Vector) set.get(n)).get(i));
    }
    set.remove(n);
  }

  //得到两个结点的连接位置
  int[] getPaintPosition(int x1, int y1, int x2, int y2) {
    int[] position = {
        x1, y1 + 15, x2, y2 + 15};
    if (x2 > x1 + 60) {
      position[0] = x1 + 30;
      position[1] = y1 + 15;
    }
    else if (x1 > x2 + 60) {
      position[2] = x2 + 30;
      position[3] = y2 + 15;
    }
    else if (x2 <= x1 + 60 || x1 <= x2 + 60) {
      if (y1 < y2) {
        position[0] = x1 + 15;
        position[1] = y1 + 30;
        position[2] = x2 + 15;
        position[3] = y2;
      }
      else {
        position[0] = x1 + 15;
        position[1] = y1;
        position[2] = x2 + 15;
        position[3] = y2 + 30;
      }
    }
    return position;
  }

  //画图函数
  public void paintComponent(Graphics g) {
    super.paintComponent(g);

    //对图中颜色的提示
    g.setColor(Color.black);
    g.drawLine(10, 10, 30, 10);
    g.drawString("图中原有边", 35, 15);
    g.setColor(Color.blue);
    g.drawLine(10, 40, 30, 40);
    g.drawString("待选择边", 35, 45);
    g.setColor(Color.red);
    g.drawLine(10, 70, 30, 70);
    g.drawString("MST中边", 35, 75);

    if (drawNode == true) { //画出各个结点
      for (int i = 0; i < node.size(); i++) {
        g.setColor(Color.lightGray);
        g.fill3DRect( ( (Point) node.get(i)).x, ( (Point) node.get(i)).y, 30,
                     30, true);
        g.setColor(Color.black);
        g.drawString( (String) nodeName.get(i), ( (Point) node.get(i)).x + 12,
                     ( (Point) node.get(i)).y + 18);
      }
    }
    if (drawEdge == true) {
      //画出各个边
      g.setColor(Color.black);

      if (findEdge) {
        for (int i = 0; i < startNode.size() && i < endNode.size(); i++) {
          int[] p = getPaintPosition( ( (Point) node.get( ( (Integer) startNode.
              get(i)).intValue())).x,
                                     ( (Point) node.get( ( (Integer) startNode.
              get(i)).intValue())).y,
                                     ( (Point) node.get( ( (Integer) endNode.
              get(i)).intValue())).x,
                                     ( (Point) node.get( ( (Integer) endNode.
              get(i)).intValue())).y);
          g.drawLine(p[0], p[1], p[2], p[3]);
          if (i < weight.size()) {
            g.drawString(String.valueOf( ( (Integer) weight.get(i)).intValue()),
                         (p[0] + p[2]) / 2 + 5,
                         (p[1] + p[3]) / 2 + 5);
          }
        }
      }
      if (hasPre) {
        //如果有了开始结点，画出从开始结点到鼠标位置之间的直线
        g.setColor(Color.black);
        g.drawLine(preNode.x, preNode.y, currentMousePoint.x,
                   currentMousePoint.y);
      }
    }
    if (brighter == true) {
      //当鼠标经过一个结点时，高亮显示该结点
      g.setColor(Color.lightGray.brighter());
      g.fill3DRect( ( (Point) node.get(currentNodeIndex)).x,
                   ( (Point) node.get(currentNodeIndex)).y, 30,
                   30, true);
      g.setColor(Color.black);
      g.drawString( (String) nodeName.get(currentNodeIndex),
                   ( (Point) node.get(currentNodeIndex)).x + 12,
                   ( (Point) node.get(currentNodeIndex)).y + 18);
    }
    if (lineBrighter) {
      //当鼠标经过一条边时，高亮显示该边及对应的权重
      g.setColor(Color.green);
      int[] p = getPaintPosition( ( (Point) node.get( ( (Integer) startNode.
          get(currentLineIndex)).intValue())).x,
                                 ( (Point) node.get( ( (Integer) startNode.
          get(currentLineIndex)).intValue())).y,
                                 ( (Point) node.get( ( (Integer) endNode.
          get(currentLineIndex)).intValue())).x,
                                 ( (Point) node.get( ( (Integer) endNode.
          get(currentLineIndex)).intValue())).y);
      g.drawLine(p[0], p[1], p[2], p[3]);
      g.drawString(String.valueOf(weight.get(currentLineIndex)),
                   (p[0] + p[2]) / 2 + 5,
                   (p[1] + p[3]) / 2 + 5);
    }
    if (paintResult) {
      //当算法过程演示已经结束的时候，画出最终的MST
      g.setColor(Color.red);
      for (int i = 0; i < sMSTEdgeV.size() && i < eMSTEdgeV.size(); i++) {
        if ( ( (Boolean) isSelect.get(i)).booleanValue()) {
          int[] p = getPaintPosition( ( (Point) node.get( ( (Integer)
              sMSTEdgeV.
              get(i)).intValue())).x,
                                     ( (Point) node.get( ( (Integer)
              sMSTEdgeV.
              get(i)).intValue())).y,
                                     ( (Point) node.get( ( (Integer)
              eMSTEdgeV.
              get(i)).intValue())).x,
                                     ( (Point) node.get( ( (Integer)
              eMSTEdgeV.
              get(i)).intValue())).y);
          g.drawLine(p[0], p[1], p[2], p[3]);
        }
      }

    }
    if (findMSTEdge) {

      g.setColor(Color.red);
      if (iD < sMSTEdgeV.size() && iD < eMSTEdgeV.size()) {
        for (int i = 0; i < iD; i++) {
          if ( ( (Boolean) isSelect.get(i)).booleanValue()) {
            //对比当前边权重小的边，如果它是MST中的边，则画出
            int[] p = getPaintPosition( ( (Point) node.get( ( (Integer)
                sMSTEdgeV.
                get(i)).intValue())).x,
                                       ( (Point) node.get( ( (Integer)
                sMSTEdgeV.
                get(i)).intValue())).y,
                                       ( (Point) node.get( ( (Integer)
                eMSTEdgeV.
                get(i)).intValue())).x,
                                       ( (Point) node.get( ( (Integer)
                eMSTEdgeV.
                get(i)).intValue())).y);
            g.drawLine(p[0], p[1], p[2], p[3]);
          }
        }
        if (iD >= 0) {
          //画出当前正在选择边及对应的权重
          int[] p = getPaintPosition( ( (Point) node.get( ( (Integer) sMSTEdgeV.
              get(iD)).intValue())).x,
                                     ( (Point) node.get( ( (Integer) sMSTEdgeV.
              get(iD)).intValue())).y,
                                     ( (Point) node.get( ( (Integer) eMSTEdgeV.
              get(iD)).intValue())).x,
                                     ( (Point) node.get( ( (Integer) eMSTEdgeV.
              get(iD)).intValue())).y);
          g.setColor(Color.blue);
          g.drawLine(p[0], p[1], p[2], p[3]);
          g.drawString(String.valueOf( ( (Edge) edge.get(iD)).weight),
                       (p[0] + p[2]) / 2 + 5,
                       (p[1] + p[3]) / 2 + 5);
        }
      }
      else {
        findMSTEdge = false;
        paintResult = true;
        repaint();
        stop();
      }
    }
  }

  //boolean delete = false;
  class KeyDown