图的基本介绍和存储形式
为什么要学图
- 我们之前学习的线性表和树都存在一定局限性；
- 线性表局限于一个直接前驱和一个后继的关系；
- 树也只能有一个直接前驱，也就是父节点；
- 当我们需要表示多对多关系时，就需要使用到图；
图的举例说明
图是一种数据结构，其中节点可以具有零个或多个相邻元素。两个几点之间的连接称为边。节点也可以称为顶点。
图的常用概念
-
顶点(vertex)
-
边(edge)
-
路径
比如从D->C的路径有：
-
无向图
顶点之间的连接没有方向，比如A-B，既可以是A->B，也可以是B->A；
-
有向图
顶点之间的连接有方向，比如A-B，只能是A->B不能是B->A；
-
带权图
图的边上带有权值；
图的表示方式
图的表示方式有两种：二维数组表示(邻接矩阵)，链表表示(邻接表)；
邻接矩阵
邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵的row和col表示的是1…n个点；
0表示不能直连，1表示可以直连；
邻接表
- 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在的，会造成空间上的一定损失。
- 邻接表的实现只关心存在的边，不关心不存在的边；因此没有空间浪费，邻接表由数组+链表组成。
举例：
- 标号为0的节点的相关联节点为1，2，3，4；
- 标号为1的节点的相关联节点为0，4；
- …
图的创建图解和代码实现
思路图解
要求：代码实现下图的结构
1表示可以直连，0表示不能直连
|
A |
B |
C |
D |
E |
| A |
0 |
1 |
0 |
1 |
0 |
| B |
1 |
0 |
1 |
1 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
| D |
1 |
1 |
0 |
0 |
1 |
| E |
0 |
0 |
0 |
1 |
0 |
思路分析：
- 存储顶点
String，使用ArraysList；
- 保存矩阵
int[][] edges;
代码实现
代码
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
| package com.jokerdig.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class GraphDemo {
private List<String> vertexList;
private int[][] edges;
private int numOfEdges;
public static void main(String[] args) {
int n = 5;
String vertexVal[] = {"A","B","C","D","E"};
GraphDemo graph = new GraphDemo(n);
for (String value : vertexVal){
graph.insertVertex(value);
}
graph.insertEdge(0,1,1);
graph.insertEdge(0,3,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(3,4,1);
graph.showGraph();
}
public GraphDemo(int n){
edges = new int [n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
}
public int getNumOfVertex(){
return vertexList.size();
}
public int getNumOfEdges(){
return numOfEdges;
}
public String getValueByIndex(int i){
return vertexList.get(i);
}
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
public void showGraph(){
for(int[] link:edges){
System.out.println(Arrays.toString(link));
}
}
public void insertVertex(String vertex){
vertexList.add(vertex);
}
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
|
运行结果
1
2
3
4
5
6
7
| [0, 1, 0, 1, 0]
[1, 0, 1, 1, 0]
[0, 1, 0, 0, 0]
[1, 1, 0, 0, 1]
[0, 0, 0, 1, 0]
Process finished with exit code 0
|
图的深度优先(DFS)算法分析
图遍历介绍
图的遍历，即是对节点的访问。一个图有那么多个节点，如果遍历这些节点，需要特定策略，一般有两种访问策略：深度优先遍历，广度优先遍历。
图深度优先遍历基本思想
图的深度优先搜索(Depth First Search)
- 深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点；可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
- 我们可以看到，这样的访问策略是优先从纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问。
- 显然，深度优先搜索是一个递归的过程。
图深度优先遍历算法步骤
- 访问初始节点v，并标记节点v已经被访问。
- 查找节点v的第一个邻接节点w。
- 若w存在，则继续执行下方步骤，若w不存在，则回到步骤1，将从v的下一个节点继续。
- 若w未被访问，对w进行深度优先遍历递归(即把w当作另一个v，然后进行上方三个步骤)。
- 查找节点v的w邻接节点的下一个邻接节点，从步骤3开始。
题目的图例：
|
A |
B |
C |
D |
E |
| A |
0 |
1 |
0 |
1 |
0 |
| B |
1 |
0 |
1 |
1 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
| D |
1 |
1 |
0 |
0 |
1 |
| E |
0 |
0 |
0 |
1 |
0 |
图的深度优先(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
| package com.jokerdig.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class GraphDemo {
private List<String> vertexList;
private int[][] edges;
private int numOfEdges;
private boolean [] isVisited;
public static void main(String[] args) {
int n = 5;
String vertexVal[] = {"A","B","C","D","E"};
GraphDemo graph = new GraphDemo(n);
for (String value : vertexVal){
graph.insertVertex(value);
}
graph.insertEdge(0,1,1);
graph.insertEdge(0,3,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(3,4,1);
System.out.println("深度优先遍历");
graph.dfs();
}
public GraphDemo(int n){
edges = new int [n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
isVisited = new boolean[5];
}
public int getFirstNe(int index){
for (int j = 0; j <vertexList.size(); j++) {
if(edges[index][j]>0) {
return j;
}
}
return -1;
}
public int getNextNe(int v1,int v2){
for (int j = v2+1; j < vertexList.size(); j++) {
if(edges[v1][j]>0){
return j;
}
}
return -1;
}
private void dfs(boolean[] isVisited,int i){
System.out.print(getValueByIndex(i)+"->");
isVisited[i] = true;
int w = getFirstNe(i);
while(w!=-1) {
if(!isVisited[w]){
dfs(isVisited,w);
}
w = getNextNe(i,w);
}
}
public void dfs(){
for (int i = 0; i < getNumOfVertex(); i++) {
if(!isVisited[i]){
dfs(isVisited,i);
}
}
}
public int getNumOfVertex(){
return vertexList.size();
}
public int getNumOfEdges(){
return numOfEdges;
}
public String getValueByIndex(int i){
return vertexList.get(i);
}
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
public void showGraph(){
for(int[] link:edges){
System.out.println(Arrays.toString(link));
}
}
public void insertVertex(String vertex){
vertexList.add(vertex);
}
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
|
运行结果
1
2
3
4
| 深度优先遍历
A->B->C->D->E->
Process finished with exit code 0
|
图的广度优先(BFS)算法分析
图广度优先遍历基本思想
图的广度优先搜索(Broad First Search)
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，便于按照这个顺序来访问这些节点的邻接节点。
图广度优先遍历算法步骤
- 访问初始节点v，并标记节点v为已经访问。
- 节点v入队列。
- 当队列非空时，继续执行，否则节点v的算法结束。
- 出队列，取得队列头部节点u。
- 查找节点u的第一个邻接节点w。
- 若节点u的邻接节点w不存在，则转到步骤3，否则循环执行以下三个步骤：
- 若节点w尚未被访问， 则访问节点w并标记为已访问；
- 节点w入队列；
- 查找节点u的当前邻接节点w的下一个邻接节点，也记为w，并转到步骤6；
题目的图例：
|
A |
B |
C |
D |
E |
| A |
0 |
1 |
0 |
1 |
0 |
| B |
1 |
0 |
1 |
1 |
0 |
| C |
0 |
1 |
0 |
0 |
0 |
| D |
1 |
1 |
0 |
0 |
1 |
| E |
0 |
0 |
0 |
1 |
0 |
图的广度优先(BFS)代码实现
代码
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
177
178
179
180
181
| package com.jokerdig.graph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class GraphDemo {
private List<String> vertexList;
private int[][] edges;
private int numOfEdges;
private boolean [] isVisited;
public static void main(String[] args) {
int n = 5;
String vertexVal[] = {"A","B","C","D","E"};
GraphDemo graph = new GraphDemo(n);
for (String value : vertexVal){
graph.insertVertex(value);
}
graph.insertEdge(0,1,1);
graph.insertEdge(0,3,1);
graph.insertEdge(1,2,1);
graph.insertEdge(1,3,1);
graph.insertEdge(3,4,1);
System.out.println("广度优先遍历");
graph.bfs();
}
public GraphDemo(int n){
edges = new int [n][n];
vertexList = new ArrayList<String>(n);
numOfEdges = 0;
isVisited = new boolean[5];
}
public int getFirstNe(int index){
for (int j = 0; j <vertexList.size(); j++) {
if(edges[index][j]>0) {
return j;
}
}
return -1;
}
public int getNextNe(int v1,int v2){
for (int j = v2+1; j < vertexList.size(); j++) {
if(edges[v1][j]>0){
return j;
}
}
return -1;
}
private void dfs(boolean[] isVisited,int i){
System.out.print(getValueByIndex(i)+"->");
isVisited[i] = true;
int w = getFirstNe(i);
while(w!=-1) {
if(!isVisited[w]){
dfs(isVisited,w);
}
w = getNextNe(i,w);
}
}
public void dfs(){
for (int i = 0; i < getNumOfVertex(); i++) {
if(!isVisited[i]){
dfs(isVisited,i);
}
}
}
private void bfs(boolean[] isVisited,int i){
int u;
int w;
LinkedList queue = new LinkedList<>();
System.out.print(getValueByIndex(i)+"->");
isVisited[i] = true;
queue.addLast(i);
while(!queue.isEmpty()){
u = (Integer)queue.removeFirst();
w = getFirstNe(u);
while(w!=-1){
if(!isVisited[w]){
System.out.print(getValueByIndex(w)+"->");
isVisited[w] = true;
queue.addLast(w);
}
w = getNextNe(u,w);
}
}
}
public void bfs(){
for (int i = 0; i < getNumOfVertex(); i++) {
if(!isVisited[i]){
bfs(isVisited,i);
}
}
}
public int getNumOfVertex(){
return vertexList.size();
}
public int getNumOfEdges(){
return numOfEdges;
}
public String getValueByIndex(int i){
return vertexList.get(i);
}
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
public void showGraph(){
for(int[] link:edges){
System.out.println(Arrays.toString(link));
}
}
public void insertVertex(String vertex){
vertexList.add(vertex);
}
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
|
运行结果
1
2
3
4
| 广度优先遍历
A->B->D->C->E->
Process finished with exit code 0
|
DFS和BFS比较
应用实例
