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

image-20200926084046750

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

图的分类

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

有向 无向
有权 有向有权图 无向有权图
无权 有向无权图 无向无权图
图的分类

图的基本概念

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

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

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

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

GarphBasis2

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

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

GraphBasis3

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

image-20200926084046750

顶点 $0$ 的度为 $2$，因为顶点 $0$ 有两个邻边，同理，顶点 $2$ 的度为 $3$，因为它有三个邻边。

图的表示

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

image-20200926084046750

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

image-20200926084743962

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

邻接矩阵

首先我们介绍使用一个矩阵来存储图，如果整个图有 $V$ 个节点，那么我们就用 $V \times V$ 大小的矩阵来存储图，假设这个矩阵记做 $A$，如果 $A[i][j] = 1$，则说明顶点 $i$ 与顶点 $j$ 之间存在一条边，反之如果 $A[i][j] = 0$，则说明顶点 $i$ 与顶点 $j$ 之间不存在一条边

AdjMatrix-Page-2

因为不存在自环边，所以 $A[i][i]$ 的值一定为 $0$，即矩阵对角线上的值一定是 $0$。

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

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

这个 txt 表示什么意思呢? 第一行的两个数字表示图中的顶点数和边数，如上图有 $6$ 个顶点和 $7$ 条边，后面每行的两个数字表示两个顶点，表示这两个顶点之间存在一条边，如第二行就表示顶点 $0$ 和顶点 $1$ 之间存在一条边，因为总共有 $7$ 条边，所以第一行后应该有 $7$ 行表示有 $7$ 条边。

代码如下：

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class AdjMatrix {
    // 图的边数
    private int E;
    // 图的顶点个数
    private int V;
    // 表示图的矩阵
    private int[][] matrix;

    public AdjMatrix(String filename) {
        // 从文件中读取图的数据
        File file = new File(filename);
        Scanner scanner = null;
        try {
            // 第一行是顶点数和边数
            scanner = new Scanner(file);
            this.V = scanner.nextInt();
            matrix = new int[this.V][this.V];
            this.E = scanner.nextInt();
            
            for (int i = 0; i < this.E; i++) {
                // 读取两个相邻的顶点
                int a = scanner.nextInt();
                int b = scanner.nextInt();

                // 设置为 1 表示相邻
                this.matrix[a][b] = 1;
                this.matrix[b][a] = 1;
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            assert scanner != null;
            scanner.close();
        }
    }

    // 当打印对象时，将矩阵打印出来
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
        for (int i = 0; i < this.V; i++) {
            for (int j = 0; j < this.V; j++) {
                stringBuilder.append(String.format("%d ", this.matrix[i][j]));
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        AdjMatrix adjMatrix = new AdjMatrix("g.txt");
        System.out.println(adjMatrix);
    }
}

打印结果为

V: 6, E: 7
0 1 1 0 0 0 
1 0 0 1 0 0 
1 0 0 1 1 0 
0 1 1 0 0 1 
0 0 1 0 0 1 
0 0 0 1 1 0

AdjMatrix 类有三个属性

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

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

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class AdjMatrix {
    private int E;
    private int V;
    private int[][] matrix;

    public AdjMatrix(String filename) {
        File file = new File(filename);
        Scanner scanner = null;
        try {
            scanner = new Scanner(file);
            
            // 如果读取到的 V 和 E 小于 0，那么抛出异常
            this.V = scanner.nextInt();
            if (this.V < 0) {
                throw new IllegalArgumentException("V Must Be Positive");
            }
            matrix = new int[this.V][this.V];
            this.E = scanner.nextInt();
            if (this.E < 0) {
                throw new IllegalArgumentException("E Must Be Positive");
            }

            for (int i = 0; i < this.E; i++) {
                // 对读取到的顶点编号进行验证，是否在 [0, V) 的范围中
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);

                // 如果存在自环边，抛出异常
                if (a == b) {
                    throw new IllegalArgumentException("Self loop exists");
                }
                // 如果存在平行边，抛出异常
                if (this.matrix[a][b] == 1) {
                    throw new IllegalArgumentException("Parallel edge exists");
                }
                this.matrix[a][b] = 1;
                this.matrix[b][a] = 1;
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            assert scanner != null;
            scanner.close();
        }
    }

    // 对顶点编号进行验证，是否合法
    private void validateVertex(int v) {
        if (v < 0 || v >= this.V) {
            throw new IllegalArgumentException("Vertex " + v + " is invalid");
        }
    }

    // 返回顶点数
    public int V() {
        return this.V;
    }

    // 返回边数
    public int E() {
        return this.E;
    }

    // 返回与顶点 v 相邻的所有顶点
    public ArrayList<Integer> adj(int v) {
        validateVertex(v);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < this.V; i++) {
            if (this.matrix[v][i] == 1) {
                res.add(i);
            }
        }

        return res;
    }

    // 判断顶点 v 和 w 是否相邻
    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return this.matrix[v][w] == 1;
    }

    // 返回顶点 v 的度，即与顶点 v 相邻的顶点的个数
    public int degree(int v) {
        return adj(v).size();
    }

    // toString 不变，节省篇幅，省略
}

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

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

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

  • 空间复杂度：$O(V^2)$
  • 时间复杂度：
    • 建图：$O(E)$
    • 获得与顶点 $v$ 相邻的顶点：$O(V)$
    • 查看两个顶点是否相邻：$O(1)$

