图的表示

首先我们来看看图的数据结构长什么样子

图的表示 - 图1

一个图它由顶点 Vertex 和边 Edge 组成，上图蓝色的节点表示顶点，而节点与节点之间的有条线连着，这就是顶点之间的边。为了在计算机中表示图，我们给图的顶点编了号，从 图的表示 - 图2 开始。在实际的模型中，顶点可能表示的是一个地铁站点，社交网络中的一个人，我们可以通过哈希表将编号与顶点实际的意义映射起来，进而把顶点的具体意义抽象为编号或者下标，当图的顶点以编号表示时，它就不具有具体的意义，从而我们可以研究图的一般理论，而当我们需要结论的具体意义时，可以通过哈希表将编号映射为具体的意义。

图的分类

根据边是否有方向可以分为有向图和无向图，根据边上有否有权值可以分为有权图和无权图

有向 无向
有权 有向有权图 无向有权图
无权 有向无权图 无向无权图

图的表示 - 图3

图的基本概念

在进入正题之前，简单的介绍一下在后面会遇到的关于图的基本概念。

  • 自环边：图中有一个顶点有条边指向自己
  • 平行边：两个顶点之间有两条边

如果一幅图既没有自环边，也没有平行边，我们就称该图为简单图。我们只处理简单图，如果图中有自环边或者平行边，我们会忽略这种边，或者抛出异常。

在一个图中，并不是所有的顶点都是联通的，如下

图的表示 - 图4

例如顶点 6-7 和顶点 0-5 之间是不联通的，像上面这样的图，我们认为它有两个联通分量，顶点 0-5 和顶点 6-7 分别代表一个联通分量。

另外，根据图中是否有环，我们可以将图分为有环图和无环图

图的表示 - 图5

最后介绍一个有关图的概念，那就是度(degree)，对于无向图和有向图，度的定义是不同的，这里我们介绍无向图关于度的定义，度指的是某个顶点有多少个邻边，度是顶点的属性。比如对于下图

图的表示 - 图6

顶点 图的表示 - 图7 的度为 图的表示 - 图8，因为顶点 图的表示 - 图9 有两个邻边，同理，顶点 图的表示 - 图10 的度为 图的表示 - 图11，因为它有三个邻边。

图的表示

所谓图的表示，就是指如何在计算机中保存一个图的数据结构

图的表示 - 图12

如上图，怎么将它保存在计算机中。如果学习过其他数据结构的话，如栈，队列，树，它们是怎么表示的呢?

图的表示 - 图13

对于栈和队列这种线性的数据结构，我们一般使用数组或者链表来进行存储，而对于树这种数据结构，我们一般使用链表进行表示，每个节点都有两个指针分别指向它的左孩子和右孩子，当然对于某些树结构，如堆、线段树，我们也可以使用数组来进行表示，因为这两种数据结构都是满二叉树，它们的孩子节点与父节点之间含有某种关系，可以十分方便的使用数组进行表示。

邻接矩阵

首先我们介绍使用一个矩阵来存储图，如果整个图有 图的表示 - 图14 个节点，那么我们就用 图的表示 - 图15 大小的矩阵来存储图，假设这个矩阵记做 图的表示 - 图16，如果 图的表示 - 图17，则说明顶点 图的表示 - 图18 与顶点 图的表示 - 图19 之间存在一条边，反之如果 图的表示 - 图20，则说明顶点 图的表示 - 图21 与顶点 图的表示 - 图22 之间不存在一条边

图的表示 - 图23

因为不存在自环边，所以 图的表示 - 图24 的值一定为 图的表示 - 图25，即矩阵对角线上的值一定是 图的表示 - 图26。

在构建一张图时，我们会读取一个 txt 的文件，根据这个文件我们使用矩阵来存储一张图，例如上图所对应的 txt 内容如下

  1. 6 7
  2. 0 1
  3. 0 2
  4. 1 3
  5. 2 3
  6. 2 4
  7. 3 5
  8. 4 5

这个 txt 表示什么意思呢? 第一行的两个数字表示图中的顶点数和边数，如上图有 图的表示 - 图27 个顶点和 图的表示 - 图28 条边，后面每行的两个数字表示两个顶点，表示这两个顶点之间存在一条边，如第二行就表示顶点 图的表示 - 图29 和顶点 图的表示 - 图30 之间存在一条边，因为总共有 图的表示 - 图31 条边，所以第一行后应该有 图的表示 - 图32 行表示有 图的表示 - 图33 条边。

