Дан связный неориентированный граф. Выполните обход графа по глубине.
Примечание: Используйте рекурсивный подход для нахождения DFS-обхода графа, начиная с 0-й вершины слева направо в соответствии с графом.
Пример 1:
Вход:
Выход: 0 1 2 4 3
Объяснение:
0 подключен к 1, 2, 4.
1 подключен к 0.
2 подключен к 0.
3 соединен с 4.
4 соединен с 0, 3.
Таким образом, начиная с 0, он переходит к 1, затем к 2.
затем к 4, а затем от 4 к 3.
Таким образом, dfs будет 0 1 2 4 3.
Для одного компонента:
class Solution {
// Function to return a list containing the DFS traversal of the graph.
public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
ArrayList<Integer> dfs = new ArrayList<>();
boolean visited[] = new boolean[V];
if(!visited[0])
dfsUtil(0,dfs,adj,visited);
return dfs;
}
public void dfsUtil(int node, ArrayList<Integer> dfs, ArrayList<ArrayList<Integer>> list,
boolean[] visited){
dfs.add(node);
visited[node] = true;
List<Integer> deepNodes = list.get(node);
for(Integer n : deepNodes){
if(!visited[n])
dfsUtil(n,dfs,list,visited);
}
}
}
Для более чем одного компонента:
Временная сложность: O(n) +O(n), т.е. O(n) для выполнения цикла for и еще o(n) для dfsUtil() (помните, что TC не O(n^2), так как dfsUtil() не будет вызываться на каждой итерации цикла for, он будет вызываться только при наличии других компонентов, так как за один вызов dfsUtil() будут посещены все узлы в этом компоненте.
class Solution {
// Function to return a list containing the DFS traversal of the graph.
public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
ArrayList<Integer> dfs = new ArrayList<>();
boolean visited[] = new boolean[V];
for(int i =0;i<V;i++)
if(!visited[i])
dfsUtil(i,dfs,adj,visited);
return dfs;
}
public void dfsUtil(int node, ArrayList<Integer> dfs, ArrayList<ArrayList<Integer>> list,
boolean[] visited){
dfs.add(node);
visited[node] = true;
List<Integer> deepNodes = list.get(node);
for(Integer n : deepNodes){
if(!visited[n])
dfsUtil(n,dfs,list,visited);
}
}
}