1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.Scanner;
  4. public class Main{
  5. static int[][] edges;
  6. static ArrayList<Integer> vertexList;
  7. boolean[] isVisited;
  8. public Main(int n){
  9. edges = new int[n][n];
  10. vertexList = new ArrayList<>(n);
  11. isVisited = new boolean[n];
  12. }
  13. public int getFirst(int index){
  14. for (int i = 0;i<vertexList.size();i++){
  15. if (edges[index][i]>0){
  16. return i;
  17. }
  18. }
  19. return -1;
  20. }
  21. public int getNext(int v1,int v2){
  22. for (int i = v2+1;i<vertexList.size();i++){
  23. if (edges[v1][i]>0){
  24. return i;
  25. }
  26. }
  27. return -1;
  28. }
  29. public void bfs(boolean[] isVisited,int index){
  30. System.out.print(vertexList.get(index)+" ");
  31. isVisited[index] = true;
  32. LinkedList queue = new LinkedList();
  33. queue.addLast(index);
  34. while(!queue.isEmpty()){
  35. int u = (int)queue.poll();
  36. int w = getFirst(u);
  37. while (w!=-1){
  38. if(!isVisited[w]){
  39. System.out.print(vertexList.get(w)+" ");
  40. queue.addLast(w);
  41. isVisited[w] = true;
  42. }else {
  43. w = getNext(u,w);
  44. }
  45. }
  46. }
  47. }
  48. public void bfs(){
  49. for (int i = 0;i<vertexList.size();i++){
  50. if(!isVisited[i]){
  51. bfs(isVisited,i);
  52. }
  53. }
  54. }
  55. public static void main(String[] args) {
  56. Scanner sc = new Scanner(System.in);
  57. int n = sc.nextInt();
  58. Main m = new Main(n);
  59. for (int i = 0;i<n;i++){
  60. vertexList.add(i);
  61. }
  62. for (int i = 0;i<n;i++){
  63. for (int j = 0;j<n;j++){
  64. edges[i][j] = sc.nextInt();
  65. }
  66. }
  67. m.bfs();
  68. }
  69. }
点赞(0)
 

7 分

2 人评分

 

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论