public class GraphDfs { private AdjList graph; private ArrayList<Integer> list = new ArrayList<>(); private boolean visited[]; public GraphDfs(AdjList graph) { this.graph = graph; this.visited = new boolean[graph.getV()]; for (int i = 0; i < graph.getV(); i++) { if (!visited[i]) Dfs(i); } } private void Dfs(int v) { visited[v] = true; list.add(v); for (int w : graph.adj(v)) { if (!visited[w]) { Dfs(w); } } } public ArrayList<Integer> getList() { return list; } }
int count=0; this.graph = graph; this.visited = new boolean[graph.getV()]; for (int i = 0; i < graph.getV(); i++) { count++; if (!visited[i]) Dfs(i); }
public GraphDfs(AdjList graph) { int count = 0; this.graph = graph; this.visited = new int[graph.getV()]; for (int i = 0; i < visited.length; i++) visited[i] = -1; for (int i = 0; i < graph.getV(); i++) if (visited[i] == -1) Dfs(i, count++); } private void Dfs(int v, int count) { visited[v] = count; list.add(v); for (int w : graph.adj(v)) if (visited[w] == -1) Dfs(w, count); }
public boolean isConnected(int v, int w) { graph.ValidateVertex(v); graph.ValidateVertex(w); return visited[v]== visited[w]; }
区别与使用图的邻接点的遍历方式判断
非最短路径,基于DFS遍历,将寻找结果缓存。
private void Dfs(int v, int w) {//w为父亲节点 from[v] = w; for (int next : graph.adj(v)) { if (from[next] == -1) { Dfs(next, v); } else if (next != w)//如果next节点遍历过,并且父亲节点不是next节点 hasCycle = true; } }
可参照leetcode分类中关于图论部分第一题
public class GraphBFS { AdjList adjList; ArrayList<Integer> order = new ArrayList<>(); boolean visited[]; public GraphBFS(AdjList adjList) { this.adjList = adjList; visited = new boolean[adjList.getV()]; for (int i = 0; i < visited.length; i++) { if (visited[i] == false) bfs(i); } } private void bfs(int v) { Queue<Integer> queue = new LinkedList<>(); visited[v] = true; queue.add(v); while (!queue.isEmpty()) { Integer cur = queue.poll(); order.add(cur); for (int next : adjList.adj(cur)) { if (!visited[next]) { queue.add(next); visited[next] = true; } } } } }
相比DFS,可以求解出无权图的最短路径问题
同样的思路,不同的遍历顺序
提交评论