代码如下：

  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.Scanner;
  5. public class AdjMatrix {
  6.     // 图的边数
  7.     private int E;
  8.     // 图的顶点个数
  9.     private int V;
  10.     // 表示图的矩阵
  11.     private int[][] matrix;
  13.     public AdjMatrix(String filename) {
  14.         // 从文件中读取图的数据
  15.         File file = new File(filename);
  16.         Scanner scanner = null;
  17.         try {
  18.             // 第一行是顶点数和边数
  19.             scanner = new Scanner(file);
  20.             this.V = scanner.nextInt();
  21.             matrix = new int[this.V][this.V];
  22.             this.E = scanner.nextInt();
  24.             for (int i = 0; i < this.E; i++) {
  25.                 // 读取两个相邻的顶点
  26.                 int a = scanner.nextInt();
  27.                 int b = scanner.nextInt();
  29.                 // 设置为 1 表示相邻
  30.                 this.matrix[a][b] = 1;
  31.                 this.matrix[b][a] = 1;
  32.             }
  33.         } catch (FileNotFoundException e) {
  34.             e.printStackTrace();
  35.         } finally {
  36.             assert scanner != null;
  37.             scanner.close();
  38.         }
  39.     }
  41.     // 当打印对象时，将矩阵打印出来
  42.     @Override
  43.     public String toString() {
  44.         StringBuilder stringBuilder = new StringBuilder();
  45.         stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
  46.         for (int i = 0; i < this.V; i++) {
  47.             for (int j = 0; j < this.V; j++) {
  48.                 stringBuilder.append(String.format("%d ", this.matrix[i][j]));
  49.             }
  50.             stringBuilder.append("\n");
  51.         }
  52.         return stringBuilder.toString();
  53.     }
  55.     public static void main(String[] args) {
  56.         AdjMatrix adjMatrix = new AdjMatrix("g.txt");
  57.         System.out.println(adjMatrix);
  58.     }
  59. }

打印结果为

  1. V: 6, E: 7
  2. 0 1 1 0 0 0 
  3. 1 0 0 1 0 0 
  4. 1 0 0 1 1 0 
  5. 0 1 1 0 0 1 
  6. 0 0 1 0 0 1 
  7. 0 0 0 1 1 0

AdjMatrix 类有三个属性

属性 含义
V 表示顶点数
E 表示边数
matrix 表示图的矩阵

