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

本文以实例形式讲述了基于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的下一个邻接点

实现代码如下：

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] + " ");
}

}