fsofgragh.java~22~

图论中关于简单无向图的深度

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */
import java.awt.*;
import java.awt.event.*;
public class FSofGragh extends Frame implements ActionListener{
  public static void main(String args[]){
          FSofGragh fSofGragh=new FSofGragh();
          fSofGragh.show();
      }

      java.util.Vector vector;
      java.util.Vector colorVector;

      Graph graph;

      private Menu helpMenu;               //帮助菜单
      private Menu algoMenu;               //算法
      private Menu drawMenu;               //画图
      private Menu exitMenu;               //退出

      private Node node[];
      private int c_id;
      private Button btn1,btn2,btn3;
      private int count=-1;
      private boolean drawNode=false;
      private boolean drawEdge=false;
      private boolean autoGenerated;

      private InputBox input;
      private TextArea info;
     // private ListBox listbox;

       AboutDialog about;
       HelpDialog  help;

      private int nodeColor[];
      private int pi[];
      private int d[];
      private int f[];
      private int time;

      public FSofGragh() {
          setTitle("图算法深度优先和广度优先：");
          setSize(800,600);
          setResizable(false);
          setBackground(Color.white);
          addWindowListener(new exit_1());
          MouseKeeper k=new MouseKeeper();
          addMouseListener(k);
          addMouseMotionListener(k);
          input=new InputBox(this,"请输入起点");
          info=new TextArea();
          info.setBounds(20,500,120,250);
          //add(info);
       //   listbox=new ListBox(this,"选择最小生成树算法");
     //     listbox.addItem("Kruskal算法");
      //    listbox.addItem("Prim算法");
          about=new AboutDialog(this);
          help=new HelpDialog(this);

          createHelpMenu();
          createAlgoMenu();
          createDrawMenu();
          createExitMenu();

          MenuBar menubar = new MenuBar();
          setMenuBar(menubar);
          menubar.add(drawMenu);
          menubar.add(algoMenu);
          menubar.add(helpMenu);
          menubar.add(exitMenu);

          vector=new java.util.Vector();
          colorVector=new java.util.Vector();

          setLayout(null);
          btn1=new Button("画点");
          btn2=new Button("画边");
          btn3=new Button("清除");
          btn1.setBounds(700,100,60,30);
          btn2.setBounds(700,150,60,30);
          btn3.setBounds(700,200,60,30);

          btn1.addActionListener(this);
          btn2.addActionListener(this);
          btn3.addActionListener(this);

          add(btn1);
          add(btn2);
          add(btn3);

          nodeColor = new int[100];
          pi = new int[100];
          d = new int[100];
          f = new int[100];


          node=new Node[400];
          for(int i=0;i<20;i++){
              for(int j=0;j<20;j++){
                  node[i*20+j]=new Node(i*20+j,(int)(j*30)+50,(int)(i*30)+60);
              }
          }
         /*
          Graphics g =getGraphics();
          g.setColor(Color.red);
          g.drawLine(30,40,450,40);
          g.drawLine(30,40,30,450);
                    g.drawLine(30,450,450,40);
          g.drawLine(450,450,450,40);
         */
          repaint();
      }
      private void createAlgoMenu() {
                MenuItem item;
               algoMenu = new Menu("算法");
               item = new MenuItem("BFS");
               item.addActionListener(this);
               algoMenu.add(item);

               item = new MenuItem("DFS");
               item.addActionListener(this);
               algoMenu.add(item);

           //    item = new MenuItem("Kruskal");
          //     item.addActionListener(this);
          //     algoMenu.add(item);

          //     item = new MenuItem("Prim");
          //     item.addActionListener(this);
          //     algoMenu.add(item);

           }

           private void createDrawMenu() {
                MenuItem item;

               drawMenu = new Menu("画图");
               item = new MenuItem("画点");
               item.addActionListener(this);
               drawMenu.add(item);

               item = new MenuItem("画边");
               item.addActionListener(this);
               drawMenu.add(item);

          //     item = new MenuItem("随机生成图");
           //    item.addActionListener(this);
           //    drawMenu.add(item);

               item = new MenuItem("清除");
               item.addActionListener(this);
               drawMenu.add(item);

           }

           private void  createHelpMenu() {
                MenuItem item;
               helpMenu = new Menu("帮助");
               item = new MenuItem("关于");
               item.addActionListener(this);
               helpMenu.add(item);

               item = new MenuItem("如何使用");
               item.addActionListener(this);
               helpMenu.add(item);



           }
           private void createExitMenu() {
                MenuItem item;
               exitMenu = new Menu("退出系统");
               item = new MenuItem("退出");
               item.addActionListener(this);
               exitMenu.add(item);

           }