但是上面的程序还不够健壮，因为我们没有对 g.txt 中读到的数字进行校验，例如读到的顶点个数为负数，读到的顶点编号不合理，例如有 图的表示 - 图34 个顶点，但是它的编号为 图的表示 - 图35。另外，我们只处理简单图，对于自环边以及平行边也没有进行处理，所以我们需要对上面的代码进行改进

  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.ArrayList;
  4. import java.util.Scanner;
  6. public class AdjMatrix {
  7.     private int E;
  8.     private int V;
  9.     private int[][] matrix;
  11.     public AdjMatrix(String filename) {
  12.         File file = new File(filename);
  13.         Scanner scanner = null;
  14.         try {
  15.             scanner = new Scanner(file);
  17.             // 如果读取到的 V 和 E 小于 0，那么抛出异常
  18.             this.V = scanner.nextInt();
  19.             if (this.V < 0) {
  20.                 throw new IllegalArgumentException("V Must Be Positive");
  21.             }
  22.             matrix = new int[this.V][this.V];
  23.             this.E = scanner.nextInt();
  24.             if (this.E < 0) {
  25.                 throw new IllegalArgumentException("E Must Be Positive");
  26.             }
  28.             for (int i = 0; i < this.E; i++) {
  29.                 // 对读取到的顶点编号进行验证，是否在 [0, V) 的范围中
  30.                 int a = scanner.nextInt();
  31.                 validateVertex(a);
  32.                 int b = scanner.nextInt();
  33.                 validateVertex(b);
  35.                 // 如果存在自环边，抛出异常
  36.                 if (a == b) {
  37.                     throw new IllegalArgumentException("Self loop exists");
  38.                 }
  39.                 // 如果存在平行边，抛出异常
  40.                 if (this.matrix[a][b] == 1) {
  41.                     throw new IllegalArgumentException("Parallel edge exists");
  42.                 }
  43.                 this.matrix[a][b] = 1;
  44.                 this.matrix[b][a] = 1;
  45.             }
  46.         } catch (FileNotFoundException e) {
  47.             e.printStackTrace();
  48.         } finally {
  49.             assert scanner != null;
  50.             scanner.close();
  51.         }
  52.     }
  54.     // 对顶点编号进行验证，是否合法
  55.     private void validateVertex(int v) {
  56.         if (v < 0 || v >= this.V) {
  57.             throw new IllegalArgumentException("Vertex " + v + " is invalid");
  58.         }
  59.     }
  61.     // 返回顶点数
  62.     public int V() {
  63.         return this.V;
  64.     }
  66.     // 返回边数
  67.     public int E() {
  68.         return this.E;
  69.     }
  71.     // 返回与顶点 v 相邻的所有顶点
  72.     public ArrayList<Integer> adj(int v) {
  73.         validateVertex(v);
  74.         ArrayList<Integer> res = new ArrayList<>();
  75.         for (int i = 0; i < this.V; i++) {
  76.             if (this.matrix[v][i] == 1) {
  77.                 res.add(i);
  78.             }
  79.         }
  81.         return res;
  82.     }
  84.     // 判断顶点 v 和 w 是否相邻
  85.     public boolean hasEdge(int v, int w) {
  86.         validateVertex(v);
  87.         validateVertex(w);
  88.         return this.matrix[v][w] == 1;
  89.     }
  91.     // 返回顶点 v 的度，即与顶点 v 相邻的顶点的个数
  92.     public int degree(int v) {
  93.         return adj(v).size();
  94.     }
  96.     // toString 不变，节省篇幅，省略
  97. }

在上面我们对读取到的数字都进行了检查，保证了代码的健壮性。除了增强了代码的健壮性以外，我们还在类中添加了五个方法，具体作用见下表

方法 作用
int V() 返回图的顶点数
int E() 返回图的边数
ArrayList adj(int v) 返回与顶点 v 相邻的顶点
boolean hasEdge(int v, int w) 判断两顶点是否相邻
int degree(int v) 返回顶点 v 的度

在最后我们分析一下使用邻接矩阵表示的空间复杂度和时间复杂度

空间复杂度：图的表示 - 图36#card=math&code=O%28V%5E2%29)

时间复杂度：

  • 建图：图的表示 - 图37#card=math&code=O%28E%29)
  • 获得与顶点 图的表示 - 图38 相邻的顶点：图的表示 - 图39#card=math&code=O%28V%29)
  • 查看两个顶点是否相邻：图的表示 - 图40#card=math&code=O%281%29)

对于建图来说，因为我们必须扫描所有的边才能获得必要的信息，所以建图的时间复杂度最少也是 图的表示 - 图41#card=math&code=O%28E%29)，无法再优化；而查看两个顶点是否相邻，时间复杂度为 图的表示 - 图42#card=math&code=O%281%29)，无需优化，那么我们看看空间复杂度和获得与顶点 图的表示 - 图43 相邻的顶点的时间复杂度能否进行优化。

因为我们平常遇到的图都是稀疏图，所谓稀疏图就是一幅图它的度平均值对于图的节点数目来说很小，这就会导致我们的邻接矩阵是一个稀疏矩阵，即大部分的元素是 图的表示 - 图44。例如对于一个社交网络，有一亿个节点，但是对于每个人来说，他认识的人最多几百个，也就是这幅图平均的度为几百，相对于一亿来说十分的小，所以社交网络是一个稀疏图。

建立一个图，我们只需要知道一幅图的顶点信息以及边的信息即可，也就是说我们只需要 图的表示 - 图45#card=math&code=O%28V%20%2B%20E%29) 的空间复杂度就可以表示一幅图，对于稀疏图来说，由于图的每个顶点度的平均值远远小于节点数，而 图的表示 - 图46 的大小等于平均度的值乘以节点数，即

图的表示 - 图47

从而有

图的表示 - 图48

得到

图的表示 - 图49%20%5Cll%20O(V%5E2)%0A#card=math&code=O%28V%20%2B%20E%29%20%5Cll%20O%28V%5E2%29%0A)

