[그래프탐색][자료구조][java]BFS

그래프 탐색 방법 : DFS, BFS

BFS : 너비 우선 탐색

- 루트노드나 임의의 노드에서 시작하여 인접한 노드를 먼저 모두 확인한 다음 depth를 탐색

- Queue를 사용하여 데이터를 탐색 (FIFO 원칙)

- 재귀적으로 동작하지 않음

 

구현방법(인접행렬, 인접리스트)

1. 인접행렬(adjacent array)

package Basic_Algorithm.concept.그래프탐색;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Node{
    int start;
    int end;

    public Node(int start,int end){
        this.start=start;
        this.end=end;
    }
}
public class BFS_adjacentArray {
    static int edge;        //정점의 갯수
    static int vertex;      //간선의 갯수
    static int[][] graph;     //그래프에 점정간의 간선으로 연결된 정보를 가진 2차원 배열
    static boolean[] visited;   //정점에 방문 여부 boolean default값은 false

    public static void bfs(int start,int end){
        Queue<Node> queue=new LinkedList<>();
        queue.add(new Node(start,end));

        while(!queue.isEmpty()){
            Node node=queue.poll();
            System.out.println(node.start);

            for (int i = 0; i < graph.length; i++) {
                if(graph[node.start][i]==1 && visited[i]){
                    queue.add(new Node(i,end));
                    visited[i]=true;
                }
            }
        }

}
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        vertex= scan.nextInt();
        edge= scan.nextInt();
        graph=new int[vertex+1][vertex+1];
        visited=new boolean[vertex+1];

        //graph 정보를 담기 위한 코드
        for (int i = 0; i < edge; i++) {
            int start= scan.nextInt();
            int end= scan.nextInt();

            graph[start][end]=1;
            graph[end][start]=1;
        }
        // 정점 1부터 시작-> 정점 끝까지
        bfs(1,vertex);
    }
}

 

 

2.인접리스트

package Basic_Algorithm.concept.그래프탐색;

import java.util.*;

public class BFS_adjacentList {
    static ArrayList<Integer>[] arrayList;                    //정점간의 정보를 담을 배열안에 리스트 (index:정점번호, 안에 리스트로 연결된 정점값을 가진다.
    static boolean[] visited;                                 //방문한 정점의 정보를 true false로 저장
    static ArrayList<Integer> bfsList = new ArrayList<>();      //dfs를 통하여 방문한 정점 번호 순서를 담는 dfsList이다.
    static int vertex;  //정점의 갯수
    static int edge;    //간선의 갯수
    static int startVertex; //시작 정점 번호

    public static void bfs(int start){
        Queue<Integer> queue=new LinkedList<>();
        queue.add(start);
        visited[start]=true;

        while(!queue.isEmpty()){
            int end=queue.poll();
            System.out.print(end+" ");
            for(int c:arrayList[end]){
                if(!visited[c]){
                    visited[c]=true;
                    queue.add(c);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        vertex = scan.nextInt();
        edge = scan.nextInt();
        startVertex = scan.nextInt();

        arrayList = new ArrayList[vertex + 1];

        for (int i = 0; i < arrayList.length; i++) {
            arrayList[i] = new ArrayList<>();
        }

        visited = new boolean[vertex + 1];

        for (int i = 0; i < edge; i++) {
            int start = scan.nextInt();
            int end = scan.nextInt();

            arrayList[start].add(end);
            arrayList[end].add(start);
        }
        //간선에 연결된 리스트 정보를 번호 작은 순서대로 나타내기 위해 sort
        for (int i = 0; i < vertex + 1; i++) {
            Collections.sort(arrayList[i]);
        }

        //시작 정점 부터 dfs 탐색 시작
        bfs(startVertex);

        //순서 출력을 위한 코드
        for (Integer num : bfsList) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

}