图的广度优先遍历算法（BFS）

  1 import java.util.ArrayList;
  2 import java.util.Arrays;
  3 import java.util.LinkedList;
  4 
  5 
  6 public class Graph {
  7 
  8     //创建一个集合用来存放顶点
  9     private ArrayList<String> arrayList;
 10     //创建一个二位数组来作为邻接矩阵
 11     private int[][] TwoArray;
 12     //边的数目
 13     private int numOfEdges;
 14     //使用一个数组记录节点是否被访问过
 15     private boolean[] isVisted;
 16     public static void main(String[] args) {
 17         Graph graph = new Graph(5);
 18         //测试
 19         String[] ver={"A","B","C","D","E"};
 20         //将节点放到集合中
 21         for (String s : ver) {
 22          graph.InsertVex(s);
 23         }
 24         //设置边
 25         //A-B A-C B-C B-D B-E
 26         graph.InsertEdeges(0,1,1);
 27         graph.InsertEdeges(0,2,1);
 28         graph.InsertEdeges(1,2,1);
 29         graph.InsertEdeges(1,3,1);
 30         graph.InsertEdeges(1,4,1);
 31         //显示
 32         graph.Show();
 33         graph.BFS();
 34     }
 35 
 36     //初始化数据
 37     public Graph(int n){
 38         arrayList=new ArrayList<>(n);
 39         TwoArray=new int[n][n];
 40         numOfEdges=0;
 41         isVisted=new boolean[n];
 42     }
 43 
 44     /**
 45      * 根据节点的下标返回第一个邻接节点的下标
 46      * @param index 节点的下标
 47      * @return
 48      */
 49     public int getFirstVex(int index){
 50         for (int i = 0; i < arrayList.size(); i++) {
 51             if(TwoArray[index][i]!=0){
 52                 return i;
 53             }
 54         }
 55         return -1;
 56     }
 57 
 58     /**
 59      * 根据前一个节点下标获取下一个节点的下标
 60      * @param v1 找到的第一个节点的
 61      * @param v2 找到的第一个邻接节点并且被访问过的
 62      * @return
 63      */
 64     public int getNextVex(int v1,int v2){
 65         for (int i = v2+1; i < numEdges(); i++) {
 66             if(TwoArray[v1][i]!=0){
 67                 return i;
 68             }
 69         }
 70         return -1;
 71     }
 72 
 73     /**
 74      * 广度优先遍历
 75      * @param isVisted 记录是否被访问过的数组
 76      * @param i 想要访问的节点下标
 77      */
 78     public void BFS(boolean[] isVisted,int i){
 79        //表示队列头节点的下标
 80         int u;
 81         //用于存放队列头节点的第一个邻接节点
 82         int w;
 83         //定义一个队列用来存放节点
 84         LinkedList<Object> queue = new LinkedList<>();
 85         //访问该节点
 86         System.out.print(getValue(i)+"->");
 87         //在数组中标记为该下标已经被访问过了
 88         isVisted[i]=true;
 89         //把访问过的节点下标放到队列中，放到队列的尾部
 90         queue.addLast(i);
 91         //判断队列是否为空
 92         while (!queue.isEmpty()){
 93             //队列不为空，那么取出队列的头节点的下标
 94             u=(Integer) queue.removeFirst();
 95             //获取头节点的第一个邻接节点的下标
 96             w = getFirstVex(u);
 97             //判断该节点是否存在
 98             while (w!=-1){
 99                 //说明存在，在判断是否被访问过
100                 if(!isVisted[w]){
101                     //没有访问过，标记为已访问
102                     isVisted[w]=true;
103                     //输出
104                     System.out.print(getValue(w)+"->");
105                     //访问完加入队列中
106                     queue.addLast(w);
107                 }
108                 //以u作为前驱节点，w作为u刚刚访问过的节点，来查找w的下一个邻接节点
109                 w = getNextVex(u, w);
110             }
111         }
112     }
113 
114     public void BFS(){
115         for (int i = 0; i < arrayList.size(); i++) {
116             if(!isVisted[i]){
117                 BFS(isVisted,i);
118             }
119         }
120     }
121 
122     /**
123      * 添加节点
124      * @param vex
125      */
126     public void InsertVex(String vex){
127         arrayList.add(vex);
128     }
129 
130     /**
131      * 设置边
132      * @param v1 第一个节点对应的下标
133      * @param v2  第二节点对应的下标
134      * @param weight 两个节点对应的权值
135      */
136     public void InsertEdeges(int v1,int v2,int weight){
137         TwoArray[v1][v2]=weight;
138         TwoArray[v2][v1]=weight;
139         numOfEdges++;
140     }
141 
142     /**
143      * 返回节点对应的个数
144      * @return
145      */
146     public int numVex(){
147         return arrayList.size();
148     }
149 
150     /**
151      * 返回边的总个数
152      * @return
153      */
154     public int numEdges(){
155         return numOfEdges;
156     }
157 
158     /**
159      * 显示邻接矩阵（图的展示）
160      */
161     public void Show(){
162         for (int[] ints : TwoArray) {
163             System.out.println(Arrays.toString(ints));
164         }
165     }
166 
167     /**
168      * 根据下标获取对应的数据
169      * @param i 下标
170      * @return
171      */
172     public String getValue(int i){
173         return arrayList.get(i);
174     }
175 
176     public int getWeight(int v1,int v2){
177         int weight=TwoArray[v1][v2];
178         return weight;
179     }
180 }