所以使用邻接矩阵表示图，对于稀疏矩阵来说，其实浪费了很多的空间，下面将介绍使用另一种方法表示图，无论是对于稀疏图还是稠密图，都可以有更好的性能。

邻接表

在这个小节中将讲解使用邻接表来表示矩阵，所谓的邻接表，是指对于每个顶点来说，我们使用一个链表来记录与它相邻的节点，如下图

图的表示 - 图50

图中表格第一列表示顶点编号，顶点编号后的一行表示与该顶点相邻的顶点，例如对于第一行，表示与顶点 图的表示 - 图51 相邻的顶点有顶点 图的表示 - 图52 和 图的表示 - 图53。

现在我们就要编码实现，因为大部分的逻辑与邻接矩阵是相同的，所以很多的代码与邻接矩阵表示的方式是一样的，不过因为底层保存图使用的是链表，有一些写法的不同，在下面的代码中我也会标出

  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.LinkedList;
  4. import java.util.Scanner;
  6. public class AdjList {
  7.     private int E;
  8.     private int V;
  9.     // 对每一个顶点，使用一个链表来存储与它相邻的顶点
  10.     private LinkedList<Integer>[] lists;
  12.     public AdjList(String filename) {
  13.         File file = new File(filename);
  14.         Scanner scanner = null;
  15.         try {
  16.             scanner = new Scanner(file);
  17.             this.V = scanner.nextInt();
  18.             if (this.V < 0) {
  19.                 throw new IllegalArgumentException("V Must Be Positive");
  20.             }
  22.             // 初始化链表
  23.             this.lists = new LinkedList[this.V];
  24.             for (int i = 0; i < this.V; i++) {
  25.                 this.lists[i] = new LinkedList<>();
  26.             }
  28.             this.E = scanner.nextInt();
  29.             if (this.E < 0) {
  30.                 throw new IllegalArgumentException("E Must Be Positive");
  31.             }
  33.             for (int i = 0; i < this.E; i++) {
  34.                 int a = scanner.nextInt();
  35.                 validateVertex(a);
  36.                 int b = scanner.nextInt();
  37.                 validateVertex(b);
  39.                 if (a == b) {
  40.                     throw new IllegalArgumentException("Self loop exists");
  41.                 }
  42.                 // 平行边的判断
  43.                 if (lists[a].contains(b)) {
  44.                     throw new IllegalArgumentException("Parallel edge exists");
  45.                 }
  47.                 // 将相邻顶点添加到自己的链表中
  48.                 this.lists[a].add(b);
  49.                 this.lists[b].add(a);
  50.             }
  51.         } catch (FileNotFoundException e) {
  52.             e.printStackTrace();
  53.         } finally {
  54.             assert scanner != null;
  55.             scanner.close();
  56.         }
  57.     }
  59.     private void validateVertex(int v) {
  60.         if (v < 0 || v >= this.V) {
  61.             throw new IllegalArgumentException("Vertex " + v + " is invalid");
  62.         }
  63.     }
  65.     public int V() {
  66.         return this.V;
  67.     }
  69.     public int E() {
  70.         return this.E;
  71.     }
  73.     public LinkedList<Integer> adj(int v) {
  74.         validateVertex(v);
  75.         // 直接返回顶点自己的链表即可
  76.         return lists[v];
  77.     }
  79.     public boolean hasEdge(int v, int w) {
  80.         validateVertex(v);
  81.         validateVertex(w);
  82.         return this.lists[v].contains(w);
  83.     }
  85.     public int degree(int v) {
  86.         return adj(v).size();
  87.     }
  89.     @Override
  90.     public String toString() {
  91.         StringBuilder stringBuilder = new StringBuilder();
  92.         stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
  93.         for (int v = 0; v < this.V; v++) {
  94.             stringBuilder.append(String.format("%d : ", v));
  95.             for (int w: adj(v)) {
  96.                 stringBuilder.append(String.format("%d ", w));
  97.             }
  98.             stringBuilder.append("\n");
  99.         }
  100.         return stringBuilder.toString();
  101.     }
  103.     public static void main(String[] args) {
  104.         AdjList adjList = new AdjList("g.txt");
  105.         System.out.println(adjList);
  106.     }
  107. }

