基于Java實(shí)現(xiàn)的圖的廣度優(yōu)先遍歷算法

更新時(shí)間：2014年07月23日 16:04:15 投稿：shichen2014

這篇文章主要介紹了基于Java實(shí)現(xiàn)的圖的廣度優(yōu)先遍歷算法,需要的朋友可以參考下

本文以實(shí)例形式講述了基于Java的圖的廣度優(yōu)先遍歷算法實(shí)現(xiàn)方法，具體方法如下：

用鄰接矩陣存儲(chǔ)圖方法：

1.確定圖的頂點(diǎn)個(gè)數(shù)和邊的個(gè)數(shù)

2.輸入頂點(diǎn)信息存儲(chǔ)在一維數(shù)組vertex中

3.初始化鄰接矩陣；

4.依次輸入每條邊存儲(chǔ)在鄰接矩陣arc中

輸入邊依附的兩個(gè)頂點(diǎn)的序號(hào)i,j；
將鄰接矩陣的第i行第j列的元素值置為1；
將鄰接矩陣的第j行第i列的元素值置為1；

廣度優(yōu)先遍歷實(shí)現(xiàn)：

1.初始化隊(duì)列Q
2.訪問頂點(diǎn)v；visited[v]=1;頂點(diǎn)v入隊(duì)Q;
3.while(隊(duì)列Q非空)

v=隊(duì)列Q的隊(duì)頭元素出隊(duì)；
w=頂點(diǎn)v的第一個(gè)鄰接點(diǎn)
while(w存在)

如果w未被訪問，則訪問頂點(diǎn)w;visited[w]=1;頂點(diǎn)w入隊(duì)列Q

w=頂點(diǎn)v的下一個(gè)鄰接點(diǎn)

實(shí)現(xiàn)代碼如下：

package com.teradata.lsw.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {

// 存儲(chǔ)節(jié)點(diǎn)信息
private Object[] vertices;
// 存儲(chǔ)邊的信息數(shù)組
private int[][] arcs;
// 邊的條數(shù)
private int vexnum;
// 記錄第i個(gè)節(jié)點(diǎn)是否被訪問過
private boolean[] visited;
//構(gòu)建一個(gè)臨時(shí)鏈表存已經(jīng)遍歷過的節(jié)點(diǎn)
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("圖的廣度優(yōu)先遍歷：");
g.bfs();
}

// 廣度優(yōu)先遍歷實(shí)現(xiàn)
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();
//判斷如果全部遍歷完了就不需要循環(huán)了
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);
}
}
}
}
}

}

// 查找下一個(gè)節(jié)點(diǎn)
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;

}

// 初始化圖的節(jié)點(diǎn)
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] + " ");
}

}

您可能感興趣的文章: