graph.java

本软件是使用java 开发的

package datastructure;

import java.awt.*;
import java.awt.event.*;
import java.math.*;
import javax.swing.*;

public class Graph
    extends Panel
    implements Runnable, ActionListener {
  private Thread runner;

  private boolean runFlag = false;
  static JButton newButton;
  static JButton runButton;
  static JButton stepButton;
  static JButton stayButton;
  TextArea record;
  //控制演示速度
  private GlobalControls controlsPanel = new GlobalControls();
  private int controls;
  CodeAnimationPanel codePanel;
  Panel panel;
  Panel eastPanel;
  JTextField textfield00;
  JTextField textfield01;
  JTextField textfield10;
  JTextField textfield11;
  JTextField textfield20;
  JTextField textfield21;
  JTextField textfield30;
  JTextField textfield31;
  JTextField textfield40;
  JTextField textfield41;
  private int count;
  private int codePart = 1;
  private int subCodePart = 8;
  int drawMode = 4;
  int arrayPointer = 0;
  int visitPointer = 0;
  int graphArray[][] = new int[12][12];
  boolean visited[] = new boolean[12];
  int vertexnum = 8;

  Label note = new Label();
  private boolean doneFlag = false;
  boolean expFlag = true;
  String notecon = new String();
  boolean switchflag = false;
  int subcodePart = 1;
  private vertex[] vertexList = new vertex[12];
  GraphStack theStack = new GraphStack(); //
  private int startingVertex = 0;
  private int displayVertex;
  private byte visitIndex = 0;
  private char[] visitArray = new char[12];
  private String visitdshow = new String();
  int w;
  public Graph() {
    System.out.println("kdsflk");
    this.init();

  }

  public void init() {
    this.graphArray[0][1] = 1;
    this.graphArray[0][2] = 1;
    this.graphArray[3][4] = 1;
    this.graphArray[0][4] = 1;
    this.graphArray[3][5] = 1;
    this.makeVertex();
    String as[] = {
        "  void DFSTraverse(Graph G,Status(*Visit)(int v)){",
        "  visitFunc=visit;",
        "  for(v=0;v<G.vexnum;++v) visited[v]=FALSE;  ",
        "  for(v=0;v<G.vexnum;++v)",
        "   {  if(!visited[v])",
        "      DFS(G,v);}",
        "   }",
        "  void DFS(Graph G,int v)",
        "  {  visited[v]=TRUE; VistiFunc(v);",
        "     for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))",
        "       if(!visited[v])  DFS(G,w); ",
        "   }",
        "   }",
    };
    visitIndex = 0;
    this.setBackground(Color.lightGray);
    controlsPanel.delay = 900;
    codePanel = new CodeAnimationPanel(as);
    this.setLayout(new BorderLayout());
    note.setSize(200, 20);
    note.setLocation(20, 75);
    textfield00 = new JTextField("变量名");
    textfield01 = new JTextField("变量值");
    textfield10 = new JTextField("vernum");
    textfield11 = new JTextField("");
    textfield20 = new JTextField("v");
    textfield21 = new JTextField("");
    textfield30 = new JTextField("visited[v]");
    textfield31 = new JTextField("");
    textfield40 = new JTextField("w");
    textfield41 = new JTextField("");
    runFlag = false;
    eastPanel = new Panel();
    eastPanel.setLayout(new BorderLayout());
    panel = new Panel();
    panel.setLayout(new GridLayout(5, 2));
    panel.add(textfield00);
    panel.add(textfield01);
    panel.add(textfield10);
    panel.add(textfield11);
    panel.add(textfield20);
    panel.add(textfield21);
    panel.add(textfield30);
    panel.add(textfield31);
    panel.add(textfield40);
    panel.add(textfield41);
    textfield00.setEditable(false);
    textfield01.setEditable(false);
    textfield10.setEditable(false);
    textfield11.setEditable(false);
    textfield20.setEditable(false);
    textfield21.setEditable(false);
    textfield30.setEditable(false);
    textfield31.setEditable(false);
    textfield40.setEditable(false);
    textfield41.setEditable(false);
    eastPanel.add(codePanel, BorderLayout.NORTH);
    eastPanel.add(panel, BorderLayout.SOUTH);
    this.add(eastPanel, BorderLayout.EAST);

    newButton = new JButton("新 建");
    newButton.addActionListener(this);
    runButton = new JButton("运 行");
    runButton.addActionListener(this);

    stepButton = new JButton("单 步");
    stepButton.addActionListener(this);

    stayButton = new JButton("暂 停");
    stayButton.addActionListener(this);
    repaint();
  }

  public void makeVertex() {
    int i, j;
    for (int pos = 0; pos <= vertexnum; pos++) {

      i = 200 + (int) (100 * Math.cos(2 * 3.14 / vertexnum * pos));
      j = 200 + (int) (100 * Math.sin(2 * 3.14 / vertexnum * pos));
      vertexList[pos] = new vertex(i, j);
      vertexList[pos].label = (char) ('a' + pos);
    }
    drawMode = 4;
    return;

  }

  public void drawOneVertex(Graphics g, int i) {
    if (i < 0)
      return;
    Color color = vertexList[i].color;
    char c = vertexList[i].label;
    int j = vertexList[i].x - 15;
    int k = vertexList[i].y - 15;
    g.setColor(color);
    g.fillOval(j, k, 30, 30);
    g.setColor(Color.black);
    g.drawOval(j, k, 30, 30);
    if (vertexList[i].wasVisited) {
      g.setColor(Color.red);

    }
    g.setFont(new Font("Courier", Font.PLAIN, 18));
    g.drawString(String.valueOf(c), j + 10, k + 20);
  }

  private void drawEdge(Graphics g, int i, int j, int k) {
    int l = vertexList[i].x;
    int i1 = vertexList[i].y;
    int j1 = vertexList[j].x;
    int k1 = vertexList[j].y;
    g.drawLine(l, i1, j1, k1);
    if (k != 1) {
      g.drawLine(l + 1, i1, j1 + 1, k1);
      if ( (j1 - l > 0) != (k1 - i1 > 0)) {
        g.drawLine(l, i1 - 1, j1, k1 - 1);
        return;
      }
      g.drawLine(l, i1 + 1, j1, k1 + 1);
    }
  }

  public void draw(Graphics g) {

    switch (drawMode) {

      case 2:
        drawOneVertex(g, displayVertex);
        break;
      case 3:

        break;

      case 4:
        g.setColor(Color.lightGray);
        g.fillRect(0, 0, 440, 400);
        g.setColor(Color.black);

        for (int k = 0; k < vertexnum; k++) {
          for (int i1 = 0; i1 < vertexnum; i1++) {
            int j = graphArray[k][i1];
            if (j > 0)
              drawEdge(g, k, i1, j);
          }
        }
        for (int l = 0; l < vertexnum; l++)
          drawOneVertex(g, l);
        break;
    }
    g.setFont(new Font("Courier", Font.PLAIN, 18));
    g.setColor(Color.lightGray);
    this.visitdshow = "访问序列:";
    g.fillRect(10, 350, 400, 40);
    for (int i = 0; i < visitIndex; i++) {
      this.visitdshow += visitArray[i] + ",";
    }
    g.setColor(Color.black);
    g.drawString(this.visitdshow, 20, 350);
    drawMode = 4;
  }

  public void start() {
    if (runner == null) {
      runner = new Thread(this);
      runner.start();
    }
  }

  public void stop() {
    if (runner != null) {
      runner.yield();
      runner = null;
    }
  }

  public void paint(Graphics g) {
    draw(g);

  }

  public void update(Graphics g) {
    paint(g);
  }

  public void pramUpdate() {
    this.textfield11.setText(String.valueOf(this.vertexnum));
    this.textfield21.setText(String.valueOf(this.visitPointer));
    this.textfield31.setText(String.valueOf(vertexList[visitPointer].wasVisited));
    this.textfield41.setText(String.valueOf(String.valueOf(w)));

  }

  public void actionPerformed(ActionEvent actionevent) {

    if (actionevent.getSource() == newButton) {
      stop();
      this.switchflag = false;
      codePart = 1;
      codePanel.highlight(1);
      this.doneFlag = false;
      visitIndex = 0;
      GraphFrame.graphdata.setSize(600, 400);
      GraphFrame.graphdata.setVisible(true);
      this.graphArray = GraphFrame.graphdata.getArray();
      vertexnum = GraphFrame.graphdata.getVertexNum();
      makeVertex();
      {
        stepButton.setEnabled(true);
        runButton.setEnabled(true);
        stayButton.setEnabled(true);
      }
      codePart = 1;
      doneFlag = false;
    }

    if (actionevent.getSource() == stepButton) {
      runFlag = false;
      if (switchflag)
        dfs();
      else
        DFSTraverse(graphArray);
      if (doneFlag) {

        newButton.setEnabled(true);
        stepButton.setEnabled(false);
        stayButton.setEnabled(false);
        runButton.setEnabled(false);
        JOptionPane.showConfirmDialog(this,
                                      "    算法演示完成！\n  \n 单击相关按钮重新开始\n",
                                      "演示完成", JOptionPane.DEFAULT_OPTION);

      }
    }
    if (actionevent.getSource() == runButton) {
      try {
        this.start();
      }
      catch (Exception exp) {
        exp.toString();
      }
      runFlag = true;

    }
    if (actionevent.getSource() == stayButton) {
      runFlag = false;
    }
    repaint();
  }

  public void run() {
    while (Thread.currentThread() == this.runner) {

      if (runFlag) {
        if (doneFlag) { //判断是否运行结束
          newButton.setEnabled(true);
          stepButton.setEnabled(false);
          stayButton.setEnabled(false);
          runButton.setEnabled(false);
          runFlag = false;
          JOptionPane.showConfirmDialog(this,
                                        "    算法演示完成！\n  \n 单击相关按钮重新开始\n",
                                        "演示完成", JOptionPane.DEFAULT_OPTION);

          stop();
        }
        else {

          if (switchflag)
            dfs();
          else
            DFSTraverse(graphArray);
          pramUpdate();
          repaint();
          try {
            controls = controlsPanel.delay;
            Thread.sleep(controls);
          }
          catch (InterruptedException exp) {
            exp.toString();
          }
        }
      }
    }
  }

  public void DFSTraverse(int array[][]) {
    drawMode = 4;

    switch (codePart) {
      case 1:
        arrayPointer = 0;
        visitPointer = 0;
        codePanel.highlight(1);
        codePart = 2;
        return;
      case 2:
        codePanel.highlight(2);
        codePart = 3;
        return;
      case 3:
        if (this.arrayPointer < vertexnum) {
          vertexList[arrayPointer].wasVisited = false;
          codePart = 3;
          arrayPointer++;
          codePanel.highlight(3);
          return;
        }
        else {
          codePart = 4;
          codePanel.highlight(3);
          return;
        }
      case 4:
        if (visitPointer < vertexnum) {
          codePart = 5;
        }
        else {
          codePart = 7;
        }
        codePanel.highlight(4);
        return;
      case 5:
        if (vertexList[visitPointer].wasVisited == false) {
          codePart = 6;
        }
        else {
          visitPointer++;
          codePart = 4;
        }

        codePanel.highlight(5);
        return;
      case 6:
        codePanel.highlight(6);
        switchflag = true;

        subcodePart = 1;
        startingVertex = visitPointer;
        return;
      case 7:
        this.doneFlag = true;

        codePanel.highlight(7);
        return;
    }
  }

  public void dfs() {

    switch (subcodePart) {
      case 1:
        drawMode = 3;
        subcodePart = 2;
        return;

      case 2:

        // note = "Starting search from vertex " + vertexList[startingVertex].label;
        for (; !theStack.isEmpty(); theStack.pop())
          ;
        vertexList[startingVertex].wasVisited = true;
        visitArray[visitIndex++] = vertexList[startingVertex].label;

        theStack.push(startingVertex);
        subcodePart = 23;

        displayVertex = startingVertex;
        drawMode = 3;
        return;
      case 23:
        codePanel.highlight(9);
        subcodePart = 3;
        return;
      case 3:
        if (!theStack.isEmpty()) {
          subcodePart = 31;
          codePanel.highlight(10);
          return;

        }
        else {
          subcodePart = 32;
          codePanel.highlight(11);
          return;
        }
      case 31:
        codePanel.highlight(10);
        int i = getAdjUnvisitedVertex(theStack.peek());
        w = i;
        if (i == -1) {
          theStack.pop();
          subcodePart = 3;
          return;
        }
        else {
          subcodePart = 311;
          return;
        }

      case 311: //  note = "Visited vertex " + vertexList[i].label;

        vertexList[w].wasVisited = true;
        visitArray[visitIndex++] = vertexList[w].label;
        theStack.push(w);
        codePanel.highlight(11);
        displayVertex = w;
        drawMode = 2;
        subcodePart = 23;

        return;
      case 32:
        subcodePart = 4;
        drawMode = 1;
        return;

      case 4:
        subcodePart = 1;
        this.switchflag = false;
        visitPointer++;
        codePart = 4;
        drawMode = 4;
        return;
    }
  }

  public int getAdjUnvisitedVertex(int i) {
    for (int j = 0; j < vertexnum; j++)
      if (this.graphArray[i][j] == 1 && !vertexList[j].wasVisited)
        return j;

    return -1;
  }

}