<Algorithm> 4. BFS

BFS

• 넓이 우선 탐색 --> DFS가 세로라고 생각하면 BFS는 가로탐색이다.  같은 넓이에 있는 정점들을 큐에 저장하고 한번에 출력한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

class Bfs{     ArrayList<Edge>[] graph;      boolean[] visited;           public Bfs(ArrayList<Edge>[] graph) {         // TODO Auto-generated constructor stub               this.graph=graph;          visited=new boolean[graph.length]; // 방문했는지 안했는지 확인                    for(int i=0;i<graph.length;i++){              if(!visited[i]){              bfs(i); // bfs 반복 호출              }          }                    }     public void bfs(int vertex){         visited[vertex]=true; // 방문함                   Queue<Integer> queue=new LinkedList<Integer>(); //방문정점을 저장할 큐 생성         queue.add(vertex);// 시작 정점 저장                  while(!queue.isEmpty()){             System.out.print(queue.remove()+" -> ");             // 큐에 들어있는 정점들 들어간 순서대로 출력                          for(Edge e:graph[vertex]){// 방문정점에 인접정점 반복                 if(!visited[e.adj_vertex]){                     queue.add(e.adj_vertex); // 인접정점 방문안했다면 큐에 저장                     visited[e.adj_vertex]=true; // 방문함                 }             }                      }         }      }   class Edge{     int adj_vertex;     public Edge(int adj_vertex) {         // TODO Auto-generated constructor stub      this.adj_vertex=adj_vertex;     }      } Colored by Color Scripter

cs