/** * 递归搜索,递归到最底层的时候才会返回来递归前一个顶点. * @param g 图实例. * @param startPoint 顶点. */ privatevoidbfs(Graph g, int startPoint){ // 队列代替递归循环 Queue<Integer> q = new ArrayDeque<>(); marked[startPoint] = true; q.add(startPoint); while (!q.isEmpty()) { int point = q.poll(); for (int _point : g.adj(point)) { if (marked[_point]) { continue; } marked[_point] = true; q.add(_point); // 下标保存被连接的点的值,数组值保存上一个点的值 edgeTo[_point] = point; if (_point == endPoint) { return; } }
} }
public Iterable<Integer> pathTo(){ // 使用栈反过来查找edgeTo Stack<Integer> path = new Stack<>(); for (int x = endPoint; x != startPoint; x = edgeTo[x]) { path.push(x); } path.push(startPoint); return path; }
publicDigraph(int v){ V = v; E = 0; lists = (List<Integer>[]) new List[v]; for (int i = 0; i < v; i++) { lists[i] = new ArrayList<>(); } }
publicintV(){ return V; }
publicintE(){ return E; }
publicvoidaddEdge(int v, int w){ // 只是添加一个方向的,比无向图少了一个返回 lists[v].add(w); E++; }
// 返回一个顶点所有连接的另外一个顶点 public Iterable<Integer> adj(int e){ return lists[e]; }
// 反转图的方向 public Digraph reverse(){ Digraph g = new Digraph(V); for (int i = 0; i < V; i++) { for (Integer j : adj(i)) { g.addEdge(j, i); } } return g; }
privatevoiddfs(Digraph g, int point){ onStack[point] = true; marked[point] = true;
for (Integer v : g.adj(point)) { if (hasCycle()) { return; } if (!marked[v]) { edgeTo[v] = point; dfs(g, v); } elseif (onStack[v]) { cycle = new Stack<>(); for (int x = point; x != v; x = edgeTo[x]) { cycle.push(x); } cycle.push(v); cycle.push(point); } }
publicDFSIter(Digraph g){ this.marked = newboolean[g.V()]; this.pre = new ArrayDeque<>(); this.post = new ArrayDeque<>(); this.reversePost = new Stack<>(); for (int i = 0; i < g.V(); i++) { if (!marked[i]) { dfs(g, i); } } }
privatevoiddfs(Digraph g, int v){ this.pre.offer(v); this.marked[v] = true; for (Integer w : g.adj(v)) { if (!this.marked[w]) { dfs(g, w); } } this.post.offer(v); this.reversePost.push(v); }
public Queue<Integer> getPre(){ return pre; }
public Queue<Integer> getPost(){ return post; }
public Iterable<Integer> getReversePost(){ List<Integer> l = new ArrayList<>(); for (int i = reversePost.size(); i > 0; i--) { l.add(reversePost.pop()); } return l; }
// 创建图用例 Digraph g = new Digraph(12); for (String _l : line) { String[] split = _l.split("-"); g.addEdge(Integer.parseInt(split[0]), Integer.parseInt(split[1])); }
DFSIter dfsIter = new DFSIter(g); System.out.println(dfsIter.getPre()); System.out.println(dfsIter.getPost()); System.out.println(dfsIter.getReversePost()); }
}
强连通性
强连通性表示的是,给定一个图和两个顶点 AB,同时存在一条线路可以从 A 到达 B,也存在另外一条线路从 B 到 A,就说明 A 和 B 是具有 强连通性 的。而 环 就是 强连通性的一种方式 那么,一个叫做 Kosaraju 的人,就发现了,如果我对一个有向图进行 深度遍历,发现 A -> B,而如果存在一个路径是 B->A 的话,那么在这个有向图的反向图中,必定存在 A -> B 的路径: 首先,先构建一个图:
publicPrim(EdgeWeightedGraph g){ tmp = new PriorityQueue<>(); result = new ArrayDeque<>(); marked = newboolean[g.V()];
marked(g, 0); while (!tmp.isEmpty()) { Edge poll = tmp.poll(); int v = poll.either(); int w = poll.other(v); if (marked[v] && marked[w]) { continue; } result.add(poll); if (!marked[v]) marked(g, v); if (!marked[w]) marked(g, w); } }
privatevoidmarked(EdgeWeightedGraph g, int v){ marked[v] = true; for (Edge edge : g.adj(v)) { if (!marked[edge.other(v)]) { tmp.add(edge); } } }
publicKruskalMST(EdgeWeightedGraph G){ // more efficient to build heap by passing array of edges MinPQ<Edge> pq = new MinPQ<Edge>(); for (Edge e : G.edges()) { pq.insert(e); }
// run greedy algorithm UF uf = new UF(G.V()); while (!pq.isEmpty() && mst.size() < G.V() - 1) { Edge e = pq.delMin(); int v = e.either(); int w = e.other(v); if (uf.find(v) != uf.find(w)) { // v-w does not create a cycle uf.union(v, w); // merge v and w components mst.enqueue(e); // add edge e to mst } } }
publicDirectedEdgeWeightedGraph(int v){ V = v; E = 0; adj = (List<DirectedEdge>[]) new List[v]; for (int i = 0; i < v; i++) { adj[i] = new ArrayList<>(); } }
Iterable<DirectedEdge> pathTo(int v){ if (!hasPathTo(v)) { returnnull; }
Stack<DirectedEdge> path = new Stack<>(); for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { path.push(e); } return path; }
publicstaticvoidmain(String[] args){ String[] lines = { "4-5-0.35", "5-4-0.35", "4-7-0.37", "5-7-0.28", "7-5-0.28", "5-1-0.32", "0-4-0.38", "0-2-0.26", "7-3-0.39", "1-3-0.29", "2-7-0.34", "6-2-0.40", "3-6-0.52", "6-0-0.58", "6-4-0.93", }; DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8); for (String _line : lines) { String[] split = _line.split("-"); String v = split[0], w = split[1], weight = split[2]; int vi = Integer.parseInt(v), vw = Integer.parseInt(w); ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight))); }
DijkstraShortest d = new DijkstraShortest(ewg, 0); for (int i = 0; i < ewg.V(); i++) { System.out.println("0到" + i + "的最短距离是:" + d.distTo(i) + ",路径是:" + d.pathTo(i)); } }
publicTopologicalIter(DirectedEdgeWeightedGraph g){ // if (new CycleDiagraphUtil(g, 0).hasCycle()) { // throw new RuntimeException("出现环,无法计算拓扑结构"); // } this.marked = newboolean[g.V()]; this.pre = new ArrayDeque<>(); this.post = new ArrayDeque<>(); this.reversePost = new Stack<>(); for (int i = 0; i < g.V(); i++) { if (!marked[i]) { dfs(g, i); } } }
privatevoiddfs(DirectedEdgeWeightedGraph g, int v){ this.pre.offer(v); this.marked[v] = true; for (DirectedEdge w : g.adj(v)) { int to = w.to(); if (!this.marked[to]) { dfs(g, to); } } this.post.offer(v); this.reversePost.push(v); }
public Queue<Integer> getPre(){ return pre; }
public Queue<Integer> getPost(){ return post; }
public Iterable<Integer> getReversePost(){ List<Integer> l = new ArrayList<>(); for (int i = reversePost.size(); i > 0; i--) { l.add(reversePost.pop()); } return l; }
publicstaticvoidmain(String[] args){ String[] lines = { "5-4-0.35", "4-7-0.37", "5-7-0.28", "5-1-0.32", "4-0-0.38", "0-2-0.26", "3-7-0.39", "1-3-0.29", "7-2-0.34", "6-2-0.40", "3-6-0.52", "6-0-0.58", "6-4-0.93", }; DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8); for (String _line : lines) { String[] split = _line.split("-"); String v = split[0], w = split[1], weight = split[2]; int vi = Integer.parseInt(v), vw = Integer.parseInt(w); ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight))); }
TopologicalIter top = new TopologicalIter(ewg); System.out.println(top.getReversePost()); }
Iterable<DirectedEdge> pathTo(int v){ if (!hasPathTo(v)) { returnnull; }
Stack<DirectedEdge> path = new Stack<>(); for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { path.push(e); } return path; }
publicstaticvoidmain(String[] args){ String[] lines = { "5-4-0.35", "4-7-0.37", "5-7-0.28", "5-1-0.32", "4-0-0.38", "0-2-0.26", "3-7-0.39", "1-3-0.29", "7-2-0.34", "6-2-0.40", "3-6-0.52", "6-0-0.58", "6-4-0.93", }; DirectedEdgeWeightedGraph ewg = new DirectedEdgeWeightedGraph(8); for (String _line : lines) { String[] split = _line.split("-"); String v = split[0], w = split[1], weight = split[2]; int vi = Integer.parseInt(v), vw = Integer.parseInt(w); ewg.addEdge(new DirectedEdge(vi, vw, Double.parseDouble(weight))); }
DijkstraNoCycleShortest d = new DijkstraNoCycleShortest(ewg, 5); for (int i = 0; i < ewg.V(); i++) { System.out.println("5 -> " + i + ": " + d.pathTo(i)); } }
}
那为啥说引入拓扑结构就会使算法变得高效呢,因为我们知道拓扑排序,是基于图相互依赖的关系(前提是一个无环图)来排序的,那么,我们使用这个排序再来放松顶点边的时候,当 v-w 这条边被放松了过后,起点 v 因为拓扑排序的关系一定排在 w 之前,所以他在被放松以后,就不会继续被访问到,也不会继续被放松,所以算法经过放松的次数比原生的 Dijkstra算法 更少,所以说针对 无环 的有向图,使用拓扑排序会比原来的算法高效。 那么如果我们需要计算出图中的最长路径呢,那么我们只需要将 distTo 数组所有值先初始化为无限小,然后改变放松计算中的大小方向就可以了。
privatevoidrelax(DirectedEdgeWeightedGraph g, int v){ for (DirectedEdge directedEdge : g.adj(v)) { int w = directedEdge.to(); /* 遍历当前顶点连接的所有点,然后计算如果现有的距离比目前存储的大的话,就开始替换 */ if (distTo[w] > distTo[v] + directedEdge.weight()) { distTo[w] = distTo[v] + directedEdge.weight(); edgeTo[w] = directedEdge; if (!onQ[w]) { queue.add(w); onQ[w] = true; } } if (cost++ % g.V() == 0) { findNegativeCycle(); if (hasNegativeCycle()) return; } } }
privatevoidfindNegativeCycle(){ int v = edgeTo.length; DirectedEdgeWeightedGraph t = new DirectedEdgeWeightedGraph(v); for (int i = 0; i < v; i++) { if (edgeTo[i] != null) { t.addEdge(edgeTo[i]); } }
DirectedEdgeWeightedGraphFinder f = new DirectedEdgeWeightedGraphFinder(t); cycle = f.cycle; }
staticclassDirectedEdgeWeightedGraphFinder{ Stack<DirectedEdge> cycle; privateboolean[] marked; private DirectedEdge[] edgeTo; privateboolean[] onStack; DirectedEdgeWeightedGraphFinder(DirectedEdgeWeightedGraph G) { // 直接通过dfs找出环 marked = newboolean[G.V()]; onStack = newboolean[G.V()]; edgeTo = new DirectedEdge[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v);
}
privatevoiddfs(DirectedEdgeWeightedGraph G, int v){ onStack[v] = true; marked[v] = true; for (DirectedEdge e : G.adj(v)) { int w = e.to();
if (cycle != null) return;
elseif (!marked[w]) { edgeTo[w] = e; dfs(G, w); }
elseif (onStack[w]) { cycle = new Stack<>();
DirectedEdge f = e; while (f.from() != w) { cycle.push(f); f = edgeTo[f.from()]; } cycle.push(f);