图的表示方式及邻接矩阵实现

1 图的表示方式

图的 逻辑结构 采用顶点集合边集合来表示一个图。顶点之间没有任何次序关系,各条边之间也没有次序关系。然而,要表示并存储一个图,必须约定顶点的次序。约定如下:

  1. $V(G)$ 是 $n$ $(n>=0)$ 个顶点的有限集合,采用线性表 {$V_0, V_1, …V_{n-1}$} 表示和存储。约定一种顶点次序,用序号 i 唯一标识一个顶点 $V_i$。当添加图的一个顶点时,执行线性表尾插入,顶点序号依次递增。

  2. $E(G)$ 边集合包含图 G 所有顶点的边,按顶点次序可划分成若干子集:{$V_0$ 边的子集,$V_1$ 边的子集,…$V_{n-1}$ 边的子集}

    • 其中,每个子集(顶点 $V_i$ 的边集)可采用线性表 {$e_0, e_1, …e_{m-1}$} 表示和存储,每条边 $<V_i, V_j>$ 表示一对顶点 $V_i$ 和 $V_j$ 间的邻接关系,可用顶点序号 i、j 唯一标识,边的表示方式依赖于顶点次序。

    • 因此,$E (G)$ 边集合表达的每对顶点间的邻接关系,是一种二维线性关系,即矩阵。矩阵的存储方式有以下三种:

      • 边采用顺序存储结构,即二维数组,称为图的邻接矩阵。邻接矩阵的随机读写的时间复杂度为 $O(1)$,但在稀疏矩阵的场景下会浪费大量的空间,而且增删顶点或者矩阵扩容时需要移动大量的元素,效率更低;
      • 边采用链式存储结构,存储行的后继,即矩阵行的单链表,称为图的邻接表。邻接表只存储存在的边的数据,空间利用率更高,但是查询时需要遍历链表;
      • 边采用链式存储结构,存储行和列的后继,即矩阵十字链表,称为图的邻接多重表。邻接多重表实现较单链表更复杂一些,但在一定程度上优化了查询性能。

2 图的邻接矩阵表示

图的邻接矩阵 (Adjacency Matrix) 表示是指采用顺序表存储图的顶点集合,采用邻接矩阵存储图的边集合。邻接矩阵是表示图中各顶点之间邻接关系的矩阵。根据边是否带权值,邻接矩阵有以下两种定义。

2.1 不带权图的邻接矩阵

设图 $G=(V, E)$ 有 n 个顶点,E 可用一个图 G 的邻接矩阵 $A_n$ 描述,$A_n$ 的元素 $a_{ij}$ 表示图 G 中顶点 $V_i$ 到 $V_j$ 之间的邻接关系,若存在从顶点 $V_i$ 到 $V_j$ 的边,则 $a_{ij} = 1$,否则 $a_{ij} = 0$。$A_n = [a_{ij}]$ 定义如下:

不带权图的定义

示意图如下:

  • 无向图: 无向不带权图的邻接矩阵
  • 有向图: 有向不带权图的邻接矩阵

由图可知,无向图的邻接矩阵是对称的,有向图则不一定对称。

从邻接矩阵可得知顶点的度:

  • 在无向图中,顶点 $V_i$ 的度可以通过邻接矩阵的第 i 行或第 i 列上各元素之和来计算;
  • 对于有向图,顶点 $V_i$ 的出度可以通过邻接矩阵的第 i 行上各元素之和来计算,而入度可以通过邻接矩阵的第 i 列上各元素之和来计算。

2.2 带权图的邻接矩阵

带权图的邻接矩阵 $A_n = [a_{ij}]$ 定义如下:

带权图定义

其中,$w_{ij} (w_{ij} > 0)$ 表示边 $(v_i,v_j)$ 或 $<v_i,v_j>$ 的权值。

示意图如下:

  • 无向图: 带权无向图的邻接矩阵
  • 有向图: 带权有向图的邻接矩阵

3 图的邻接矩阵实现

