对于图来说，图中的任何一个顶点都可以被看成第一个顶点，任一顶点的邻接点之间也不存在次序关系。

  • 定义顶点
  1. public class Vertex {
  3.     public String label;
  5.     public Vertex(String label) {
  6.         this.label = label;
  7.     }
  8. }
  • 定义边
  1. public class Edge {
  3.   public int index;
  4.   public int weight;
  6.   public Edge(int index, int weight) {
  7.       this.index = index;
  8.       this.weight = weight;
  9.   }
  10. }

图不能用简单的顺序存储结构表示。所以图的存储结构有五种。

1. 邻接矩阵

图的邻接矩阵（Adjcency Matrix）存储方式是用二维数组来表示，其中行表示顶点信息，列表示邻接顶点信息，数组值表示边信息。

无向图的邻接矩阵表示

无向图中用0表示两个顶点之间无边，1表示两个顶点之间有边；定义数组 vertex[4]={ 图的存储结构 - 图1 }表示顶点数组，定义如下数组表示边数组
图的存储结构 - 图2
矩阵图中的对角线的值表示顶点到自身的边，所以全为0表示，其他值1表示存在顶点图的存储结构 - 图3到顶点图的存储结构 - 图4的边。

有向图的邻接矩阵表示

有向图可以用数值表示两个顶点之间边的权值，图的存储结构 - 图5表示两个顶点之间无边；
可以定义数组 vertex[4]={ 图的存储结构 - 图6}表示顶点数组，再定义如下数组表示边数组
图的存储结构 - 图7
矩阵图中的对角线的值表示顶点到自身的边，所以全为0表示，其他值1表示存在顶点图的存储结构 - 图8到顶点图的存储结构 - 图9的边。

邻接矩阵存储结构

  1. public class Graph{
  3.   public Vertex[] vertexs;
  4.   public int[][] adjMatrix;
  6.   public Graph(Vertex[] vertexs) {
  7.       this.vertexs = vertexs;
  8.       this.adjMatrix = new int[vertexs.length][vertexs.length];
  9.   }
  11.   public Graph(Vertex[] vertexs, int[][] adjMatrix) {
  12.       this.vertexs = vertexs;
  13.       this.adjMatrix = adjMatrix;
  14.   }
  16.   public void addEdge(int i, int j) {
  17.       this.adjMatrix[i][j] = 1;
  18.   }
  20.   public int[] getAdjVertex(int i) {
  21.       return adjMatrix[i];
  22.   }
  24.   public int getAdjArc(int i, int j) {
  25.       return adjMatrix[i][j];
  26.   }
  27. }

2. 邻接表

对于边数较少的图，邻接矩阵存在对存储空间极大的浪费。因此可以考虑另外一种存储结构，链式存储结构，，即将顶点存入数组，并对顶点的邻接顶点进行链式存储。这种数组和链表相结合的存储方法称为邻接表（Adjacency List）。
定义链表节点

  1. public class Graph{
  3.   private Vertex[] vertex;//顶点数
  4.   private LinkedList<Edge>[] adjEdge ;
  6. public Graph(Vertex[] vertexs) {
  7.     this.vertexs = vertexs;
  8.     this.adjEdge = new LinkedList[vertexs.length];
  9.     for (int i = 0; i < vertexs.length; i++) {
  10.         this.adjEdge[i] = new LinkedList<Edge>();
  11.     }
  12.   }
  14.   public Graph(int[] vertex, LinkedList<Edge>[] adjEdge){
  15.     this.vertex = vertex;
  16.     this.adjEdge = adjEdge;
  17.   }
  19.   public void addEdge(int i, int j,int weight) {
  20.      this.adjEdge[i].add(new Edge(j,weight));
  21.   }
  23.   public LinkedList<Edge> getAdjVertex(int i) {
  24.       return this.adjEdge[i];
  25.   }
  26. }

对于有向图，邻接表结构相似，除了要有一个链表数组记录出度的相邻顶点，还要有一个链表数组记录入度的相邻顶点。

3. 十字链表

十字链表（Orthogonal List）是邻接表和逆邻接表的结合,因为对于有向图，邻接表只能记录顶点的出度，逆邻接表只能记录顶点的入度。
顶点表结构如下：

  1. public class Node{
  2.   private int data;
  3.   private Node next;//下一个节点
  4.  }
  6. public class Vertex{
  7.   private int data;
  8.   private Node firstin;//入度链表的第一个节点
  9.   private Node firstout;//出度的第一个节点
  10. }

4. 邻接多重表

对于无向图，如果关注的重点是顶点，则用邻接表，但是如果是关注对边的操作，如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边依附的两个顶点进行操作。

5. 边集数组

边集数组是由二维数组构成，行表示图中的每个边，第一列表示边起点下标（begin）,第二列表示（end）,第三列表示边的权重（weight）。

邻接矩阵 vs 邻接表

  • 有向图中邻接表或者逆邻接表的空间复杂度为图的存储结构 - 图10
  • 无向图中邻接表的空间复杂度为图的存储结构 - 图11
  • 若图中的边数e远远小于图的存储结构 - 图12,称为稀疏矩阵，其邻接表比邻接矩阵节省空间
  • 若图中的边数e接近图的存储结构 - 图13,称为稠密矩阵，其邻接矩阵比邻接表节省空间，其中无向图中边e接近n(n-1)/2，有向图中边e接近n(n-1)
  • 求有向图顶点的度时，采用邻接矩阵比邻接表结构方便，在邻接表结构中，求顶点的出度容易，入度困难，逆邻接表中，求顶点的入度比较容易，出度困难。
  • 判断边，邻接矩阵比邻接表容易，求边数时：邻接矩阵中花费的时间复杂度为图的存储结构 - 图14，邻接表中花费的时间复杂度为图的存储结构 - 图15