Java数据结构-图的相关笔记总结_数据结构getedgenum函数

1. 基本介绍

图是一种数据结构，其中结点可以有零个或多个相邻元素，两个结点之间的连接称为边。结点也可以称为顶点。

关于图的常用概念：
路径：一个顶点到另一个顶点需要经历的边，如下图从B->E的路径有：
(1) B->D->E
(2) B->A->D->E

无向图：顶点之间的连接没有方向，比如A->B，也可以是B->A。
一个基本的无向图结构如下图所示：

有向图：顶点之间的连接有方向，比如从A到B的路径，只能是A->B，不能是B->A。有向图如图所示：

带权图：边上带有权值的图，带权图也叫网。带权图示例：

2. 图的表示方式

图的表示方式有两种：邻接矩阵（二维数组表示）和邻接表（链表表示）

2.1 邻接矩阵

2.1.1 基本介绍

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵的行（下标用i表示）、列（下标用j表示），(i,j)的值表示横坐标为i的点和纵坐标为j的点是否有连接，1表示有连接，0表示无连接。邻接矩阵示例：

说明：
标记为0的顶点与1顶点相关联，和5顶点不关联

2.1.2 代码实现

用代码实现邻接矩阵表示下面这个图：

完整代码：

public class Graph {

    /**
     * 顶点集合
     */
    private ArrayList<String> vertexList;
    /**
     * 存储图对应的邻接矩阵
     */
    private int[][] edges;
    /**
     * 边界的数量
     */
    private int edgeNum;

    public Graph(int n){
        vertexList=new ArrayList<>(n);
        edges=new int[n][n];
        edgeNum=0;
    }

    /**
     * 插入顶点到vertexList
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 顶点在edges的下标
     * @param v2
     * @param weight 1或0，1表示有连接，0表示无连接
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        edgeNum++;
    }

    /**
     * 返回结点的数量
     * @return
     */
    public int getVertexNum(){
        return vertexList.size();
    }

    /**
     * 得到图的边数量
     * @return
     */
    public int getEdgeNum(){
        return edgeNum;
    }

    /**
     * 通过下标获取结点对应的数据
     * @param index
     * @return
     */
    public String getVauleByIndex(int index){
        return vertexList.get(index);
    }

    /**
     * 返回v1和v2之间的权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2){
        return edges[v1][v2];
    }

    /**
     * 显示矩阵
     */
    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public static void main(String[] args) {
        String[] vertexes={"A","B","C","D","E"};
        int size=5;
        Graph graph = new Graph(size);
        //插入顶点
        for (String vertex : vertexes) {
            graph.insertVertex(vertex);
        }
        //添加边
        //A-B
        graph.insertEdge(0,1,1);
        //A-C
        graph.insertEdge(0,2,1);
        //B-C
        graph.insertEdge(1,2,1);
        //B-D
        graph.insertEdge(1,3,1);
        //B-E
        graph.insertEdge(1,4,1);
        graph.showGraph();
    }
}
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

查看控制台输出是否正确表示给出的图，如下

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
1
2
3
4
5

2.2 邻接表

2.2.1 基本介绍

邻接表由数组+链表组成，邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费。作为对比，因为邻接矩阵有n个顶点就需要为每个顶点都分配n个空间，由于大多数情况下，很多顶点不相连接，因此造成了内存空间浪费。

邻接表的示例图：

说明：标号为0的结点的相关联的结点为 1 、2、3、4；标号为1的结点的相关联结点为0、4；标号为2的结点相关联的结点为 0、4、5。

2.2.2 代码实现

用代码实现邻接表表示下面这个图：

顶点"A",“B”,“C”,“D”,“E”,分别使用0，1，2，3，4，5表示

新建类用于表示图的顶点

class VertexNode{
    public int data;
    public VertexNode next;

    public VertexNode(int data) {
        this.data = data;
    }

    public VertexNode(int data, VertexNode next) {
        this.data = data;
        this.next = next;
    }

