In directed graphs, edges are one-way: the pair of vertices that defines each edge is an ordered pair that specifies a one-way adjacency. Many applications (for example, graphs that represent the web, scheduling constraints, or telephone calls) are naturally expressed in terms of directed graphs. The one-way restriction is natural, easy to enforce in our implementations, and seems innocuous; but it implies added combinatorial structure that has profound implications for our algorithms and makes working with directed graphs quite different from working with undirected graphs.
Glossary
Our definitions for directed graphs are nearly identical to those for undirected graphs but they are worth restating. The slight differences in the wording to account for edge directions imply structural properties that will be the focus of this section.
- A directed graph (or digraph) is a set of vertices and a collection of directed edges. Each directed edge connects an ordered pair of vertices.
- A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A directed cycle is a directed path with at least one edge whose first and last vertices are the same. A simple cycle is a cycle with no repeated edges or vertices (except the requisite repetition of the first and last vertices). The length of a path or a cycle is its number of edges.
public class Digraph { private final int V; private int E; private Bag<Integer>[] adj; /** * Create an empty digraph with V vertices. * * @throws java.lang.IllegalArgumentException if V < 0 */ public Digraph(int V) { if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); this.V = V; this.E = 0; adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } } /** * Create a digraph from input stream. */ public Digraph(In in) { try { this.V = in.readInt(); if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative"); adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<Integer>(); } int E = in.readInt(); if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative"); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); addEdge(v, w); } } catch (NoSuchElementException e) { throw new InputMismatchException("Invalid input format in Digraph constructor"); } } /** * Copy constructor. */ public Digraph(Digraph G) { this(G.V()); this.E = G.E(); for (int v = 0; v < G.V(); v++) { // reverse so that adjacency list is in same order as original Stack<Integer> reverse = new Stack<Integer>(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } /** * Return the number of vertices in the digraph. */ public int V() { return V; } /** * Return the number of edges in the digraph. */ public int E() { return E; } /** * Add the directed edge v->w to the digraph. * * @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V */ public void addEdge(int v, int w) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V - 1)); if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V - 1)); adj[v].add(w); E++; } /** * Return the list of vertices pointed to from vertex v as an Iterable. * * @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V */ public Iterable<Integer> adj(int v) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); return adj[v]; } /** * Return the reverse of the digraph. */ public Digraph reverse() { Digraph R = new Digraph(V); for (int v = 0; v < V; v++) { for (int w : adj(v)) { R.addEdge(w, v); } } return R; } /** * Return a string representation of the digraph. */ public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(String.format("%d: ", v)); for (int w : adj[v]) { s.append(String.format("%d ", w)); } s.append(NEWLINE); } return s.toString(); } }
Representation. We use the adjacency-lists representation,where an edge v->w is represented as a list node containing w in the linked list corresponding to v. This representation is essentially the same as for undirected graphs but is even more straight forward because each edge occurs just once, as shown on the facing page.
Input format. The code for the constructor that takes a digraph from an input stream is identical to the corresponding constructor in Graph—the input format is the same, but all edges are interpreted to be directed edges.In the list-of-edgesformat,apairv w is interpreted as an edge v->w.
Reversing a digraph. Digraph also adds to the API a method reverse() which returns a copy of the digraph, with all edges reversed. This method is sometimes needed in digraph processing because it allows clients to find the edges that point to each vertex, while adj() gives just vertices connected by edges that point from each vertex.
Symbolic names. It is also a simple matter to allow clients to use symbolic names in digraph applications. To implement a class SymbolDigraph like SymbolGraph, replace Graph by Digraph everywhere.
Single-source reachability. Given a digraph and a source vertex s, support queries of the form Is there a directed path from s to a given target vertex v? DirectedDFS on the facing page is a slight embellishment of DepthFirstSearch which is the answer to this question.
By adding a second constructor that takes a list of vertices, this API supports for clients the following generalization of the problem:
Multiple-source reachability. Given a digraph and a set of source vertices, support queries of the form Is there a directed path from any vertex in the set to a given target vertex v?
public class DirectedDFS { private boolean[] marked; // marked[v] = true if v is reachable // from source (or sources) // single-source reachability public DirectedDFS(Digraph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } // multiple-source reachability public DirectedDFS(Digraph G, Iterable<Integer> sources) { marked = new boolean[G.V()]; for (int v : sources) dfs(G, v); } private void dfs(Digraph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) dfs(G, w); } } // is there a directed path from the source (or sources) to v? public boolean marked(int v) { return marked[v]; } }
DFS marks all the vertices in a digraph reachable from a given set of sources in time proportional to the sum of the outdegrees of the vertices marked.
Finding paths in digraphs.
Single-source directed paths. Given a digraph and a source vertex s, support queries of the form Is there a directed path from s to a given target vertex v? If so, find such a path.
public class DepthFirstDirectedPaths { private boolean[] marked; // marked[v] = true if v is reachable from s private int[] edgeTo; // edgeTo[v] = last edge on path from s to v private final int s; // source vertex // single source public DepthFirstDirectedPaths(Digraph G, int s) { marked = new boolean[G.V()]; edgeTo = new int[G.V()]; this.s = s; dfs(G, s); } private void dfs(Digraph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } } } // is there a directed path from s to v? public boolean hasPathTo(int v) { return marked[v]; } // return path from s to v; null if no such path public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<Integer>(); for (int x = v; x != s; x = edgeTo[x]) path.push(x); path.push(s); return path; } }
Single-source shortest directed paths. Given a digraph and a source vertex s, support queries of the form Is there a directed path from s to a given target vertex v? If so, find a shortest such path (one with a minimal number of edges).
public class BreadthFirstDirectedPaths { private static final int INFINITY = Integer.MAX_VALUE; private boolean[] marked; // marked[v] = is there an s->v path? private int[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private int[] distTo; // distTo[v] = length of shortest s->v path // single source public BreadthFirstDirectedPaths(Digraph G, int s) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; bfs(G, s); } // multiple sources public BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; bfs(G, sources); } // BFS from single source private void bfs(Digraph G, int s) { Queue<Integer> q = new Queue<Integer>(); marked[s] = true; distTo[s] = 0; q.enqueue(s); while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } // BFS from multiple sources private void bfs(Digraph G, Iterable<Integer> sources) { Queue<Integer> q = new Queue<Integer>(); for (int s : sources) { marked[s] = true; distTo[s] = 0; q.enqueue(s); } while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } // length of shortest path from s (or sources) to v public int distTo(int v) { return distTo[v]; } // is there a directed path from s (or sources) to v? public boolean hasPathTo(int v) { return marked[v]; } // shortest path from s (or sources) to v; null if no such path public Iterable<Integer> pathTo(int v) { if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<Integer>(); int x; for (x = v; distTo[x] != 0; x = edgeTo[x]) path.push(x); path.push(x); return path; } }
Cycles and DAGs
Directed cycles are of particular importance in applications that involve processing digraphs. To motivate the study of the role of directed cycles in digraph processing we consider, as a running example, the following prototypical application where digraph models arise directly:
Scheduling problems. A widely applicable problem-solving model has to do with arranging for the completion of a set of jobs, under a set of constraints, by specifying when and how the jobs are to be performed. Constraints might involve functions of the time taken or other resources consumed by the jobs. The most important type of constraints is precedence constraints, which specify that certain tasks must be performed before certain others. Different types of additional constraints lead to many different types of scheduling problems, of varying difficulty.
Precedence-constrained scheduling. Given a set of jobs to be completed, with precedence constraints that specify that certain jobs have to be completed before certain other jobs are begun, how can we schedule the jobs such that they are all completed while still respecting the constraints?
For any such problem, a digraph model is immediate, with vertices corresponding to jobs and directed edges corresponding to precedence constraints. In digraphs, precedence-constrained scheduling amounts to the following fundamental problem:
Topological sort. Given a digraph, put the vertices in order such that all its directed edges point from a ver- tex earlier in the order to a vertex later in the order (or report that doing so is not possible).
Cycles in digraphs. If job x must be completed before job y, job y before job z, and job z before job x, then someone has made a mistake, because those three constraints cannot all be satisfied. In general, if a precedence-constrained scheduling problem has a directed cycle, then there is no feasible solution. To check for such errors, we need to be able to solve the following problem: Directed cycle detection. Does a given digraph have a directed cycle? If so, find the vertices on some such cycle, in order from some vertex back to itself. A directed acyclic graph (DAG) is a digraph with no directed cycles.
public class DirectedCycle { private boolean[] marked; // marked[v] = has vertex v been marked? private int[] edgeTo; // edgeTo[v] = previous vertex on path to v private boolean[] onStack; // onStack[v] = is vertex on the stack? private Stack<Integer> cycle; // directed cycle (or null if no such cycle) public DirectedCycle(Digraph G) { marked = new boolean[G.V()]; onStack = new boolean[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // check that algorithm computes either the topological order or finds a directed cycle private void dfs(Digraph G, int v) { onStack[v] = true; marked[v] = true; for (int w : G.adj(v)) { // short circuit if directed cycle found if (cycle != null) return; //found new vertex, so recur else if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } // trace back directed cycle else if (onStack[w]) { cycle = new Stack<Integer>(); for (int x = v; x != w; x = edgeTo[x]) { cycle.push(x); } cycle.push(w); cycle.push(v); } } onStack[v] = false; } public boolean hasCycle() { return cycle != null; } public Iterable<Integer> cycle() { return cycle; } // certify that digraph is either acyclic or has a directed cycle private boolean check(Digraph G) { if (hasCycle()) { // verify cycle int first = -1, last = -1; for (int v : cycle()) { if (first == -1) first = v; last = v; } if (first != last) { System.err.printf("cycle begins with %d and ends with %d\n", first, last); return false; } } return true; } }
Depth-first orders and topological sort. Precedence-constrained scheduling amounts to computing a topological order for the vertices of a DAG, a digraph has a topological order if and only if it is a DAG.
Remarkably, it turns out that we have already seen an algorithm for topological sort: a one-line addition to our standard recursive DFS does the job! To convince you of this fact, we begin with the class DepthFirstOrder on page 580. It is based on the idea that depth-first search visits each vertex exactly once. If we save the vertex given as argument to the recursive dfs() in a data structure, then iterate through that data structure, we see all the graph vertices, in order determined by the nature of the data structure and by whether we do the save before or after the recursive calls. Three vertex orderings are of interest in typical applications:
■ Preorder : Put the vertex on a queue before the recursive calls.
■ Postorder : Put the vertex on a queue after the recursive calls.
■ Reverse postorder : Put the vertex on a stack after the recursive calls.
A trace of DepthFirstOrder for our sample DAG is given on the facing page. It is simple to implement and supports pre(), post(), and reversePost() methods that are useful for advanced graph-processing algorithms. For example, order() in Topological consists of a call on reversePost().
public class DepthFirstOrder { private boolean[] marked; // marked[v] = has v been marked in dfs? private int[] pre; // pre[v] = preorder number of v private int[] post; // post[v] = postorder number of v private Queue<Integer> preorder; // vertices in preorder private Queue<Integer> postorder; // vertices in postorder private int preCounter; // counter or preorder numbering private int postCounter; // counter for postorder numbering // depth-first search preorder and postorder in a digraph public DepthFirstOrder(Digraph G) { pre = new int[G.V()]; post = new int[G.V()]; postorder = new Queue<Integer>(); preorder = new Queue<Integer>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // depth-first search preorder and postorder in an edge-weighted digraph public DepthFirstOrder(EdgeWeightedDigraph G) { pre = new int[G.V()]; post = new int[G.V()]; postorder = new Queue<Integer>(); preorder = new Queue<Integer>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v++) if (!marked[v]) dfs(G, v); } // run DFS in digraph G from vertex v and compute preorder/postorder private void dfs(Digraph G, int v) { marked[v] = true; pre[v] = preCounter++; preorder.enqueue(v); for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } postorder.enqueue(v); post[v] = postCounter++; } // run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder private void dfs(EdgeWeightedDigraph G, int v) { marked[v] = true; pre[v] = preCounter++; preorder.enqueue(v); for (DirectedEdge e : G.adj(v)) { int w = e.to(); if (!marked[w]) { dfs(G, w); } } postorder.enqueue(v); post[v] = postCounter++; } public int pre(int v) { return pre[v]; } public int post(int v) { return post[v]; } // return vertices in postorder as an Iterable public Iterable<Integer> post() { return postorder; } // return vertices in preorder as an Iterable public Iterable<Integer> pre() { return preorder; } // return vertices in reverse postorder as an Iterable public Iterable<Integer> reversePost() { Stack<Integer> reverse = new Stack<Integer>(); for (int v : postorder) reverse.push(v); return reverse; } // check that pre() and post() are consistent with pre(v) and post(v) private boolean check(Digraph G) { // check that post(v) is consistent with post() int r = 0; for (int v : post()) { if (post(v) != r) { StdOut.println("post(v) and post() inconsistent"); return false; } r++; } // check that pre(v) is consistent with pre() r = 0; for (int v : pre()) { if (pre(v) != r) { StdOut.println("pre(v) and pre() inconsistent"); return false; } r++; } return true; } }
Reverse post order in a DAG is a topological sort. With DFS,we can topologically sort a DAG in time proportional to V+E.
public class Topological { private Iterable<Integer> order; // topological order // topological sort in a digraph public Topological(Digraph G) { DirectedCycle finder = new DirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); } } // topological sort in an edge-weighted digraph public Topological(EdgeWeightedDigraph G) { EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G); if (!finder.hasCycle()) { DepthFirstOrder dfs = new DepthFirstOrder(G); order = dfs.reversePost(); } } // return topological order if a DAG; null otherwise public Iterable<Integer> order() { return order; } // does digraph have a topological order? public boolean hasOrder() { return order != null; } public static void main(String[] args) { String filename = args[0]; String delimiter = args[1]; SymbolDigraph sg = new SymbolDigraph(filename, delimiter); Topological topological = new Topological(sg.G()); for (int v : topological.order()) { System.out.println(sg.name(v)); } } }
相关推荐
计算机二级公共基础知识模 拟试题及答案详解.pdf
内容概要:本文档详细介绍了语音发射机的设计与实现,涵盖了从硬件电路到具体元件的选择和连接方式。文档提供了详细的电路图,包括电源管理、信号处理、音频输入输出接口以及射频模块等关键部分。此外,还展示了各个引脚的功能定义及其与其他组件的连接关系,确保了系统的稳定性和高效性能。通过这份文档,读者可以全面了解语音发射机的工作原理和技术细节。 适合人群:对电子工程感兴趣的初学者、从事嵌入式系统开发的技术人员以及需要深入了解语音发射机制的专业人士。 使用场景及目标:适用于希望构建自己的语音发射设备的研究人员或爱好者,帮助他们掌握相关技术和实际操作技能。同时,也为教学机构提供了一个很好的案例研究材料。 其他说明:文档不仅限于理论讲解,还包括具体的实施步骤,使读者能够动手实践并验证所学知识。
内容概要:本文详细介绍了用易语言编写的单线程全功能注册机源码,涵盖了接码平台对接、滑块验证处理、IP代理管理以及料子导入等多个核心功能。文章首先展示了主框架的初始化配置和事件驱动逻辑,随后深入探讨了接码平台(如打码兔)的API调用及其返回数据的处理方法。对于滑块验证部分,作者分享了如何利用易语言的绘图功能模拟真实用户的操作轨迹,并提高了验证通过率。IP代理模块则实现了智能切换策略,确保代理的有效性和稳定性。此外,料子导入功能支持多种格式的数据解析和去重校验,防止脏数据污染。最后,文章提到了状态机设计用于控制注册流程的状态持久化。 适合人群:有一定编程基础,尤其是熟悉易语言的开发者和技术爱好者。 使用场景及目标:适用于希望深入了解易语言注册机开发的技术细节,掌握接码、滑块验证、IP代理等关键技术的应用场景。目标是帮助读者理解并优化现有注册机的功能,提高其稳定性和效率。 其他说明:文中提到的部分技术和实现方式可能存在一定的风险,请谨慎使用。同时,建议读者在合法合规的前提下进行相关开发和测试。
计算机绘图实用教程 第三章.pdf
计算机辅助设计—AutoCAD 2018中文版基础教程 各章CAD图纸及相关说明汇总.pdf
C++相关书籍,计算机相关书籍,linux相关及http等计算机学习、面试书籍。
计算机二级mysql数据库程序设计练习题(一).pdf
计算机发展史.pdf
计算机二级课件.pdf
计算机概论第三讲:计算机组成.pdf
内容概要:本文档由中国移动通信集团终端有限公司、北京邮电大学、中国信息通信研究院和中国通信学会共同发布,旨在探讨端侧算力网络(TCAN)的概念、架构、关键技术及其应用场景。文中详细分析了终端的发展现状、基本特征和发展趋势,阐述了端侧算力网络的定义、体系架构、功能架构及其主要特征。端侧算力网络通过整合海量泛在异构终端的算力资源,实现分布式多级端侧算力资源的高效利用,提升网络整体资源利用率和服务质量。关键技术涵盖层次化端算力感知图模型、资源虚拟化、数据压缩、多粒度多层次算力调度、现场级AI推理和算力定价机制。此外,还探讨了端侧算力网络在智能家居、智能医疗、车联网、智慧教育和智慧农业等领域的潜在应用场景。 适合人群:从事通信网络、物联网、边缘计算等领域研究和开发的专业人士,以及对6G网络和端侧算力网络感兴趣的学者和从业者。 使用场景及目标:适用于希望深入了解端侧算力网络技术原理、架构设计和应用场景的读者。目标是帮助读者掌握端侧算力网络的核心技术,理解其在不同行业的应用潜力,推动端侧算力网络技术的商业化和产业化。 其他说明:本文档不仅提供了端侧算力网络的技术细节,还对其隐私与安全进行了深入探讨
学习java的心得体会.docx
计算机二级考试(南开100题齐全).pdf
内容概要:本文详细介绍了计算机二级C语言考试的内容和备考方法。首先概述了计算机二级考试的意义及其在计算机技能认证中的重要性,重点讲解了C语言的基础语法,包括程序结构、数据类型、运算符和表达式等。接着深入探讨了进阶知识,如函数、数组、指针、结构体和共用体的应用。最后分享了针对选择题、填空题和编程题的具体解题技巧,强调了复习方法和实战演练的重要性。 适合人群:准备参加计算机二级C语言考试的学生和技术爱好者。 使用场景及目标:①帮助考生系统地掌握C语言的核心知识点;②提供有效的解题策略,提高应试能力;③指导考生制定合理的复习计划,增强实战经验。 其他说明:本文不仅涵盖了理论知识,还提供了大量实例代码和详细的解释,有助于读者更好地理解和应用所学内容。此外,文中提到的解题技巧和复习建议对实际编程也有很大帮助。
论文格式及要求.doc
内容概要:本文详细介绍了如何使用三菱FX3U PLC及其485BD通信板与四台台达VFD-M系列变频器进行通信的设置与应用。主要内容涵盖硬件连接注意事项、通信参数配置、RS指令的应用、CRC校验算法的实现以及频率给定和状态读取的具体方法。文中提供了多个实用的编程示例,展示了如何通过梯形图和结构化文本编写通信程序,并讨论了常见的调试技巧和优化建议。此外,还提到了系统的扩展性和稳定性措施,如增加温度传感器通信功能和应对电磁干扰的方法。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是那些熟悉三菱PLC和台达变频器的使用者。 使用场景及目标:适用于需要实现多台变频器联动控制的工业应用场景,旨在提高生产效率和系统可靠性。通过学习本文,读者可以掌握如何构建稳定的RS485通信网络,确保变频器之间的高效协同工作。 其他说明:本文不仅提供了详细的理论指导,还包括了许多来自实际项目的经验教训,帮助读者避免常见错误并提升编程技能。
计算机服务规范.pdf
Discuz_X3.2_TC_UTF8.zip LNMP搭建安装包
2023年房地产行业研究报告:缓解竣工下行加速的两大改革
win32汇编环境,网络编程入门之十五