数据结构——图（一）

数据结构与算法——图（一）

继上一次的数据结构学完后，很快就学习了图，学习这种东西真的是奇怪，学到了就有成就感了，有成就感就上瘾，今天就总结一下所学到的图的相关知识。大概就关于图是什么样的、图的概念、图的遍历这些。

图的概念

首先我们应该了解无向图、有向图、度、顶点、边相关概念，什么是顶点？顶点就是图中的数据元素，线性表中称为元素，树中成为节点。将每一个顶点连接起来的线叫做边，图中一个节点最大边数，称为图的度，与树的度一样。知道了这几个最基本的概念，我们就可以来看看整个图长什么样了，图分为有向图和无向图：

无向图

有向图

从上面两张图可以看到这两类图的样子，无向图就是节点到节点间没有方向，有向图就是节点到节点间是有方向的，有向图中带方向的边可分为出度和入度，出度就是从该节点向其他节点的边，入度则是从其他节点到该节点的边。概念很容易搞懂，这也是图目前来说算是比较简单的地方。

那么怎么创建一个图呢？其实图只需要一个数组就存储其顶点，用一个邻接矩阵来表示顶点与顶点之间的关系。让我们来看看下面这张图。

矩阵示例图

这张图是从参考视频中获取的，矩阵的第一行代表这个第一个顶点到其他顶点的边，0通常为该顶点到该顶点的权值，无穷符号代表没有这个边，其他常数代表该顶点到第n个顶点的权值。为了方便理解，我们也可以认为是顶点到顶点的距离，这样更便于我们认识它。

因此，初始化一个图比较简单，如下代码：

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
package graph;

import java.util.LinkedList;

public class DirectedGraphs<T extends Comparable<T>> {