对于建图来说，因为我们必须扫描所有的边才能获得必要的信息，所以建图的时间复杂度最少也是 $O(E)$，无法再优化；而查看两个顶点是否相邻，时间复杂度为 $O(1)$，无需优化，那么我们看看空间复杂度和获得与顶点 $v$ 相邻的顶点的时间复杂度能否进行优化。

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

建立一个图，我们只需要知道一幅图的顶点信息以及边的信息即可，也就是说我们只需要 $O(V + E)$ 的空间复杂度就可以表示一幅图，对于稀疏图来说，由于图的每个顶点度的平均值远远小于节点数，而 $E$ 的大小等于平均度的值乘以节点数，即
$$
E = degree * V
$$
从而有
$$
degree \ll V \Rightarrow E \ll V^2
$$
得到
$$
O(V + E) \ll O(V^2)
$$
所以使用邻接矩阵表示图，对于稀疏矩阵来说，其实浪费了很多的空间，下面将介绍使用另一种方法表示图，无论是对于稀疏图还是稠密图，都可以有更好的性能。

邻接表

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

2020-10-01_182536

图中表格第一列表示顶点编号，顶点编号后的一行表示与该顶点相邻的顶点，例如对于第一行，表示与顶点 $0$ 相邻的顶点有顶点 $1$ 和 $2$。

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

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;

public class AdjList {
    private int E;
    private int V;
    // 对每一个顶点，使用一个链表来存储与它相邻的顶点
    private LinkedList<Integer>[] lists;

    public AdjList(String filename) {
        File file = new File(filename);
        Scanner scanner = null;
        try {
            scanner = new Scanner(file);
            this.V = scanner.nextInt();
            if (this.V < 0) {
                throw new IllegalArgumentException("V Must Be Positive");
            }

            // 初始化链表
            this.lists = new LinkedList[this.V];
            for (int i = 0; i < this.V; i++) {
                this.lists[i] = new LinkedList<>();
            }

            this.E = scanner.nextInt();
            if (this.E < 0) {
                throw new IllegalArgumentException("E Must Be Positive");
            }

            for (int i = 0; i < this.E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);

                if (a == b) {
                    throw new IllegalArgumentException("Self loop exists");
                }
                // 平行边的判断
                if (lists[a].contains(b)) {
                    throw new IllegalArgumentException("Parallel edge exists");
                }

                // 将相邻顶点添加到自己的链表中
                this.lists[a].add(b);
                this.lists[b].add(a);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            assert scanner != null;
            scanner.close();
        }
    }

    private void validateVertex(int v) {
        if (v < 0 || v >= this.V) {
            throw new IllegalArgumentException("Vertex " + v + " is invalid");
        }
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }

