package com.work8; import java.awt.Graphics; import java.awt.Graphics2D; import java.util.ArrayList; import javax.swing.JFrame; import javax.swing.JPanel; class MGraph{ //创建一个邻接矩阵的类; private static final int INFI=9999; private ArrayList VertexList; //图节点的储存点; private double[][] Edges; //图边的储存点; private int arcNum; //图边的数量储存容器; private int vexNum; //图的节点的数量的储存容器; private boolean[] info; public MGraph(int n){ //初始化邻接矩阵,矩阵的边和节点; VertexList=new ArrayList(n); Edges=new double[n][n]; info=new boolean[n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ Edges[i][j]=INFI; } } for(int i=0;i<n;i++){ info[i]=false; } arcNum=0; vexNum=0; } public void setVertex(int v){ //在列表的表尾增加一个元素; VertexList.add(v); } public int getVertex(int i){ if(VertexList.get(i)!=null){ return (int) VertexList.get(i); //返回i位置是否有点; } else{ return INFI; } } public int getVertexLocation(int v){ //已知点v的值,判断该点在图的位置; for(int i=0;VertexList.get(i)!=null;i++){ if((int)VertexList.get(i)==v){ return i; } } return INFI; } public void setinfo(int i){ //表示i位置的点是已经连接入网的,并将i位置的点的标记设为true; info[i]=true; } public boolean getinfo(int i){ //判断i位置的点是否已经连接入网,如果i位置的点已经连接入网了,则返回true,否则返回false; if(info[i]==true){ return true; } else{ return false; } } public void setArc(int x,int y ,double Distance){ //更改节点x和y之间的距离; Edges[x][y]=Distance; } public double getArc(int x,int y){ //输出x和y节点之间的距离; return Edges[x][y]; } public int GetVexNum(){ //返回图的节点数目; return VertexList.size(); } } class Node{ //节点的储存结构; private int x; private int y; public void setNode_x(int x){ this.x=x; } public void setNode_y(int y){ this.y=y; } public int GetNode_x(){ return x; } public int GetNode_y(){ return y; } } class SaveNode{ //建立一个特殊的数据结构,用于储存; Node[] save; public SaveNode(){ save=new Node[10000]; } public void setNode(Node[] node){ this.save=node; } public Node[] getNode(){ return save; } } class NodeConnect extends JPanel { public int k=0; private static final int Max=100; private static final int INFI=9999; public static final int step=10; Node[] Value=new Node[Max]; //存储需要接连入网的各个节点的位置; MGraph Graph=new MGraph(Max); //初始化路网; int[][] Graph_sort=new int [Max][Max]; //初始化路网,确定路网需要怎么连; SaveNode[] Save=new SaveNode[Max]; public NodeConnect(){ //利用构造函数方法,建立一个线程; new Thread(new Runnable(){ @Override public void run() { StartValue(); int i=1; while(i<11){ AddValue(i,i+1); i=i+2; repaint(); try { Thread.sleep(5000); } catch (InterruptedException e) { e.printStackTrace(); } } } }).start(); } public void StartValue(){ //初始化路网,作为路网仿真的初始值; Node Nanchang=new Node(); Nanchang.setNode_x(243); Nanchang.setNode_y(181); Node Jiujiang=new Node(); Jiujiang.setNode_x(260); Jiujiang.setNode_y(57); Node Xianning=new Node(); Xianning.setNode_x(81); Xianning.setNode_y(41); Node Jingdezhen=new Node(); Jingdezhen.setNode_x(360); Jingdezhen.setNode_y(140); Node Fuzhou=new Node(); Fuzhou.setNode_x(301); Fuzhou.setNode_y(272); Node Xinyu=new Node(); Xinyu.setNode_x(143); Xinyu.setNode_y(260); Node Yichun=new Node(); Yichun.setNode_x(90); Yichun.setNode_y(291); Node Pingxiang=new Node(); Pingxiang.setNode_x(23); Pingxiang.setNode_y(317); Node Yingtan=new Node(); Yingtan.setNode_x(374); Yingtan.setNode_y(232); Node Shangrao=new Node(); Shangrao.setNode_x(470); Shangrao.setNode_y(207); Node Ruichang=new Node(); Ruichang.setNode_x(220); Ruichang.setNode_y(60); Node Jian=new Node(); Jian.setNode_x(150); Jian.setNode_y(373); Node Wuyishan=new Node(); Wuyishan.setNode_x(478); Wuyishan.setNode_y(280); Value[0]=Nanchang; Value[1]=Jiujiang; Value[2]=Ruichang; Value[3]=Jingdezhen; Value[4]=Yingtan; Value[5]=Xinyu; Value[6]=Jian; Value[7]=Xianning; Value[8]=Yichun; Value[9]=Fuzhou; Value[10]=Pingxiang; Value[11]=Shangrao; Value[12]=Wuyishan; //初始化路网,整个路网当中只有合肥一个点,其余点慢慢加上去; Graph.setVertex(0); //在未连接的路网中加入合肥这个点; int logo=Graph.getVertexLocation(0); //得到0的位置; Graph.setinfo(logo); //set true表示0点已经连接入网; for(int i=1;i<Max;i++){ //合肥到任何点的距离都初始化为INFI; Graph.setArc(logo, i, INFI); } for(int i=0;i<Max;i++){ //将Graph_sort置0; for(int j=0;j<Max;j++){ Graph_sort[i][j]=0; } } } public void AddValue(int n1,int n2){ //加入未连接点的方法,随机加入两个点; Graph.setVertex(n1); //将n1点加入图中; int logo1=Graph.getVertexLocation(n1); //返回n1的坐标位置; Graph.setVertex(n2); //将n2加入图中; int logo2=Graph.getVertexLocation(n2); //返回n2的坐标位置; for(int i=0;Graph.getinfo(i);i++){ int temp=i; Graph.setArc(temp, logo1, Math.sqrt((Value[temp].GetNode_x()-Value[logo1].GetNode_x())*(Value[temp].GetNode_x()-Value[logo1].GetNode_x()) +(Value[temp].GetNode_y()-Value[logo1].GetNode_y())*(Value[temp].GetNode_y()-Value[logo1].GetNode_y()))); Graph.setArc(logo1, temp, Math.sqrt((Value[temp].GetNode_x()-Value[logo1].GetNode_x())*(Value[temp].GetNode_x()-Value[logo1].GetNode_x()) +(Value[temp].GetNode_y()-Value[logo1].GetNode_y())*(Value[temp].GetNode_y()-Value[logo1].GetNode_y()))); Graph.setArc(temp, logo2, Math.sqrt((Value[temp].GetNode_x()-Value[logo2].GetNode_x())*(Value[temp].GetNode_x()-Value[logo2].GetNode_x()) +(Value[temp].GetNode_y()-Value[logo2].GetNode_y())*(Value[temp].GetNode_y()-Value[logo2].GetNode_y()))); Graph.setArc(logo2, temp, Math.sqrt((Value[temp].GetNode_x()-Value[logo2].GetNode_x())*(Value[temp].GetNode_x()-Value[logo2].GetNode_x()) +(Value[temp].GetNode_y()-Value[logo2].GetNode_y())*(Value[temp].GetNode_y()-Value[logo2].GetNode_y()))); } double max=INFI; int k1=0,k2=0; for(int i=0;Graph.getinfo(i);i++){ if(Graph.getArc(i, logo1)<max){ max=Graph.getArc(i, logo1); k1=i; } } Graph_sort[k1][logo1]=1; for(int i=0;Graph.getinfo(i);i++){ if(Graph.getArc(i, logo2)<max){ max=Graph.getArc(i, logo2); k2=i; } } Graph_sort[k2][logo2]=1; Graph.setinfo(logo1); //将logo1和logo2 Graph.setinfo(logo2); //set true 加入路网; /////////////////////////////////////////////////////////////////////////// //根据Graph_sort的数组情况选择点的连接方式; for(int i=0;Graph.getinfo(i);i++){ if(Graph_sort[i][logo1]==1&&Graph_sort[i][logo2]==1){ Node[] save=new Node[10000]; ThreeNodeLine(Value[logo1],Value[logo2],Value[i],save); SaveNode savenode=new SaveNode(); savenode.setNode(save); Save[k++]=savenode; Node[] save1=new Node[10000]; TwoNodeLine(Value[logo1],Value[logo2],save1); SaveNode savenode1=new SaveNode(); savenode1.setNode(save1); Save[k++]=savenode1; } if(Graph_sort[i][logo1]==1&&Graph_sort[i][logo2]!=1){ Node[] save=new Node[10000]; TwoNodeLine(Value[logo1],Value[i],save); SaveNode savenode=new SaveNode(); savenode.setNode(save); Save[k++]=savenode; } if(Graph_sort[i][logo1]!=1&&Graph_sort[i][logo2]==1){ Node[] save=new Node[10000]; TwoNodeLine(Value[logo2],Value[i],save); SaveNode savenode=new SaveNode(); savenode.setNode(save); Save[k++]=savenode; } } for(int i=0;i<Max;i++){ //将Graph_sort置0; for(int j=0;j<Max;j++){ Graph_sort[i][j]=0; } } } private void TwoNodeLine(Node x,Node y,Node[] Save){ int Temp_x,Temp_y,kx,ky; Temp_x=x.GetNode_x()-y.GetNode_x(); Temp_y=x.GetNode_y()-y.GetNode_y(); kx=(int)((Temp_x/Math.sqrt(Temp_x*Temp_x+Temp_y*Temp_y))*step); ky=(int)((Temp_y/Math.sqrt(Temp_x*Temp_x+Temp_y*Temp_y))*step); Save[0]=y; for(int i=1;i<INFI-1;i++){ if(Save[i]==x){ break; } else{ Node che=new Node(); che.setNode_x(Save[i-1].GetNode_x()+kx); che.setNode_y(Save[i-1].GetNode_y()+ky); Save[i]=che; Temp_x=x.GetNode_x()-Save[i].GetNode_x(); Temp_y=x.GetNode_y()-Save[i].GetNode_y(); kx=(int)((Temp_x/Math.sqrt(Temp_x*Temp_x+Temp_y*Temp_y))*step); ky=(int)((Temp_y/Math.sqrt(Temp_x*Temp_x+Temp_y*Temp_y))*step); } } } private void ThreeNodeLine(Node x,Node y,Node z,Node[] Save){ int Temp_x,Temp_y,kx,ky; int Temp_x1=x.GetNode_x()-z.GetNode_x(); int Temp_y1=x.GetNode_y()-z.GetNode_y(); int Temp_x2=y.GetNode_x()-z.GetNode_x(); int Temp_y2=y.GetNode_y()-z.GetNode_y(); int Kx1=(int)((Temp_x1/Math.sqrt(Temp_x1*Temp_x1+Temp_y1*Temp_y1))*step); int Ky1=(int)((Temp_y1/Math.sqrt(Temp_x1*Temp_x1+Temp_y1*Temp_y1))*step); int Kx2=(int)((Temp_x2/Math.sqrt(Temp_x2*Temp_x2+Temp_y2*Temp_y2))*step); int Ky2=(int)((Temp_y2/Math.sqrt(Temp_x2*Temp_x2+Temp_y2*Temp_y2))*step); Save[0]=z; for(int i = 1;i<INFI-1;i++){ if(Kx1+Kx2==0&&Ky1+Ky2==0){ break; } else { Temp_x=Kx1+Kx2; Temp_y=Ky1+Ky2; kx=(int)((Temp_x/Math.sqrt(Temp_x*Temp_x+Temp_y*Temp_y))*step); ky=(int)((Temp_y/Math.sqrt(Temp_x*Temp_x+Temp_y*Temp_y))*step); Node che=new Node(); che.setNode_x(Save[i-1].GetNode_x()+kx); che.setNode_y(Save[i-1].GetNode_y()+ky); Save[i]=che; Temp_x1=x.GetNode_x()-Save[i].GetNode_x(); Temp_y1=x.GetNode_y()-Save[i].GetNode_y(); Temp_x2=y.GetNode_x()-Save[i].GetNode_x(); Temp_y2=y.GetNode_y()-Save[i].GetNode_y(); Kx1=(int)((Temp_x1/Math.sqrt(Temp_x1*Temp_x1+Temp_y1*Temp_y1))*step); Ky1=(int)((Temp_y1/Math.sqrt(Temp_x1*Temp_x1+Temp_y1*Temp_y1))*step); Kx2=(int)((Temp_x2/Math.sqrt(Temp_x2*Temp_x2+Temp_y2*Temp_y2))*step); Ky2=(int)((Temp_y2/Math.sqrt(Temp_x2*Temp_x2+Temp_y2*Temp_y2))*step); } } } public void paintComponent(Graphics G){ super.paintComponent(G); Graphics2D G2D=(Graphics2D)G; for(int i=0;Value[i]!=null;i++){ G2D.fillOval(Value[i].GetNode_x(), Value[i].GetNode_y(), 10, 10); } for(int i=0;Save[i]!=null;i++) { Node[] node=new Node[1000]; node=Save[i].getNode(); for(int j=0;node[j]!=null;j++){ G2D.fillOval(node[j].GetNode_x(), node[j].GetNode_y(), 3, 3); } } } } public class Work8 { private static void GuiShow(){ JFrame frame=new JFrame(); frame.setTitle("work6Test"); frame.setSize(400, 400); frame.setLocationRelativeTo(null); frame.setVisible(true); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); NodeConnect Panel=new NodeConnect(); frame.add(Panel); } public static void main(String[] args) { GuiShow(); } }