图分为带权图与不带权图两种,这两种类型的图的实现方法基本一致,本文主要介绍带权图的实现方法。

3.1 抽象图类声明

首先我们声明抽象图类 AbstractGraph<T>,该抽象类用于描述图的顶点集合:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public abstract class AbstractGraph<T> {
    // 顶点顺序表,存储图的顶点集合
    protected List<T> vertexList;

    /**
     * 构造空图
     * @param length 指定顶点顺序表的容量
     */
    public AbstractGraph(int length) {
        vertexList = new ArrayList<>(length);
    }

    /**
     * 按照默认大小构造顶点数组
     */
    public AbstractGraph() {
        this(10);
    }

    @Override
    public String toString() {
        return "AbstractGraph{" +
                "vertexList=" + vertexList +
                '}';
    }

    // 返回顶点元素 Vi
    public T getVertex(int i) {
        return vertexList.get(i);
    }
    // 设置顶点 Vi 元素为 x
    public void setVertexList(int i, T x) {
        this.vertexList.set(i, x);
    }
    // 返回顶点个数
    public int vertexCount() {
        return vertexList.size();
    }

    // 抽象方法 ======================

    /**
     * 插入顶点
     * @param x 顶点元素
     * @return 顶点的序号
     */
    public abstract boolean insertVertex(T x);

    /**
     * 移除顶点
     * @param i 被移除的顶点序号
     */
    public abstract void removeVertex(int i);

    /**
     * 返回 <Vi,Vj> 的权值
     */
    public abstract int weight(int i, int j);

    /**
     * 返回 Vi 在 Vj 后的后继邻接顶点序号
     */
    public abstract int next(int i, int j);
}

3.2 邻接矩阵类型实现