输出为

  1. V: 6, E: 7
  2. 0 : 1 2 
  3. 1 : 0 3 
  4. 2 : 0 3 4 
  5. 3 : 1 2 5 
  6. 4 : 2 5 
  7. 5 : 3 4

下面分析一下使用邻接表实现图的时间复杂度和空间复杂度：

  • 空间复杂度：图的表示 - 图54#card=math&code=O%28V%20%2B%20E%29)
  • 时间复杂度：
    • 建表：图的表示 - 图55#card=math&code=O%28VE%29)
    • 获得与顶点 图的表示 - 图56 相邻的顶点：图的表示 - 图57#card=math&code=O%28degree%29)
    • 判断两个顶点是否相邻：图的表示 - 图58#card=math&code=O%28degree%29)

建表的时间复杂度为 图的表示 - 图59#card=math&code=O%28VE%29)，是因为每次我们都要扫描一遍表判断是否有平行边，判断两个顶点是否相邻的时间复杂度为 图的表示 - 图60#card=math&code=O%28degree%29)，是因为需要遍历表来判断两个顶点是否相邻。上面两个操作都比使用邻接矩阵实现图的操作更加的费时，都是因为查找的能力比较慢(在建图时需要查重判断是否有平行边，判断两个顶点是否相邻时也需要在链表中进行查找)，所以我们是否有办法可以提高查找表的速度。

说到查找速度，不得不说哈希表和红黑树，所以我们可以考虑使用 HashSet 或者 TreeSet 来替代上面的 LinkedList，以此来提高查找速度，二者查找的时间复杂度如下

数据结构 查找时间复杂度
HashSet 图的表示 - 图61#card=math&code=O%281%29)
TreeSet 图的表示 - 图62#card=math&code=O%28%5Clog%20v%29)

从时间复杂度上看，使用 HashSet 是更好的选择，但是 TreeSet 有一个优点那就是有序性，这会带来两个优点

  • 复现我的代码时可以得到与我一致的结果(输出的顺序)
  • 当我使用图片解释算法过程时，输出的结果可以与我演示的结果一致，可以更好的理解算法

所以这里我选择 TreeSet。我们新建一个 AdjSet 类，复制 AdjList 的代码，将其中所有的 LinkedList 改为 TreeSet 即可，如下

  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.Scanner;
  4. import java.util.TreeSet;
  6. public class AdjSet {
  7.     private int E;
  8.     private int V;
  9.     private TreeSet<Integer>[] sets;
  11.     public AdjSet(String filename) {
  12.         File file = new File(filename);
  13.         Scanner scanner = null;
  14.         try {
  15.             scanner = new Scanner(file);
  16.             this.V = scanner.nextInt();
  17.             if (this.V < 0) {
  18.                 throw new IllegalArgumentException("V Must Be Positive");
  19.             }
  21.             // 初始化链表
  22.             this.sets = new TreeSet[this.V];
  23.             for (int i = 0; i < this.V; i++) {
  24.                 this.sets[i] = new TreeSet<>();
  25.             }
  27.             this.E = scanner.nextInt();
  28.             if (this.E < 0) {
  29.                 throw new IllegalArgumentException("E Must Be Positive");
  30.             }
  32.             for (int i = 0; i < this.E; i++) {
  33.                 int a = scanner.nextInt();
  34.                 validateVertex(a);
  35.                 int b = scanner.nextInt();
  36.                 validateVertex(b);
  38.                 if (a == b) {
  39.                     throw new IllegalArgumentException("Self loop exists");
  40.                 }
  41.                 // 平行边的判断
  42.                 if (sets[a].contains(b)) {
  43.                     throw new IllegalArgumentException("Parallel edge exists");
  44.                 }
  46.                 // 将相邻顶点添加到自己的链表中
  47.                 this.sets[a].add(b);
  48.                 this.sets[b].add(a);
  49.             }
  50.         } catch (FileNotFoundException e) {
  51.             e.printStackTrace();
  52.         } finally {
  53.             assert scanner != null;
  54.             scanner.close();
  55.         }
  56.     }
  58.     private void validateVertex(int v) {
  59.         if (v < 0 || v >= this.V) {
  60.             throw new IllegalArgumentException("Vertex " + v + " is invalid");
  61.         }
  62.     }
  64.     public int V() {
  65.         return this.V;
  66.     }
  68.     public int E() {
  69.         return this.E;
  70.     }
  72.     public TreeSet<Integer> adj(int v) {
  73.         validateVertex(v);
  75.         // 直接返回自己的链表即可
  76.         return sets[v];
  77.     }
  79.     public boolean hasEdge(int v, int w) {
  80.         validateVertex(v);
  81.         validateVertex(w);
  82.         return this.sets[v].contains(w);
  83.     }
  85.     public int degree(int v) {
  86.         return adj(v).size();
  87.     }
  89.     @Override
  90.     public String toString() {
  91.         StringBuilder stringBuilder = new StringBuilder();
  92.         stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
  93.         for (int v = 0; v < this.V; v++) {
  94.             stringBuilder.append(String.format("%d : ", v));
  95.             for (int w: adj(v)) {
  96.                 stringBuilder.append(String.format("%d ", w));
  97.             }
  98.             stringBuilder.append("\n");
  99.         }
  100.         return stringBuilder.toString();
  101.     }
  103.     public static void main(String[] args) {
  104.         AdjSet adjSet = new AdjSet("g.txt");
  105.         System.out.println(adjSet);
  106.     }
  107. }