    public LinkedList<Integer> adj(int v) {
        validateVertex(v);
        // 直接返回顶点自己的链表即可
        return lists[v];
    }

    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return this.lists[v].contains(w);
    }

    public int degree(int v) {
        return adj(v).size();
    }
    
    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
        for (int v = 0; v < this.V; v++) {
            stringBuilder.append(String.format("%d : ", v));
            for (int w: adj(v)) {
                stringBuilder.append(String.format("%d ", w));
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        AdjList adjList = new AdjList("g.txt");
        System.out.println(adjList);
    }
}

输出为

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

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

  • 空间复杂度：$O(V + E)$
  • 时间复杂度：
    • 建表：$O(VE)$
    • 获得与顶点 $V$ 相邻的顶点：$O(degree)$
    • 判断两个顶点是否相邻：$O(degree)$

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

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

数据结构 查找时间复杂度
HashSet $O(1)$
TreeSet $O(\log v)$

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

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

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

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.TreeSet;

public class AdjSet {
    private int E;
    private int V;
    private TreeSet<Integer>[] sets;

    public AdjSet(String filename) {
        File file = new File(filename);
        Scanner scanner = null;
        try {
            scanner = new Scanner(file);
            this.V = scanner.nextInt();
            if (this.V < 0) {
                throw new IllegalArgumentException("V Must Be Positive");
            }

            // 初始化链表
            this.sets = new TreeSet[this.V];
            for (int i = 0; i < this.V; i++) {
                this.sets[i] = new TreeSet<>();
            }

            this.E = scanner.nextInt();
            if (this.E < 0) {
                throw new IllegalArgumentException("E Must Be Positive");
            }

            for (int i = 0; i < this.E; i++) {
                int a = scanner.nextInt();
                validateVertex(a);
                int b = scanner.nextInt();
                validateVertex(b);

                if (a == b) {
                    throw new IllegalArgumentException("Self loop exists");
                }
                // 平行边的判断
                if (sets[a].contains(b)) {
                    throw new IllegalArgumentException("Parallel edge exists");
                }

                // 将相邻顶点添加到自己的链表中
                this.sets[a].add(b);
                this.sets[b].add(a);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            assert scanner != null;
            scanner.close();
        }
    }

    private void validateVertex(int v) {
        if (v < 0 || v >= this.V) {
            throw new IllegalArgumentException("Vertex " + v + " is invalid");
        }
    }

    public int V() {
        return this.V;
    }

    public int E() {
        return this.E;
    }

    public TreeSet<Integer> adj(int v) {
        validateVertex(v);

        // 直接返回自己的链表即可
        return sets[v];
    }

    public boolean hasEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return this.sets[v].contains(w);
    }

    public int degree(int v) {
        return adj(v).size();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("V: %d, E: %d\n", this.V, this.E));
        for (int v = 0; v < this.V; v++) {
            stringBuilder.append(String.format("%d : ", v));
            for (int w: adj(v)) {
                stringBuilder.append(String.format("%d ", w));
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        AdjSet adjSet = new AdjSet("g.txt");
        System.out.println(adjSet);
    }
}

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

// AdjMatrix
public ArrayList<Integer> adj(int v) {
    validateVertex(v);
    ArrayList<Integer> res = new ArrayList<>();
    for (int i = 0; i < this.V; i++) {
        if (this.matrix[v][i] == 1) {
            res.add(i);
        }
    }

    return res;
}

// AdjList
public LinkedList<Integer> adj(int v) {
    validateVertex(v);
    return lists[v];
}

// AdjSet
public TreeSet<Integer> adj(int v) {
    validateVertex(v);
    return sets[v];
}

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

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

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

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

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

总结

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

空间 建图时间 两顶点是否相邻 查找顶点的邻边
邻接矩阵 $O(V^2)$ $O(E)$ $O(1)$ $O(V)$
邻接表(LinkedList) $O(V + E)$ $O(EV)$ $O(degree)$ $O(degree)$
邻接表(TreeSet) $O(V + E)$ $O(E\log V)$ $O(\log degree)$ $O(degree)$

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

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

public interface Graph {
    int V();
    int E();
    int degree(int v);
    boolean hasEdge(int v, int w);
    Iterable<Integer> adj(int v);
}