    @Override
    public String toString() {
        return "VertexNode{" +
                "data=" + data+"}->";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

完成代码实现：

public class Graph {

    /**
     * 顶点集合
     */
    private ArrayList<String> vertexList;
    /**
     * 存储图对应的邻接矩阵
     */
    private VertexNode[] edges;
    /**
     * 边界的数量
     */
    private int edgeNum;

    public Graph02(int n){
        vertexList=new ArrayList<>(n);
        edges=new VertexNode[n];
        edgeNum=0;
    }

    /**
     * 插入顶点到vertexList
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }


    /**
     *插入边
     * @param index  数组下标
     * @param vertex 连接的顶点
     */
    public void insertEdge(int index,VertexNode vertex){
        if (edges[index]==null){
            edges[index]=vertex;
        }else{
            VertexNode temp=edges[index];
            while (temp.next!=null){
                temp=temp.next;
            }
            temp.next=vertex;
        }
    }

    /**
     *
     * @param v1 顶点1的下标
     * @param v2 顶点2的下标
     */
    public void insertEdge(int v1,int v2){
        insertEdge(v1,new VertexNode(v2));
        insertEdge(v2,new VertexNode(v1));
        edgeNum++;
    }

    /**
     * 返回结点的数量
     * @return
     */
    public int getVertexNum(){
        return vertexList.size();
    }

    /**
     * 得到图的边数量
     * @return
     */
    public int getEdgeNum(){
        return edgeNum;
    }

    /**
     * 通过下标获取结点对应的数据
     * @param index
     * @return
     */
    public String getVauleByIndex(int index){
        return vertexList.get(index);
    }

    /**
     * 返回顶点v1和顶点v2之间的权值，1表示有连接，0表示无连接
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2) {
        if (v1>=vertexList.size()||v2>=vertexList.size()){
            return 0;
        }
        if (edges[v1]==null){
            return 0;
        }
        VertexNode temp=edges[v1];
        while (temp!=null){
            if (temp.data==v2){
                return 1;
            }
            temp=temp.next;
        }
        return 0;
    }

    /**
     *
     */
    public void showVertexNode(VertexNode vertexNode){
        VertexNode temp=vertexNode;
        while (temp!=null){
            System.out.print(temp.toString());
            temp=temp.next;
        }
    }

    /**
     * 显示矩阵
     */
    public void showGraph(){
        int i=0;
        for (VertexNode edge : edges) {
            if (edge!=null){
                System.out.print(i++ +": ");
            }
            showVertexNode(edge);
            System.out.println();
        }
    }

    public static void main(String[] args) {
        String[] vertexes={"A","B","C","D","E"};
        int size=5;
        Graph graph = new Graph02(size);
        //插入顶点
        for (String vertex : vertexes) {
            graph.insertVertex(vertex);
        }
        //添加边
        //A-B,
        graph.insertEdge(0,1);
        //A-C
        graph.insertEdge(0,2);
        //B-C
        graph.insertEdge(1,2);
        //B-D
        graph.insertEdge(1,3);
        //B-E
        graph.insertEdge(1,4);
        System.out.println("该图的边的数量："+graph.getEdgeNum());
        System.out.println("该图的结点量："+graph.getVertexNum());
        graph.showGraph();
    }
}
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

控制台输出，查看是否正确表示出图：

该图的边的数量：5
改图的结点数量：5
0: VertexNode{data=1}->VertexNode{data=2}->
1: VertexNode{data=0}->VertexNode{data=2}->VertexNode{data=3}->VertexNode{data=4}->
2: VertexNode{data=0}->VertexNode{data=1}->
3: VertexNode{data=1}->
4: VertexNode{data=1}->
1
2
3
4
5
6
7

3. 图的遍历

所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略:
(1) 深度优先遍历
(2) 广度优先遍历

3.1 深度优先遍历（DFS）

3.1.1 基本介绍

深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。显然，深度优先搜索是一个递归的过程。

3.1.2 代码实现

以邻接矩阵作为图的表示，深度优先遍历算法实现步骤如下：
(1) 访问初始结点v，并标记结点v为已访问。
(2) 查找结点v的第一个未访问过的邻接结点w。
(3) 若w存在，则执行步骤4，如果w不存在，则回到第1步，将从v的下一个结点继续。
(4) 对w进行深度优先遍历递归（即把w当做另一个v)，然后进行步骤1、2、3。
(5) 遍历完v的第一个邻接结点w，查找结点v的下一个邻接结点，重复进行步骤3、4，直到遍历完所有的结点。

下面要使用邻接矩阵表示的图：

深度优先遍历实现的关键代码：

    /**
     * 从下标为0的顶点开始遍历
     */
    private void dfs(){
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i]= false;
        }
        //因为可能存在无连接的结点，所以需要遍历每个结点
        for (int i = 0; i < getVertexNum(); i++) {
            if (!isVisited[i]){
                dfs(i);
            }
        }
    }

    /**
     * 深度优先遍历算法
     * @param i 顶点的下标
     */
    private void dfs(int i){
        System.out.print(getValueByIndex(i)+"=>");
        //标记为已经访问过
        isVisited[i]=true;
        //查找下一个邻接结点w
        int w=getFirstNeighbor(i);
        while (w!=-1){
            //如果没有访问过,就继续往下遍历
            dfs(w);
            //如果w被访问过了，访问v下一个邻接结点
            w=getNextNeighbor(i,w);
        }
    }
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

完整代码：

public class Graph {

    /**
     * 顶点集合
     */
    private ArrayList<String> vertexList;
    /**
     * 存储图对应的邻接矩阵
     */
    private int[][] edges;
    /**
     * 边界的数量
     */
    private int edgeNum;
    /**
     * 结点是否被遍历到
     */
    private boolean[] isVisited;

    public Graph(int n){
        vertexList=new ArrayList<>(n);
        edges=new int[n][n];
        edgeNum=0;
        isVisited=new boolean[n];
    }