      public void setNodeColor(int seq,int c) {//改变点的颜色
          Graphics g =getGraphics();
               Clock clock = new Clock();
               int nodeid;
               nodeid=searchId(seq);
                          if (c==2) {//变为灰色
                               g.setColor(Color.gray);
                             node[nodeid].fill(g);
                     } else if (c==3) {//变为黑色
                        g.setColor(Color.black);
                             node[nodeid].fill(g);
           }
           clock.pause(0.7);
      }
      public void BFS(Graph G,int s) {
           drawNode=false;
           drawEdge=false;

                      int i;
                     for(i=0;i<G.numVertices;i++) {
                                     nodeColor[i]=1;
                                     d[i]=Integer.MAX_VALUE;
                                     pi[i]=-1;
                          }
                          //System.out.println("BFS running....");

                          nodeColor[s]=2;
// /////////////////////////         setNodeColor(s,2);
                          colorVector.addElement(new ColorNode(s,2));
                          Queue Q = new Queue();
                          Q.ENQUEUE(s);
                          while (!Q.isEmpty()) {
                                          i=Q.DEQUEUE();
                                          EdgeNode p=G.AdjList[i].firstedge;
                                          while(p!=null) {
                                                          if(nodeColor[p.adjvex]==1) {
                                                                          nodeColor[p.adjvex]=2;
                                                                          setNodeColor(p.adjvex,2);
                                                                          d[p.adjvex]=d[i]+1;
                                                                          pi[p.adjvex]=i;
                                                                          Q.ENQUEUE(p.adjvex);
                                                          }
                                                p=p.next;
                                          }
                                          nodeColor[i]=3;
   /////////////////////////////////     setNodeColor(i,3);
                                         colorVector.addElement(new ColorNode(i,3));

                          }
                          //System.out.println("BFS DONE....");

           }
           public void DFS(Graph G) {
           drawNode=false;
           drawEdge=false;

                           int i;
                          for(i=0;i<G.numVertices;i++) {
                                     nodeColor[i]=1;
                                     f[i]=Integer.MAX_VALUE;
                                     d[i]=Integer.MAX_VALUE;

                                     pi[i]=-1;
                          }
                          time=0;
                          for(i=0;i<G.numVertices;i++) {
                                          if(nodeColor[i]==1) {
                                                          DFS_VISIT(G,i);
                                          }
                          }
           }
           public void DFS_VISIT(Graph G,int u) {
                            nodeColor[u]=2;
                           setNodeColor(u,2);
                           time = time + 1;
                           d[u]=time;
                           EdgeNode p =G.AdjList[u].firstedge;
                           while(p!=null) {
                                           if(nodeColor[p.adjvex]==1) {
                                                           pi[p.adjvex]=u;
                                                          DFS_VISIT(G,p.adjvex);
                                          }
                                          p=p.next;
                          }
                          nodeColor[u]=3;
                          setNodeColor(u,3);
                          f[u]=time=time+1;
           }


      private Image image=null;

      public void paint(Graphics g){
          if(image==null)
              image=createImage(800,630);
          if(image!=null)
              g.drawImage(image,0,0,this);
      }

      public int choose(int x,int y){
          int m=0;
          while (m<400){
              if(node[m].check(x,y))return m;
              m++;
          }
          return 9999;
      }

      public void actionPerformed(java.awt.event.ActionEvent e) {
          String lab=e.getActionCommand();
          if (lab.equals("画点")){
              if(autoGenerated)resetAll();
              drawNode=true;
              drawEdge=false;
              autoGenerated=false;
          }
          else if(lab.equals("画边")){
              if(autoGenerated)resetAll();
              drawEdge=true;
              drawNode=false;
              autoGenerated=false;
          }
     /*      else if(lab.equals("随机生成图")){
              resetAll();
              graph=createRandomGraph();
              //graph.printGraph();
              depictGraph(graph);
              autoGenerated=true;
          }
        else if(lab.equals("最小生成树")){
                          //System.out.println("MST    shdfhjsfjkj");

              if(!autoGenerated){
                  //System.out.println("MST1    shdfhjsfjkj");

                  graph=new Graph(count+1);
                  //System.out.println("MST2    shdfhjsfjkj");

                  Edge temp=new Edge();
                  //System.out.println("MST3   shdfhjsfjkj");
                  for(int i=0;i<vector.size();i++){
                      temp=(Edge)vector.elementAt(i);
                      graph.addEdge(temp.head,temp.tail,temp.weight);
                  }
              }
              Edge[] result=new Edge[graph.numVertices-1];
              int choose=listbox.getSelectedIndex();
              if(choose==0){
                  result=graph.Kruskal();
              }else if(choose==1){
                  result=graph.Prim();
              }else{
                  info.setText("Error!");
              }            printResult(result,graph.numVertices-1);
          }
          else if(lab.equals("Kruskal")){
              if(!autoGenerated){
                  graph=new Graph(count+1);
                  Edge temp=new Edge();
                  for(int i=0;i<vector.size();i++){
                      temp=(Edge)vector.elementAt(i);
                      graph.addEdge(temp.head,temp.tail,temp.weight);
                  }
              }
              Edge[] result=new Edge[graph.numVertices-1];
              result=graph.Kruskal();
              printResult(result,graph.numVertices-1);
          }
          else if(lab.equals("Prim")){
              if(!autoGenerated){
                  graph=new Graph(count+1);
                  Edge temp=new Edge();
                  for(int i=0;i<vector.size();i++){
                      temp=(Edge)vector.elementAt(i);
                      graph.addEdge(temp.head,temp.tail,temp.weight);
                  }
              }


              Edge[] result=new Edge[graph.numVertices-1];
              result=graph.Prim();
              printResult(result,graph.numVertices-1);
          }*/
          else if(lab.equals("BFS")){
  //               System.out.println("BFS    shdfhjsfjkj");
                 if(!autoGenerated){
                  graph=new Graph(count+1);
                  Edge temp=new Edge();
                  for(int i=0;i<vector.size();i++){
                      temp=(Edge)vector.elementAt(i);
                      graph.addEdge(temp.head,temp.tail,temp.weight);
                   }
                 }
        //         System.out.println("BFS1    shdfhjsfjkj");
                   int s=0;
                   input.setLocation(700,400);

                   s=input.getInteger("Input Source Vertex");