图的信息包括两部分，结点信息和结点间边的信息；结点信息可用线性表（顺序表或单链表）来存储，对于n个结点的图，每个结点都可能与其他n-1个结点成为邻接结点，所以边的信息存储是一个n×n矩阵的存储，主要有邻接矩阵和邻接表两种方法。
1、邻接矩阵存储
邻接矩阵定义，假设图G=(V,E)有n个结点，即V={v0,v1,...,v(n-1)}，E可用矩阵A描述，对于A中的每一个元素aij，满足（1）若(vi,vj)∈E或<vi,vj>∈E，令aij=wij（若非带权图，权值wij=1）；（2）否则若i≠j，即某一个结点与非本身的某个结点不是邻接结点，此时令aij=∞；（3）否则若i=j，即某结点与本身构成环路，因为本文不讨论这种情况，故令aij=0。
矩阵A中的元素aij表示了结点vi和结点vj之间边的关系，也即这两个结点有邻接关系，所以称A为邻接矩阵。
说明：在图的邻接矩阵存储结构中，结点信息用一位数组存储，边信息的邻接矩阵使用二维数组存储，无向图的邻接矩阵一定是对称矩阵，因为aij=aji；有向图的邻接矩阵一般是非对称矩阵，因为有aij，即结点vi指向vj，不一定有结点vj指向vi。
对于带权图，邻接矩阵第i行中所有0<aij<∞的元素个数等于第i个结点的出度，第j列中所有0<aij<∞的元素个数等于第j个结点的入度。
2、邻接表存储
当图中结点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；
当图中结点数目较大且边的数目远小于相同结点的完全图的边数时，采用图的邻接表存储结构空间效率较高。此时，也即前面提到过的稀疏矩阵，可采用三元组链表。
对于邻接表存储结构暂时不做详细描述。
接下来我们来实现邻接矩阵存储结构并简单使用，首先要建立邻接矩阵图类来完成结点和边信息的存储：
package Map; import linearlink.SeqList; /** * @author sun * 创建时间：2017年5月7日上午10:12:53 */ //采用顺序表存储结点的数据元素，边以及权值信息用二维数组存储 public class AdjMWGraph { static final int maxWeight = 10000; private SeqList vertices;//存储结点的顺序表 private int[][] edge;//存储边的二维数组（邻接矩阵） private int numOfEdges;//边的个数 public AdjMWGraph(int maxV){//maxV为结点个数 vertices = new SeqList(maxV); edge = new int[maxV][maxV]; for(int i=0;i<maxV;i++){ for(int j=0;j<maxV;j++){ if(i==j) edge[i][j] = 0; else edge[i][j] = maxWeight; } } numOfEdges = 0; } public int getNumOfVertices(){//返回结点个数 return vertices.getSize(); } public int getNumOfEdges(){//返回边的个数 return numOfEdges; } public Object getValue(int v)throws Exception{//返回结点v的数据元素 return vertices.getData(v); } public int getWeight(int v1,int v2)throws Exception{//返回边<v1,v2>权值 if(v1<0 || v1>=vertices.getSize() || v2<0 || v2>=vertices.getSize()) throw new Exception("参数v1或v2越界出错！"); return edge[v1][v2]; } public void insertVertex(Object vertex)throws Exception{//插入结点 vertices.insert(vertices.getSize(), vertex); } public void inserEdge(int v1,int v2,int weight)throws Exception{//插入边 if(v1<0 || v1>=vertices.getSize() || v2<0 || v2>=vertices.getSize()) throw new Exception("参数v1或v2越界出错！"); //邻接矩阵中原来没有的边权值为0或无穷大，所以插入边只用修改权值就ok edge[v1][v2] = weight; numOfEdges++; } public void deleteEdge(int v1,int v2)throws Exception{//删除边 if(v1<0 || v1>=vertices.getSize() || v2<0 || v2>=vertices.getSize()) throw new Exception("参数v1或v2越界出错！"); if(edge[v1][v2]==maxWeight || v1==v2) throw new Exception("该条边本就不存在！"); edge[v1][v2] = maxWeight;//删除边就把权值变为无穷大 numOfEdges--; } public int getFirstNeighbor(int v)throws Exception{ //取结点v的第一个邻接结点，若存在返回下标，否则返回-1 if(v<0||v>=vertices.getSize()) throw new Exception("参数v越界出错！"); for(int col=0;col<vertices.getSize();col++) if(edge[v][col]>0 && edge[v][col]<maxWeight) return col; return -1; } public int getNextNeighbor(int v1,int v2)throws Exception{ //取结点v1的邻接结点v2后的邻接结点，若存在返回下标，否则返回-1 if(v1<0 || v1>=vertices.getSize() || v2<0 || v2>=vertices.getSize()) throw new Exception("参数v1或v2越界出错！"); for(int col=v2+1;col<vertices.getSize();col++) if(edge[v1][col]>0 && edge[v1][col]<maxWeight) return col; return -1; } } 接下来对图G进行测试，G=（V，E）V={A,B,C,D,E},E={<A,B>,<A,E>,<B,D>,<D,C>,<C,B>},权值w={10，20,30,50,40} package Map; /** * @author sun * 创建时间：2017年5月7日上午11:00:45 */ //把创建图所需要的数据和方法封装到类里 public class RowColWeight {//边邻接矩阵的数据 int row;//行下标 int col;//列下标 int weight;//权值 public RowColWeight(int r,int c,int w){ row = r; col = c; weight = w; } public static void createGraph(AdjMWGraph g,Object[] v,int n, RowColWeight[] rc,int e)throws Exception{ //static成员函数，用所给参数创建AdjMWGraph类对象g //v为结点的数据元素集合，n为结点个数，rc为边的集合，e为边的个数 for(int i=0;i<n;i++) g.insertVertex(v[i]);//在图g的结点顺序表中插入n个结点 for(int k=0;k<e;k++) g.inserEdge(rc[k].row, rc[k].col, rc[k].weight); } } 主函数测试： package Map; /** * @author sun * 创建时间：2017年5月7日上午11:11:39 */ public class TestMyGraph { public static void main(String[] args) { int n=5,e=5; AdjMWGraph g = new AdjMWGraph(n); Character[] a = {new Character('A'), new Character('B'), new Character('C'), new Character('D'), new Character('E')}; RowColWeight[] rcw = {new RowColWeight(0,1,10), new RowColWeight(0,4,20), new RowColWeight(1,3,30), new RowColWeight(2,1,40), new RowColWeight(3,2,50)}; try{ RowColWeight.createGraph(g, a, n, rcw, e); System.out.println("结点个数为："+g.getNumOfVertices()); System.out.println("边的个数为："+g.getNumOfEdges()); g.deleteEdge(0, 4);//删除边<0,4> System.out.println(); System.out.println("结点个数为："+g.getNumOfVertices()); System.out.println("边的个数为："+g.getNumOfEdges()); } catch(Exception ex){ ex.printStackTrace(); } } } /* 结点个数为：5 边的个数为：5 结点个数为：5 边的个数为：4 */