Для обхода только связных компонентов:
Задача:
Дан направленный граф. Задача состоит в том, чтобы сделать Breadth First Traversal этого графа, начиная с 0.
Примечание: Переход от вершины u к вершине v возможен только при наличии ребра от u к v. Найдите BFS-обход графа, начиная с 0-й вершины, слева направо в соответствии с графом. Также следует учитывать только вершины, прямо или косвенно связанные с вершиной 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.
Решение: TC O(n), так как мы будем посещать максимум 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;
}
}