在最后我们做一个改进，观察三个类的 adj 方法

  1. // AdjMatrix
  2. public ArrayList<Integer> adj(int v) {
  3.     validateVertex(v);
  4.     ArrayList<Integer> res = new ArrayList<>();
  5.     for (int i = 0; i < this.V; i++) {
  6.         if (this.matrix[v][i] == 1) {
  7.             res.add(i);
  8.         }
  9.     }
  11.     return res;
  12. }
  14. // AdjList
  15. public LinkedList<Integer> adj(int v) {
  16.     validateVertex(v);
  17.     return lists[v];
  18. }
  20. // AdjSet
  21. public TreeSet<Integer> adj(int v) {
  22.     validateVertex(v);
  23.     return sets[v];
  24. }

这三个方法的返回值都不相同，这就会给使用者带来负担，它还需要记住每个类的返回值是什么，考虑到使用者拿到与顶点 图的表示 - 图63 相邻的所有顶点，一般都是用来遍历，所以我们返回一个接口 Iterable，ArrayList LinkedList TreeSet 三个类都实现了该接口，如下

  1. // AdjSet 其它两个类做相同修改
  2. public Iterable<Integer> adj(int v) {
  3.     validateVertex(v);
  4.     return sets[v];
  5. }

注意：记得还有修改 degree 方法，因为这是 adj 方法返回的是 Iterable 接口，该接口没有 size 方法，修改如下

  1. public int degree(int v) {
  2.     validateVertex(v);
  3.     return this.sets[v].size();
  4. }

其它两个类做类似的修改。

总结

在文章的最后，我们比较一下三种方法的空间复杂度和时间复杂度

空间 建图时间 两顶点是否相邻 查找顶点的邻边
邻接矩阵 图的表示 - 图64#card=math&code=O%28V%5E2%29) 图的表示 - 图65#card=math&code=O%28E%29) 图的表示 - 图66#card=math&code=O%281%29) 图的表示 - 图67#card=math&code=O%28V%29)
邻接表(LinkedList) 图的表示 - 图68#card=math&code=O%28V%20%2B%20E%29) 图的表示 - 图69#card=math&code=O%28EV%29) 图的表示 - 图70#card=math&code=O%28degree%29) 图的表示 - 图71#card=math&code=O%28degree%29)
邻接表(TreeSet) 图的表示 - 图72#card=math&code=O%28V%20%2B%20E%29) 图的表示 - 图73#card=math&code=O%28E%5Clog%20V%29) 图的表示 - 图74#card=math&code=O%28%5Clog%20degree%29) 图的表示 - 图75#card=math&code=O%28degree%29)

由上可见，底层使用 TreeSet 的邻接表来表示图，从空间和时间上都非常的优秀，在后面的文章，都将使用 TreeSet 版本的邻接表来表示图。

后面为了屏蔽差异，我们定义一个 Graph 的接口，这三个类都实现 Graph 接口，Graph 接口如下

  1. public interface Graph {
  2.     int V();
  3.     int E();
  4.     int degree(int v);
  5.     boolean hasEdge(int v, int w);
  6.     Iterable<Integer> adj(int v);
  7. }