以前都用的C++,java没有指针,如何存储图的呢,我现在想用邻接表实现一个图,怎么做?
------解决方案--------------------
1楼看贴不仔细。楼主说的图是一种数据结构,不是图片。
java没有指针,但有引用啊
关于java的图的实现,楼主可以网上搜索。
这篇帖子也有描述
http://www.iteye.com/topic/645079
------解决方案--------------------
写个例子你参考参考:
- Java code
//演示程序:邻接矩阵表示的带权有向图(网)import java.io.*; //最大边数和顶点数// “邻接矩阵”类class Graph { static int MaxEdges = 50; static int MaxVertices = 10; static double MaxValue=9999.9; //无穷大 //存放顶点的数组 private char VerticesList[]=new char[MaxVertices]; //邻接矩阵(存放两个顶点权值) private double Edge[][]=new double[MaxVertices][MaxVertices]; private int CurrentEdges; //现有边数 private int CurrentVertices; //现有顶点数 //构造函数:建立空的邻接矩阵 public Graph ( ){ for ( int i = 0; i < MaxVertices; i++ ) for ( int j = 0; j < MaxVertices; j++ ) if(i==j) Edge[i][j] = 0; //对角线 else //非对角线上无穷大 Edge[i][j] =MaxValue; CurrentEdges = 0; //现有边数 CurrentVertices = 0; //现有顶点数 } //查找指定的顶点的序号 public int FindVertex (char vertex){ //在顶点数组里面查找 for(int i=0;i<CurrentVertices;i++) if(VerticesList[i]==vertex) return i; //返回下标 return -1; //没有找到 } //图空否? public boolean IsGraphEmpty ( ){ return CurrentVertices==0; } //图满否? public boolean IsGraphFull ( ){ return CurrentVertices==MaxVertices || CurrentEdges==MaxEdges; } //取得顶点数 public int NumberOfVertices ( ){ return CurrentVertices; } //取得边数 public int NumberOfEdges ( ){ return CurrentEdges; } //按序号取得顶点值 public char GetValue ( int i ){ return i >= 0 && i <= CurrentVertices-1 ? VerticesList[i] : ' '; } //取得一条边的权值 public double GetWeight ( int v1, int v2 ){ if (v1 < 0 || v1 > CurrentVertices - 1) return -1.0; //用-1表示出错 if (v2 < 0 || v2 > CurrentVertices - 1) return -1.0; return Edge[v1][v2]; } //取得第一个邻接点的序号 public int GetFirstNeighbor ( int v ){ if (v< 0 || v > CurrentVertices - 1) return -1; //用-1表示出错 //邻接矩阵的行号和列号是两个邻接点的序号 for ( int col = 0; col < CurrentVertices; col++ ) if ( Edge[v][col] > 0 && //自身 Edge[v][col] < MaxValue ) //无穷大 return col; return -1; //无邻接点 } //插入一个顶点 public int InsertVertex ( char vertex ){ if(IsGraphFull()) return -1; //插入失败 //顶点表增加一个元素 VerticesList[CurrentVertices]=vertex; //邻接矩阵增加一行一列 for ( int j = 0;j <=CurrentVertices;j++ ) { Edge[CurrentEdges][j]=MaxValue; Edge[j][CurrentEdges]=MaxValue; } Edge[CurrentEdges][CurrentEdges]=0; CurrentVertices++; return CurrentVertices; //插入位置 } //插入一个边 public boolean InsertEdge( int v1, int v2, double weight){ if (v1 < 0 || v1 > CurrentVertices - 1) return false; //出错 if (v2 < 0 || v2 > CurrentVertices - 1) return false; Edge[v1][v2]=weight; //网,有向边 return true; } //删除一个顶点 public boolean RemoveVertex ( int v ){ if (v< 0 || v > CurrentVertices - 1) return false; //出错 //修改顶点表 for(int i=v+1;i< CurrentVertices;i++) VerticesList[i-1]=VerticesList[i]; //修改邻接矩阵 int k=0; //累计将要删去的边数 for(int i=0;i< CurrentVertices;i++) if ( Edge[v][i] > 0 && //自身 Edge[v][i] < MaxValue ) //无穷大 k++; //第v行 for(int i=0;i< CurrentVertices;i++) if ( Edge[i][v] > 0 && //自身 Edge[i][v] < MaxValue ) //无穷大 k++; //第v列 //覆盖第v行 int j; for(int i=v+1;i< CurrentVertices;i++) for(j=0;j< CurrentVertices;j++) Edge[i-1][j]=Edge[i][j]; //覆盖第v列 for(j=v+1;j< CurrentVertices;j++) for(int i=0;i< CurrentVertices;i++) Edge[i][j-1]=Edge[i][j]; CurrentVertices--; //修改顶点数 CurrentEdges-=k; //修改边数 return true; } //删除一个边 public boolean RemoveEdge ( int v1, int v2 ){ if (v1 < 0 || v1 > CurrentVertices - 1) return false; //用-1表示出错 if (v2 < 0 || v2 > CurrentVertices - 1) return false; if ( v1==v2) return false; Edge[v1][v2]=MaxValue; //网,无路径 return true; } //打印邻接矩阵 public void display(){ int i,j; System.out.println(" 顶点表"); for(i=0;i<CurrentVertices;i++) System.out.print(VerticesList[i]+" "); System.out.println('\n'+" 邻接矩阵"); for(i=0;i<CurrentVertices;i++) { for(j=0;j<CurrentVertices;j++) if(Edge[i][j]==MaxValue) System.out.print('@'+" "); else System.out.print(Edge[i][j]+" "); System.out.println(); } } //主函数 public static void main(String []args){ Graph G=new Graph(); //邻接矩阵 //准备有向图(网)数据 char c[]={'A','B','C','D','E','F'}; //顶点 int v[][]={ //弧 {0,1},{0,3},{1,2},{2,3},{4,5}, {1,3},{2,4},{3,5},{4,3},{2,5} }; double e[]={2.3,3.6,6.5,2.5,1.7, 0.8,7.2,9.1,5.2,1.3}; //权 //插入顶点 for(int i=0;i<6;i++) G.InsertVertex(c[i]); //插入弧 for(int i=0;i<10;i++) G.InsertEdge(v[i][0],v[i][1],e[i]); //打印输出 G.display(); //删除一个顶点 G.RemoveVertex(3); G.display(); //删除一条边 G.RemoveEdge(2,4); G.display(); } //main方法结束} //“邻接矩阵”类结束