算法习题06:图的广度优先遍历

图的广度优先遍历介绍

广度优先遍历算法步骤

代码实现

示例:

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
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
* 广度优先遍历
*
* @author:XMD
* @date: 31.7.22
*/
public class Bfs {
/**
* 存储顶点
*/
private ArrayList<String> vertexList;
/**
* 存储图对应的邻接矩阵
*/
private int[][] edges;
/**
* 表示边的数目
*/
private int numOfEdges;
/**
* 记录某个顶点是否被访问
*/
private boolean[] isVisited;


public static void main(String[] args) {
//结点个数
int n = 5;
//顶点值
String[] vertexs = {"A","B","C","D","E"};
//创建图对象
Bfs bfs = new Bfs(n);
//循环添加顶点
for (String vertex : vertexs) {
bfs.insertVertex(vertex);
}
//添加边
//A-B A-C B-C B-D B-E
bfs.insertEdge(0,1,23);
bfs.insertEdge(0,2,12);
bfs.insertEdge(1,2,34);
bfs.insertEdge(1,3,56);
bfs.insertEdge(1,4,41);

//显式邻接矩阵
bfs.showGraph();

bfs.bfs();
}

/**
* 对一个结点进行广度优先遍历
* @param isVisited
* @param i
*/
private void bfs(boolean[] isVisited, int i){
//表示队列的头结点对应下标
int u;
//邻接结点
int w;
//队列,记录结点访问的顺序
LinkedList queue = new LinkedList();
//访问结点,输出结点信息
System.out.print(getVertexByIndex(i) + "=>");
//标记为已访问
isVisited[i] = true;
//将结点假如队列
queue.addLast(i);
if (!queue.isEmpty()){
//取出队列的头结点下标
u = (Integer) queue.removeFirst();
//得到第一个邻接结点的下标W
w =getFirstNeighbor(u);
if (w != -1){
if (!isVisited[w]){
System.out.print(getVertexByIndex(w) + ">");
isVisited[w] = true;
queue.addLast(w);
}
w = getNextNeighbor(u,w);
}
}
}

public void bfs(){
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]){
bfs(isVisited,i);
}
}
}


/**
* 得到第一个邻接结点的下标
* @param index
* @return
*/
public int getFirstNeighbor(int index){
for (int i = 0; i < vertexList.size(); i++) {
if (edges[index][i] > 0){
return i;
}
}
return -1;
}

/**
* 根据前一个邻接结点的下标获取下一个邻接结点
* @param v1
* @param v2
* @return
*/
public int getNextNeighbor(int v1,int v2){
for (int i = v2 + 1; i < vertexList.size(); i++) {
if (edges[v1][i] > 0){
return i;
}
}
return -1;
}



/**
* 构造器
* @param n 顶点个数
*/
public Bfs(int n){
//初始化矩阵和vertexList
vertexList = new ArrayList<>(n);
edges = new int[n][n];
isVisited = new boolean[n];
}


/**
* 返回结点个数
* @return
*/
public int getNumOfVertex(){
return vertexList.size();
}

/**
* 返回边的数目
* @return
*/
public int getNumOfEdges(){
return numOfEdges;
}

/**
* 返回下标所对应的值
* @param index
* @return
*/
public String getVertexByIndex(int index){
return vertexList.get(index);
}

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

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

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


/**
* 添加边
* @param v1 第一个顶点的下标 (第几个顶点)
* @param v2 第二个顶点的下标
* @param weight 两个顶点之间的距离
*/
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}

}

广度优先遍历与深度优先遍历的区别

-------------本文结束感谢您的阅读-------------