国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁(yè) > 編程 > Java > 正文

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

2019-11-26 15:28:33
字體:
供稿:網(wǎng)友

本文以實(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 stubBFS 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 stubfor (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 stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// 初始化圖的節(jié)點(diǎn)private void addVertex(Object[] object) {// TODO Auto-generated method stubthis.vertices = object;}// 圖的初始化public BFS(int n) {// TODO Auto-generated constructor stubvexnum = 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 stubtemp.add(vertices[i]);System.out.print(vertices[i] + " ");}}
發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板: 民权县| 东乌| 花莲县| 武胜县| 合肥市| 辰溪县| 屯留县| 敖汉旗| 厦门市| 河西区| 安远县| 哈密市| 个旧市| 永城市| 南和县| 茂名市| 昔阳县| 务川| 汤阴县| 平安县| 湘阴县| 武清区| 上饶县| 叙永县| 庄浪县| 肃宁县| 灵台县| 台湾省| 江安县| 墨玉县| 潍坊市| 开化县| 武川县| 平凉市| 泗洪县| 普格县| 华亭县| 桑日县| 桦川县| 永泰县| 财经|