基于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的下一个邻接点
实现代码如下：
packagecom.teradata.lsw.sort;
importjava.util.ArrayList;
importjava.util.LinkedList;
importjava.util.List;
importjava.util.Queue;
publicclassBFS{
//存储节点信息
privateObject[]vertices;
//存储边的信息数组
privateint[][]arcs;
//边的条数
privateintvexnum;
//记录第i个节点是否被访问过
privateboolean[]visited;
//构建一个临时链表存已经遍历过的节点
privateList<Object>temp=newArrayList<Object>();
/**
*@paramargs
*
*@authorTD_LSW
*/
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
BFSg=newBFS(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();
}
//广度优先遍历实现
privatevoidbfs(){
//TODOAuto-generatedmethodstub
for(inti=0;i<vexnum;i++){
visited[i]=false;
}
Queue<Integer>q=newLinkedList<Integer>();
for(inti=0;i<vexnum;i++){
if(!visited[i]){
visited[i]=true;
visit(i);
q.add(i);
while(!q.isEmpty()){
intj=(Integer)q.remove().intValue();
//判断如果全部遍历完了就不需要循环了
if(temp.size()==vexnum){
q.removeAll(q);
return;
}
for(intk=this.firstAdjVex(j);k>=0;k=this
.nextAdjVex(j,k)){
if(!visited[k]){
q.add(k);
visited[k]=true;
visit(k);
}
}
}
}
}
}
//查找下一个节点
publicintfirstAdjVex(inti){
for(intj=0;j<vexnum;j++){
if(arcs[i][j]>0)
returnj;
}
return-1;
}
publicintnextAdjVex(inti,intk){
for(intj=k+1;j<vexnum;j++){
if(arcs[i][j]>0)
returnj;
}
return-1;
}
//初始化图的边
privatevoidaddEdge(inti,intj){
//TODOAuto-generatedmethodstub
if(i==j)
return;
arcs[i][j]=1;
arcs[j][i]=1;
}
//初始化图的节点
privatevoidaddVertex(Object[]object){
//TODOAuto-generatedmethodstub
this.vertices=object;
}
//图的初始化
publicBFS(intn){
//TODOAuto-generatedconstructorstub
vexnum=n;
vertices=newObject[n];
arcs=newint[n][n];
visited=newboolean[n];
for(inti=0;i<vexnum;i++){
for(intj=0;j<vexnum;j++){
arcs[i][j]=0;
}
}
}
privatevoidvisit(inti){
//TODOAuto-generatedmethodstub
temp.add(vertices[i]);
System.out.print(vertices[i]+"");
}
}