基于Java实现的图的广度优先遍历算法

内容摘要
本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法，具体方法如下：
用邻接矩阵存储图方法：
1.确定图的顶点个数和边的个数



2.输入顶点信息存储在一维数组vertex中
文章正文

本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法，具体方法如下：

用邻接矩阵存储图方法：

1.确定图的顶点个数和边的个数

2.输入顶点信息存储在一维数组vertex中

3.初始化邻接矩阵；

4.依次输入每条边存储在邻接矩阵arc中

输入边依附的两个顶点的序号i,j；
将邻接矩阵的第i行第j列的元素值置为1；
将邻接矩阵的第j行第i列的元素值置为1；

广度优先遍历实现：

1.初始化队列Q
2.访问顶点v；visited[v]=1;顶点v入队Q;
3.while(队列Q非空)

v=队列Q的队头元素出队；
w=顶点v的第一个邻接点
while(w存在)

如果w未被访问，则访问顶点w;visited[w]=1;顶点w入队列Q

w=顶点v的下一个邻接点

实现代码如下：

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 com.teradata.lsw.sort;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
public class BFS {
 
// 存储节点信息
private Object[] vertices;
// 存储边的信息数组
private int[][] arcs;
// 边的条数
private int vexnum;
// 记录第i个节点是否被访问过
private boolean[] visited;
//构建一个临时链表存已经遍历过的节点
private List<Object> temp = new ArrayList<Object>();
 
/**
* @param args
*
* @author TD_LSW
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
 
BFS g = new BFS(8);
Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
g.addVertex(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
g.addEdge(2, 6);
g.addEdge(2, 7);
 
System.out.println("图的广度优先遍历：");
g.bfs();
}
 
// 广度优先遍历实现
private void bfs() {
// TODO Auto-generated method stub
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
Queue<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < vexnum; i++) {
if (!visited[i]) {
visited[i] = true;
visit(i);
q.add(i);
while (!q.isEmpty()) {
int j = (Integer) q.remove().intValue();
//判断如果全部遍历完了就不需要循环了
if (temp.size() == vexnum) {
q.removeAll(q);
return;
}
for (int k = this.firstAdjVex(j); k >= 0; k = this
.nextAdjVex(j, k)) {
if (!visited[k]) {
q.add(k);
visited[k] = true;
visit(k);
}
}
}
}
}
 
}
 
// 查找下一个节点
public int firstAdjVex(int i) {
for (int j = 0; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}
 
public int nextAdjVex(int i, int k) {
for (int j = k + 1; j < vexnum; j++) {
if (arcs[i][j] > 0)
return j;
}
return -1;
}
 
// 初始化图的边
private void addEdge(int i, int j) {
// TODO Auto-generated method stub
if (i == j)
return;
arcs[i][j] = 1;
arcs[j][i] = 1;
 
}
 
// 初始化图的节点
private void addVertex(Object[] object) {
// TODO Auto-generated method stub
this.vertices = object;
}
 
// 图的初始化
public BFS(int n) {
// TODO Auto-generated constructor stub
vexnum = n;
vertices = new Object[n];
arcs = new int[n][n];
visited = new boolean[n];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
arcs[i][j] = 0;
}
}
}
 
private void visit(int i) {
// TODO Auto-generated method stub
temp.add(vertices[i]);
System.out.print(vertices[i] + " ");
}
 
}
代码注释
上一篇Android中使用Matrix控制图形变换和制作倒影效果的方法下一篇win10系统中proe5.0鼠标中键滚轮滑动不能放大缩小怎么办?

作者：喵哥笔记

IDC笔记

学的不仅是技术，更是梦想！