    /**
     * 插入顶点到vertexList
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 添加边
     * @param v1 顶点在edges的下标
     * @param v2
     * @param weight 1或0，1表示有连接，0表示无连接
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        edgeNum++;
    }

    /**
     * 从下标为0的顶点开始遍历
     */
    private void dfs(){
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i]= false;
        }
        //因为可能存在无连接的结点，所以需要遍历每个结点
        for (int i = 0; i < getVertexNum(); i++) {
            if (!isVisited[i]){
                dfs(i);
            }
        }
    }

    /**
     * 深度优先遍历算法
     * @param i 顶点的下标
     */
    private void dfs(int i){
        System.out.print(getValueByIndex(i)+"=>");
        //标记为已经访问过
        isVisited[i]=true;
        //查找下一个邻接结点w
        int w=getFirstNeighbor(i);
        while (w!=-1){
            //如果没有访问过,就继续往下遍历
            dfs(w);
            //如果w被访问过了，访问v下一个邻接结点
            w=getNextNeighbor(i,w);
        }
    }

    /**
     * 获取index的第一个未访问过的邻接结点
     * @param index
     * @return
     */
    private int getFirstNeighbor(int index) {
        for (int i = 0; i < edges.length; i++) {
            if (edges[index][i]>0&&!isVisited[i]){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据上一个邻接结点的下标edgeIndex，获取结点vertexIndex的下一个未访问过的邻接结点
     * @param vertexIndex
     * @param edgeIndex
     * @return
     */
    private int getNextNeighbor(int vertexIndex,int edgeIndex){
        for (int i = edgeIndex+1; i < edges.length; i++) {
            if (edges[vertexIndex][i]>0&&!isVisited[i]){
                return i;
            }
        }
        return -1;
    }

    /**
     * 返回结点的数量
     * @return
     */
    public int getVertexNum(){
        return vertexList.size();
    }

    /**
     * 得到图的边数量
     * @return
     */
    public int getEdgeNum(){
        return edgeNum;
    }

    /**
     * 通过下标获取结点对应的数据
     * @param index
     * @return
     */
    public String getValueByIndex(int index){
        return vertexList.get(index);
    }

    /**
     * 返回v1和v2之间的权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2){
        return edges[v1][v2];
    }

    /**
     * 显示矩阵
     */
    public void showGraph(){
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }

    public static void main(String[] args) {
        String[] vertexes={"1","2","3","4","5","6","7","8"};

        int size=8;
        Graph graph = new Graph(size);
        //插入顶点
        for (String vertex : vertexes) {
            graph.insertVertex(vertex);
        }
        //添加边
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);
        graph.showGraph();
        System.out.println("深度优先遍历：");
        graph.dfs();
    }
}
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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

控制台输出，图的邻接矩阵表示和深度优先遍历结果：

[0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0]
深度优先遍历：
1=>2=>4=>8=>5=>3=>6=>7=>
1
2
3
4
5
6
7
8
9
10

3.2 广度优先遍历(BFS)

3.2.1 基本介绍

图的广度优先搜索(Broad First Search) 。类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

3.2.2 代码实现

以邻接矩阵作为图的表示，广度优先遍历算法实现步骤如下：

(1)访问初始结点v并标记结点v为已访问。
(2)结点v入队列
(3)当队列非空时，继续执行，否则算法结束。
(4)出队列，取得队头结点u。
(5)查找结点u的第一个未访问过的邻接结点w。
(6)若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
6.1 访问结点w并标记为已访问。
6.2 结点w入队列
6.3 查找结点u的继邻接结点w后的下一个未访问的邻接结点w，转到步骤6。

要遍历的图和上面的深度遍历的图相同，广度优先遍历算法的关键代码如下：

  private void bfs(){
        for (int i = 0; i < isVisited.length; i++) {
            isVisited[i]= false;
        }
        //因为可能存在无连接的结点，所以需要遍历每个结点
        for (int i = 0; i < getVertexNum(); i++) {
            if (!isVisited[i]){
                bfs(i);
            }
        }
    }

    /**
     * 广度优先遍历
     * @param i
     */
    private void bfs(int i){
        //表示队列头节点对应的下标
        int u;
        //邻接结点w
        int w;
        //使用LinkedList做队列
        LinkedList<Integer> queue = new LinkedList<>();
        //标记为已访问
        isVisited[i]=true;
        System.out.print(getValueByIndex(i)+"=>");
        //将结点加入队列中
        queue.addLast(i);
        while (!queue.isEmpty()){
             //取出队列头节点的坐标
             u= queue.removeFirst();
             //得到第一个邻接结点
             w=getFirstNeighbor(u);
             //广度优先算法体现，遍历当前结点所有连接的结点，并添加到队列中
             while (w!=-1){
                 System.out.print(getValueByIndex(w)+"=>");
                 //标记为已经访问
                 isVisited[w]=true;
                 queue.addLast(w);
                 w=getNextNeighbor(u,w);
             }
        }
    }
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

控制台输出，图的邻接矩阵表示和广度优先遍历结果：

[0, 1, 1, 0, 0, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0]
广度优先遍历：
1=>2=>3=>4=>5=>6=>7=>8=>
1
2
3
4
5
6
7
8
9
10

笔记总结自：
https://www.bilibili.com/video/BV1E4411H73v
详细介绍深度优先遍历和广度优先遍历：
漫画：深度优先遍历和广度优先遍历