上文讲过,图的邻接矩阵就是普通的二维数组,实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class Matrix {
    // 行与列值
    int rows, columns;
    // 如果是带权图,则 element 存储 0 ~ ∞ 之间的权值
    // 如果是不带权图,则 element 存储 0 或 1
    private int[][] element;

    /**
     * 构造 m x n 矩阵
     */
    public Matrix(int m, int n) {
        if (m <=0 || n <=0)
            throw new IllegalArgumentException("矩阵行列必须大于 0");
        this.rows = m;
        this.columns = n;
        this.element = new int[m][n];
    }

    /**
     * 构造 n x n 矩阵
     */
    public Matrix(int n) {
        this(n, n);
    }

    /**
     * 根据 value 初始化矩阵
     */
    public Matrix(int m, int n, int[][] value) {
        this(m, n);
        for (int i = 0; i < value.length && i < m; i++) {
            for (int j = 0; j < value[i].length && j < n; j++) {
                this.element[i][j] = value[i][j];
            }
        }
    }

    public int getRows() {
        return rows;
    }

    public int getColumns() {
        return columns;
    }

    public int get(int i, int j) {
        if (i < 0 || i >= rows || j < 0 || j >= columns)
            throw new IllegalArgumentException("数组越界");
        return element[i][j];
    }

    public void set(int i, int j, int v) {
        if (i < 0 || i >= rows || j < 0 || j >= columns)
            throw new IllegalArgumentException("数组越界");
        element[i][j] = v;
    }

    /**
     * 矩阵扩容,要求 m 与 n 更大
     */
    public void grow(int m, int n) {
        if (m < this.rows || n < this.columns)
            throw new IllegalArgumentException("扩容后的容量不应小于扩容前的");
        int[][] source = this.element;
        element = new int[m][n];
        for (int i = 0; i < this.rows; i++) {
            for (int j = 0; j < this.columns; j++) {
                this.element[i][j] = source[i][j];
            }
        }
        this.rows = m;
        this.columns = n;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("Matrix{" +
                "rows=" + rows +
                ", columns=" + columns +
                "}\n");
        for (int i = 0; i < this.rows; i++) {
            for (int j = 0; j < this.columns; j++) {
                stringBuilder.append(element[i][j]).append(" ");
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }
}

3.3 图的边类实现

为了方便对图类的操作,我们可以设置一个表示边的类型 Edge。图的边结构有三个元素,分别为“起点序号”、“终点序号”和“值”。如果“值”可以取任意大于等于 0 的数,则表示带权图的边,否则表示不带权图的边。实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Edge implements Comparable<Edge> {
    // 边的起点、终点、权值
    // 如果权值只能为 0、1,则表示不带权的边,否则为带权的边
    int row, column, weight;

    public Edge(int row, int column, int weight) {
        this.row = row;
        this.column = column;
        this.weight = weight;
    }

    /**
     * 比较两边的位置
     */
    @Override
    public int compareTo(Edge edge) {
        if (this.row == edge.row && this.column == edge.column)
            return 0;
        return (this.row < edge.row || (this.row == edge.row && this.column < edge.column)) 
                ? -1 : 1;
    }

    /**
     * 判断两边是否完全相等
     */
    public boolean equals(Edge edge) {
        return this.row == edge.row 
                && this.column == edge.column && this.weight == edge.weight;
    }

    /**
     * 相同位置的边加权
     */
    public void add(Edge edge) {
        if (compareTo(edge) == 0)
            this.weight += edge.weight;
        else 
            throw new IllegalArgumentException("两边位置不同,不能相加");
    }

    /**
     * 返回矩阵对称位置的边
     */
    public Edge toSymmetry() {
        return new Edge(this.column, this.row, this.weight);
    }
}

3.4 邻接矩阵表示的带权图类声明

声明邻接矩阵表示的带权图类 WeightedMatrixGraph<T>

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class WeightedMatrixGraph<T> extends AbstractGraph<T> {
    // 最大权值
    private static final int MAX_WEIGHT = Integer.MAX_VALUE;
    // 矩阵对象
    private Matrix matrix;

    /**
     * 构造空图
     * @param length 顶点顺序表容量以及邻接矩阵容量
     */
    public WeightedMatrixGraph(int length) {
        super(length);
        this.matrix = new Matrix(length);
    }

    /**
     * 构造空图,且默认容量为 10
     */
    public WeightedMatrixGraph() {
        this(10);
    }

    /**
     * 以顶点集合构造图,边数为 0
     */
    public WeightedMatrixGraph(T[] vertices) {
        this(vertices.length);
        for (T vertex : vertices)
            this.insertVertex(vertex);
    }

    /**
     * 以顶点集合,跟边集合构造图
     */
    public WeightedMatrixGraph(T[] vertices, Edge[] edges) {
        this(vertices);
        for (Edge edge : edges)
            this.insertEdge(edge);
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder(super.toString()).append("\nMatrix: \n");
        int n = this.vertexCount();
        stringBuilder.append("  ");
        for (int i = 0; i < n; i++) {
            stringBuilder.append("[").append(vertexList.get(i)).append("]");
        }
        stringBuilder.append("\n");
        for (int i = 0; i < n; i++) {
            stringBuilder.append("[").append(vertexList.get(i)).append("]");
            for (int j = 0; j < n; j++) {
                int weight = this.matrix.get(i, j);
                if (weight == MAX_WEIGHT) {
                    stringBuilder.append("∞  ");
                } else {
                    stringBuilder.append(weight).append("  ");
                }
            }
            stringBuilder.append("\n");
        }
        return stringBuilder.toString();
    }

    // 其他方法...
}

3.5 带权图的基础方法实现

3.5.1 边和顶点的插入操作

边的插入过程相对简单,直接根据 Edge 的行、列字段,将权值插入矩阵中的对应位置即可。实现如下:

1
2
3
4
5
6
7
8
9
private void insertEdge(Edge edge) {
    if (edge.row < 0 || edge.row >= vertexCount() 
            || edge.column < 0 || edge.column >= vertexCount())
        throw new IllegalArgumentException("数组越界");
    if (edge.weight <0 || edge.weight >= MAX_WEIGHT)
        throw new IllegalArgumentException("权值非法");
    
    this.matrix.set(edge.row, edge.column, edge.weight);
}

顶点的插入过程就是简单的链表尾插,但对于带权图,还需要将新顶点所在的行、列中非对角线位置的权值设置为 MAX_WEIGHT。实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public boolean insertVertex(T x) {
        try {
            this.vertexList.add(x);
            int i = vertexCount();
            if (i >= matrix.getRows()) {
                // 扩容
                matrix.grow(i + 1, i + 1);
            }
            for (int j = 0; j < i; j++) {
                // 设置非对角线位置为无穷大
                matrix.set(i, j, MAX_WEIGHT);
                matrix.set(j, i, MAX_WEIGHT);
            }
            return true;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

3.5.2 边和顶点的删除操作

边的删除过程相对简单,当待删除的位置的行列值不同时,将对应位置的权值设为 MAX_WEIGHT 即可:

1
2
3
4
public void removeEdge(int i, int j) {
    if (i != j)
        matrix.set(i, j, MAX_WEIGHT);
}

顶点的删除过程相对复杂一些:设 n 为原顶点数,当删除顶点顺序表中的 i 个元素时,需要先将 i+1 ~ n-1 范围的所有元素向前移动,再将邻接矩阵中第 i+1 ~ n-1 行的元素向上移动,最后将矩阵中第 i+1 ~ n-1 列元素向左移动。实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
@Override
public void removeVertex(int i) {
    int n = vertexCount();
    if (i < 0 || i >= n)
        throw new IllegalArgumentException("数组越界");
    // 先移除顶点,直接是用 ArrayList API
    this.vertexList.remove(i);
    // 上移矩阵行元素
    for (int j = i + 1; j < n; j++) {
        for (int k = 0; k < n; k++) {
            matrix.set(j - 1, k, matrix.get(j, k));
        }
    }
    // 左移矩阵列元素
    for (int j = 0; j < n; j++) {
        for (int k = i + 1; k < n; k++) {
            matrix.set(j, k - 1, matrix.get(j, k));
        }
    }
}

3.5.3 获得邻接矩阵顶点和边的权值操作

这两个方法是抽象类 AbstractGraph 中定义抽象方法,我们在实现类中直接实现即可:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
@Override
public int weight(int i, int j) {
    return matrix.get(i, j);
}

@Override
public int next(int i, int j) {
    int n = vertexCount();
    if (i < 0 || i >= n || j < 0 || j >= n)
        throw new IllegalArgumentException("数组越界");
    for (int k = j + 1; k < n; k++)
        if (matrix.get(i, k) > 0 && matrix.get(i, k) < MAX_WEIGHT)
            return matrix.get(i, k);
    return -1;
}

3.6 测试

我们创建以下矩阵,然后插入几个元素并打印,查看结果是否符合预期。实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public static void main(String[] args) {
    Character[] vertices = {'a', 'b', 'c', 'd', 'e'};
    Edge[] edges = {
            new Edge(0, 0, 1),
            new Edge(0, 1, 2),
            new Edge(2, 1, 3)
    };
    WeightedMatrixGraph<Character> graph = new WeightedMatrixGraph<>(vertices, edges);
    System.out.println(graph);
}

打印结果如下:

1
2
3
4
5
6
7
8
AbstractGraph{vertexList=[a, b, c, d, e]}
Matrix: 
   [a][b][c][d][e]
[a] 0  1  ∞  ∞  ∞  
[b] ∞  0  2  ∞  ∞  
[c] ∞  3  0  ∞  ∞  
[d] ∞  ∞  ∞  0  ∞  
[e] ∞  ∞  ∞  ∞  0

由上可知,我们成功在 (0, 1)(1, 2)(2, 1) 三个节点上插入了权值分别为 1、2、3 的三个边,且矩阵对角线上的值均为 0,非对角线上的默认值均为 ∞,符合带权图的性质。