인접 행렬, 리스트를 활용한 BFS

인접 행렬

즉, 선이 많을때는 인접행렬을, 그렇지 않을때는 둘다 매우 많을때는 인접 리스트로 구현하자.

 

 이게, List로 배열을 만들어 쓰는 예시이다. 

 

public static int BFS(int [][]graph, int n)
    {
        Queue<Integer> q = new LinkedList<>();
        boolean [] visited = new boolean[n+1];
        int cnt = 1;
        q.add(1);
        visited[1] = true;
        
        while (!q.isEmpty())
        {
            int now = q.poll();
            
            for (int i = 1; i<n+1 ; i++)
            {
                if (graph[now][i] == 1 && visited[i] == false)
                {
                    q.add(i);
                    visited[i]=true;
                    cnt+=1;
                }
            }
        }
        
        
        return Math.abs(cnt*2 - n);
        
    }

 

이런 식으로.