图G(V,E)是由顶点的有穷非空集合和顶点之间的边的集合组成，V是图中顶点的集合，E是边的集合
图最常用的两种数据结构是邻接矩阵和邻接表
邻接矩阵结构 用两个数组表示图，一个一维数组存储顶点信息，一个二维数组存储边的信息
class Graph <T> { public ArrayList<T> vertexes; //储存顶点 public int[][] edges; //邻接矩阵 private int numOfVertexes; //当前顶点的数量 private int numOfEdges; //当前边的数量 public static final int INFINITY = 65535; //有权图，代表不通，无权图为0 /** * @param n is the number of vertex */ public Graph(int n) { //将数组初始化，开始时所有边均不通 edges = new int[n][n]; for(int i = 0; i <n; i++) Arrays.fill(edges[i], INFINITY); vertexes = new ArrayList<>(n); numOfVertexes = 0; numOfEdges = 0; } //插入顶点 public void insertVertex(T vertex) { vertexes.add(vertex); edges[vertexes.indexOf(vertex)][vertexes.indexOf(vertex)] = 0; //顶点与自身的权值为0 numOfVertexes++; } //添加边:无向图 public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } //添加边：有向图 /* public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; numOfEdges++; } */ //显示邻接矩阵 public void showGraph() { for(int[] link : edges) System.out.println(Arrays.toString(link)); } //获取顶点数量 public int getNumOfVertexes() { return numOfVertexes; } //返回顶点i对应的数据 public T getValueByIndex(int i) { return vertexes.get(i); } //返回两个顶点之间的权值 public int getWeight(int v1, int v2) { return edges[v1][v2]; } }