    public static void main(String[] args) {
        Integer[] vertex = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int[][] matrix = new int[][] {
                { 0, 3, MAX_WEIGHT, MAX_WEIGHT, 6, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { 3, 0, 4, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { MAX_WEIGHT, 4, 0, 7, MAX_WEIGHT, MAX_WEIGHT, 17, MAX_WEIGHT, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, 7, 0, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { 6, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0, 10, MAX_WEIGHT, 1, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 10, 0, 12, 9, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, 17, MAX_WEIGHT, MAX_WEIGHT, 12, 0, MAX_WEIGHT, 2 },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 1, 9, MAX_WEIGHT, 0, 14 },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, 14, 0 },
        };
        DirectedGraphs<Integer> graphs = new DirectedGraphs<>(vertex, matrix);
        System.out.println("权值: " + graphs.getWeight(1, 2));
    }

    public static final int MAX_WEIGHT = 100000;
    private T[] vertex;
    private int[][] matrix;

    public DirectedGraphs(T[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    public int getWeight(T start, T end) {
        int startIndex = -1, endIndex = -1;
        int weight = -1;
        for (int i = 0; i < this.vertex.length; i++) {
            if (start.compareTo(this.vertex[i]) == 0) {
                startIndex = i;
            }
            if (end.compareTo(this.vertex[i]) == 0) {
                endIndex = i;
            }
        }
        if (startIndex != -1 && endIndex != -1) {
            for (int i = startIndex + 1; i <= endIndex; i++) {
                int w = this.matrix[startIndex][i];
                if (w != MAX_WEIGHT) {
                    weight += w;
                }
            }
        }
        return weight;
    }

    public int size() {
        return vertex.length;
    }

}

这段代码非常简单，将图的顶点放入数组，将其关系用邻接矩阵写好后直接放入就算是创建好了一张图。其中还实现了一个获取某个点到某个点的权值，这个方法计算了两个顶点之间的权值，这里面的关键点就在于理解这个邻接矩阵的含义。

图的遍历

图的遍历又有很多种算法，这里主要介绍深度遍历和广度遍历，在树的结构中有着相同的东西，对应为前序遍历和层次遍历。下面这段代码在上面的实现上加上了深度遍历与广度遍历及其辅助方法。代码如下：

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package graph;

import java.util.LinkedList;

public class DirectedGraphs<T extends Comparable<T>> {

    public static void main(String[] args) {
        Integer[] vertex = new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int[][] matrix = new int[][] {
                { 0, 3, MAX_WEIGHT, MAX_WEIGHT, 6, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { 3, 0, 4, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { MAX_WEIGHT, 4, 0, 7, MAX_WEIGHT, MAX_WEIGHT, 17, MAX_WEIGHT, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, 7, 0, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT },
                { 6, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0, 10, MAX_WEIGHT, 1, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 10, 0, 12, 9, MAX_WEIGHT },
                { MAX_WEIGHT, MAX_WEIGHT, 17, MAX_WEIGHT, MAX_WEIGHT, 12, 0, MAX_WEIGHT, 2 },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 1, 9, MAX_WEIGHT, 0, 14 },
                { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 2, MAX_WEIGHT, 14, 0 },
        };
        DirectedGraphs<Integer> graphs = new DirectedGraphs<>(vertex, matrix);
        graphs.broadFirstSearch();
        graphs.depthFirstSearch();
    }

    public static final int MAX_WEIGHT = 100000;
    private T[] vertex;
    private int[][] matrix;
    private boolean[] isVisited;

    public DirectedGraphs(T[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
    }

    private void initVisited() {
        this.isVisited = new boolean[this.vertex.length];
    }

    public void broadFirstSearch() {
        initVisited();
        for (int i = 0; i < this.vertex.length; i++) {
            if (!isVisited[i]) {
                broadFirstSearch(i);
            }
        }
        initVisited();
    }

    public void depthFirstSearch() {
        initVisited();
        for (int i = 0; i < this.vertex.length; i++) {
            if (!isVisited[i]) {
                System.out.println("位置: " + i + " 数据: " + this.vertex[i]);
                depthFirstSearch(i);
            }
        }
        initVisited();
    }

    private void broadFirstSearch(int index) {
        T u, w;
        LinkedList<T> queue = new LinkedList<>();
        System.out.println("位置: " + index + " 数据: " + vertex[index]);
        isVisited[index] = true;
        queue.add(vertex[index]);
        while (!queue.isEmpty()) {
            u = queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != null) {
                int i = getVertexIndex(w);
                if (!isVisited[i]) {
                    System.out.println("位置: " + i + " 数据: " + vertex[i]);
                    isVisited[i] = true;
                    queue.add(w);
                }
                w = getNextNeighbor(u, w);
            }
        }
    }

    private void depthFirstSearch(int index) {
        this.isVisited[index] = true;
        T t = getFirstNeighbor(this.vertex[index]);
        while (t != null) {
            int i = getVertexIndex(t);
            if (!isVisited[i]) {
                this.isVisited[i] = true;
                System.out.println("位置: " + i + " 数据: " + this.vertex[i]);
                depthFirstSearch(getVertexIndex(t));
            }
            t = getNextNeighbor(this.vertex[index], t);
        }
    }

    public T getFirstNeighbor(T vertex) {
        int index = getVertexIndex(vertex);
        if (index != -1) {
            int[] arr = this.matrix[index];
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] != 0 && arr[i] != MAX_WEIGHT) {
                    return this.vertex[i];
                }
            }
        }
        return null;
    }

    public T getNextNeighbor(T vertex, T start) {
        int vertexIndex = getVertexIndex(vertex);
        if (vertexIndex != -1) {
            int startIndex = getVertexIndex(start);
            int[] arr = this.matrix[vertexIndex];
            for (int i = startIndex + 1; i < arr.length; i++) {
                if (arr[i] != 0 && arr[i] != MAX_WEIGHT) {
                    return this.vertex[i];
                }
            }
        }
        return null;
    }

    public int getVertexIndex(T vertex) {
        for (int i = 0; i < this.vertex.length; i++) {
            if (this.vertex[i].compareTo(vertex) == 0) {
                return i;
            }
        }
        return -1;
    }

}

为了方便看这里将无向图带下来，由于图是闭环的，我们要知道哪个顶点是已经遍历过的，否则将会产生重复访问的问题，并且永远也退不出循环。因此在这里使用了boolean数组来存储已经访问过的顶点。深度遍历depthFirstSearch，简称DFS，这里从数组的第一个顶点开始遍历，既然是深度优先，那么应该是从第一个临点遍历完之后，再遍历其他的临点。如图所示的图的深度遍历结果即为123476589，产生这样的结果的原因是因为存储顶点的数组为{1, 2, 3, 4, 5, 6 ,7, 8, 9}，因此4是3的第一个临点，6是7的第一个临点，5是6的第一个临点。只要第一个临点没访问过，就完成访问并且迭代继续往这个临点的第一个临点前进，直到所以顶点的第一个临点都走完了，再一个个顺序走其他临点。如图所示：

深度遍历

下面这张图描述了图的广度遍历，与树的层次遍历类似，它是先将所有的临点遍历，将这些临点放入队列，再继续将其全部临点遍历入队，重复此操作，直到将所有的点遍历完。直接理解起来还是挺简单的，下图的广度遍历结果为125368479，其遍历图解如下图：

广度遍历

广度遍历利用队列来存储节点，以确保每个节点的所有节点都遍历完成，再依次重复此操作达到广度优先的效果。图是比较复杂的数据结构，很多关于路径的算法都是用到了图，现在所学的还属于比较简单的层次。本人第一次学习图相关的数据结构，文中有表述不到位或者表述不当的地方，可以联系我，大家一起共同学习共同进步！

数据结构与算法
#数据结构
数据结构——图（一）
http://devonte.top/posts/blog/datastructure/Data_Structure__Algorithm__Graph__0.html
作者
Vector
发布于
2020年9月11日
许可协议