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

时间:2021-12-01 17:00:24

本文以实例形式讲述了基于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. package com.teradata.lsw.sort; 
  2.   
  3. import java.util.ArrayList; 
  4. import java.util.LinkedList; 
  5. import java.util.List; 
  6. import java.util.Queue; 
  7.   
  8. public class BFS { 
  9.   
  10. // 存储节点信息 
  11. private Object[] vertices; 
  12. // 存储边的信息数组 
  13. private int[][] arcs; 
  14. // 边的条数 
  15. private int vexnum; 
  16. // 记录第i个节点是否被访问过 
  17. private boolean[] visited; 
  18. //构建一个临时链表存已经遍历过的节点 
  19. private List<Object> temp = new ArrayList<Object>(); 
  20.   
  21. /** 
  22. * @param args 
  23. * 
  24. * @author TD_LSW 
  25. */ 
  26. public static void main(String[] args) { 
  27. // TODO Auto-generated method stub 
  28.   
  29. BFS g = new BFS(8); 
  30. Character[] vertices = { 'A''B''C''D''E''F''G''H' }; 
  31. g.addVertex(vertices); 
  32. g.addEdge(0, 1); 
  33. g.addEdge(0, 2); 
  34. g.addEdge(1, 3); 
  35. g.addEdge(1, 4); 
  36. g.addEdge(3, 5); 
  37. g.addEdge(4, 5); 
  38. g.addEdge(2, 6); 
  39. g.addEdge(2, 7); 
  40.   
  41. System.out.println("图的广度优先遍历:"); 
  42. g.bfs(); 
  43.   
  44. // 广度优先遍历实现 
  45. private void bfs() { 
  46. // TODO Auto-generated method stub 
  47. for (int i = 0; i < vexnum; i++) { 
  48. visited[i] = false
  49. Queue<Integer> q = new LinkedList<Integer>(); 
  50. for (int i = 0; i < vexnum; i++) { 
  51. if (!visited[i]) { 
  52. visited[i] = true
  53. visit(i); 
  54. q.add(i); 
  55. while (!q.isEmpty()) { 
  56. int j = (Integer) q.remove().intValue(); 
  57. //判断如果全部遍历完了就不需要循环了 
  58. if (temp.size() == vexnum) { 
  59. q.removeAll(q); 
  60. return
  61. for (int k = this.firstAdjVex(j); k >= 0; k = this 
  62. .nextAdjVex(j, k)) { 
  63. if (!visited[k]) { 
  64. q.add(k); 
  65. visited[k] = true
  66. visit(k); 
  67.   
  68.   
  69. // 查找下一个节点 
  70. public int firstAdjVex(int i) { 
  71. for (int j = 0; j < vexnum; j++) { 
  72. if (arcs[i][j] > 0) 
  73. return j; 
  74. return -1; 
  75.   
  76. public int nextAdjVex(int i, int k) { 
  77. for (int j = k + 1; j < vexnum; j++) { 
  78. if (arcs[i][j] > 0) 
  79. return j; 
  80. return -1; 
  81.   
  82. // 初始化图的边 
  83. private void addEdge(int i, int j) { 
  84. // TODO Auto-generated method stub 
  85. if (i == j) 
  86. return
  87. arcs[i][j] = 1; 
  88. arcs[j][i] = 1; 
  89.   
  90.   
  91. // 初始化图的节点 
  92. private void addVertex(Object[] object) { 
  93. // TODO Auto-generated method stub 
  94. this.vertices = object; 
  95.   
  96. // 图的初始化 
  97. public BFS(int n) { 
  98. // TODO Auto-generated constructor stub 
  99. vexnum = n; 
  100. vertices = new Object[n]; 
  101. arcs = new int[n][n]; 
  102. visited = new boolean[n]; 
  103. for (int i = 0; i < vexnum; i++) { 
  104. for (int j = 0; j < vexnum; j++) { 
  105. arcs[i][j] = 0; 
  106.   
  107. private void visit(int i) { 
  108. // TODO Auto-generated method stub 
  109. temp.add(vertices[i]); 
  110. System.out.print(vertices[i] + " "); 
  111.