Graph GeeksForGeeks의 너비 우선 검색 순회

연결된 구성 요소만 이송하는 경우:
문제:
유방향 그래프가 주어집니다. 작업은 0부터 시작하여 이 그래프의 Breadth First Traversal을 수행하는 것입니다.
참고: u에서 v로의 에지가 있는 경우에만 노드 u에서 노드 v로 이동할 수 있으며 그래프에 따라 왼쪽에서 오른쪽으로 0번째 정점에서 시작하는 그래프의 BFS 순회를 찾을 수 있습니다. 또한 Node 0에서 직접 또는 간접적으로 연결된 노드만 고려해야 합니다.

Input: 
Output: 0 1 2 3 4
Explanation: 
0 is connected to 1 , 2 , 3.
2 is connected to 4.
so starting from 0, it will go to 1 then 2
then 3.After this 2 to 4, thus bfs will be
0 1 2 3 4.

솔루션: 최대 n개의 노드를 방문하므로 TCO(n), 공간 복잡성: O(n)

//in bfs, we tarverse a node and adjacent nodes of the traversed node.
/*          0
      /     |     \
   1         2        3
             |
            4
*/
//bfs : 0-> 1->2->3->4
class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> bfs = new ArrayList<>();
        boolean visited[] = new boolean[V];
        // this is for traversing connected graph only 
            if(!visited[0]){
                Queue<Integer> queue = new LinkedList<>();
                visited[0] = true;
                queue.add(0);

                while(!queue.isEmpty()){
                    Integer node = queue.remove();
                    bfs.add(node);

                    for(Integer adjNode : adj.get(node)){
                        if(!visited[adjNode]){
                            visited[adjNode] = true;
                            queue.add(adjNode);
                        }
                    }  
                }
            }
        return bfs;
    }
}

연결되지 않은 그래프 구성요소를 포함한 전체 그래프 순회용

class Solution {
    // Function to return Breadth First Traversal of given graph.
    public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        ArrayList<Integer> bfs = new ArrayList<>();

        boolean visited[] = new boolean[V];
        // for traversing the entire graph
        for(int i =0;i<V;i++){
            if(!visited[i]){
                Queue<Integer> queue = new LinkedList<>();
                visited[i] = true;
                queue.add(i);

                while(!queue.isEmpty()){
                    Integer node = queue.remove();
                    bfs.add(node);

                    for(Integer adjNode : adj.get(node)){
                        if(!visited[adjNode]){
                            visited[adjNode] = true;
                            queue.add(adjNode);
                        }
                    }
                }
            }
        }
        return bfs;
    }
}