一. 有向图的相关术语

在有向图中，边是单向的：每条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图：比如任务調度的依赖关系，社交网络的任务关系等等都是天然的有向图。
以下概念都是针对有向图的：
（1）有向图：一幅有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。
（2）顶点的出度：该顶点指出的边的总数。
（3）顶点的入度：指向该顶点的边的总数。
（4）比如对于有序对(w,v) 一般代表w->v 的一条有向边。
（5）有向路径：由一系列顶点组成，其中每个顶点都存在一条有向边从它指向序列中的下一个顶点。
（6）有向环：为一条至少含有一条边且起点和终点相同的有向路径。
（7）简单有向环：是一条除了起点和终点外，不含有重复的顶点和边的环。
二. 有向图的存储数据结构

首先定义有向图的API接口，DiGraph 本质上和Graph是一样的。
public class Digraph
Digraph(int v)	创建一幅含有v个顶点，但是没有边的有向图
Digraph(In in)	从输入流中读取一幅有向图
int E()	边的总数
int V()	边的总数
void addEdge(int v, int w)	添加一条有向边v ->w
`Iterble<Integer>adj(int v)`	由顶点v出发的有向边所连接的所有顶点
Digraph reverse()	该图的反向图
String toString()	对象的字符串表示形式
1. 有向图的表示

和无向图的表示类似，我们还是使用邻接表来存储有向图，其中边 v—>w 表示为顶点v所对应的邻接链表中包含一个w顶点。
2. 有向图取反

上面的API中给出了reverse() 方法，将有向图中的所有有向边反转，并生成副本。
3. 有向图的实现

使用邻接表来存储有向图，用数组来表示图中的每个节点的集合，并且数组的下标就表示节点的标识符。
下面就是有向图的实现方式：
package com.example.algorithm4.graphs;
import edu.princeton.cs.algs4.Bag;
 * 有向图的实现
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
public class DiGraph {
     * 节点的总个数
    private final int V;
     * 边的总个数
    private int E;
     * 有向图的邻接表表示法
    private Bag<Integer>[] adj;
     * 创建一个含有V个节点，但是0条边的有向图
     * @param V
    public DiGraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[])new Bag[V];
        for (int i=0; i<this.V; i++){
            adj[V] = new Bag<>();
    public int E(){
        return this.E;
    public int V(){
        return this.V;
     * 添加一条 v-->w 的边
     * @param v 有向边的源在数组中的标识符
     * @param w 有向边的终在数组中的标识符
    public void addEgge(int v, int w){
        adj[v].add(w);
        this.E++;
     * 节点v 的所有出度的终顶点
     * @param v 节点v 的标识符
     * @return
    public Iterable<Integer> adj(int v){
        return adj[v];
     * 此有向图反转之后的副本
     * @return
    public DiGraph reverse(){
        DiGraph reverse = new DiGraph(this.V);
        for(int i=0 ;i<this.V; i++){
            for (int w : adj[i]){
                //边反转
                reverse.addEgge(w, i);
        return reverse;
4. 符号有向图的实现
 
有向图的邻接表表示和无向图的邻接表表示区别不大，仅仅在于边的处理上有一点区别。如果对于有向图的结点的标识我们也想用字符串来表示呢？其实现方法几乎和无向图一样，增加一个Map用来保存顶点的符号到数组下表的映射关系，然后用字符数组保存所有的符号，数组下标天然表示每个顶点的index。 代码实现上只需要把SymbolGraph中的Graph替换成DiGraph就可，下面也给出实现代码： 
package com.example.algorithm4.graphs;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.ST;
 * 符号有向图的实现
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
public class SymbolDiGraph {
    private ST<String, Integer> st; // map,顶点符号名 -> 数组索引
    private String[] keys; // 数组索引 -> 顶点符号名
    private DiGraph G; // 图
     * 构造一颗符号有向图
     * @param stream 顶点边的数据源
     * @param sp 顶点分隔符
    public SymbolDiGraph(String stream, String sp) {
        st = new ST<>();
        In in = new In(stream); // First pass
        while (in.hasNextLine()) {// builds the index
            String[] a = in.readLine().split(sp); // by reading strings
            for (int i = 0; i < a.length; i++) {// to associate each
                if (!st.contains(a[i])) {// distinct string
                	st.put(a[i], st.size()); // with an index.
        keys = new String[st.size()]; //建立索引 --> 结点符号
        for (String name : st.keys()) {// to get string keys
          	keys[st.get(name)] = name; // is an array.
        // 创建符号图
        G = new DiGraph(st.size());
        in = new In(stream); // Second pass
        while (in.hasNextLine()) {// builds the graph
            String[] a = in.readLine().split(sp); // by connecting the
            int v = st.get(a[0]); // source vertex
            for (int i = 1; i < a.length; i++) {// on each line
            	G.addEdge(v, st.get(a[i])); // to all the others.
  	public boolean contains(String s) {
      	return st.contains(s);
  	public int index(String s) {
      	return st.get(s);
	public String name(int v) {
      	return keys[v];
	public DiGraph G() {
      	return G;
三. 有向图中的可达性
 
我们在无向图中介绍的第一个算法就是DFS，其实无向图是很多算法的基础，解决了单点连通性的问题，可以判断无向图中指定的两个顶点是否连通。其思想对于有向图同样适用~




    
 
 定义：有向图的单点可达性：给定一个有向图和一个起点s，判断是否存在一条从起点s到指定节点v的有向路径。 
针对以上问题，设计DirectedDFS 算法的API： 
public class DirectedDFS 
DirectedDFS(DiGraph G, int s) 在G中找到从s可达的所有顶点
DirectedDFS(DiGraph G, Iterable<Integer> sources) 在G中找到从sources的所有顶点中可达的所有顶点
boolean reachable(int v) d顶点v是可达的嘛 
1. 使用DFS实现有向图的可达性分析
 
 在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比。 
下面是有向图的可达性算法的实现： 
package com.example.algorithm4.graphs;
 * 有向图的深度优先遍历
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
public class DirectedDFS {
     * 从起点s开始DFS访问过的路径标记
    private boolean[] marked;
    public DirectedDFS(Digraph digraph, int s) {
        this.marked = new boolean[digraph.V()];
        dfs(digraph, s);
    public DirectedDFS(Digraph digraph, Iterable<Integer> sources) {
        this.marked = new boolean[digraph.V()];
        for(int s : sources){
            if (!marked[s]){
                dfs(digraph, s);
     * 从节点v 开始有向图的DFS
     * @param digraph 有向图
     * @param v 结点
    private void dfs(Digraph digraph, int v){
        this.marked[v] = true;
        for (int w : digraph.adj(v)){
            if(!this.marked[w]){
                dfs(digraph, w);
    public boolean marked(int v){
        return marked[v];
这份深度优先搜索能够实现判断一个或则一组(多点可达性)顶点能到达哪些其他顶点。 
2. 标记-清除的垃圾收集
 
多点可达性的一个重要的实际应用是在典型的内存管理上，比如JVM内存管理，在一幅有向图中，一个顶点代表一个对象，一条边代表一个对象对另外一个对象的引用。 有向图的模型很好的可以应用在JVM内存管理上面。当从根节点遍历时候，那么不可达的顶点就代表不会再被使用，就可以被回收以释放内存。 
标记-清除的垃圾回收算法会为每个对象保存一个位作为垃圾回收之用，然后周期性的运行一个类似于DirectedDFS的有向图可达性算法来标记所有可以被访问到的对象，然后清理所有对象，回收没有被标记的对象，以达到释放内存的目的。 
3. 有向图的寻路
 
DepthFirstPaths 和 BreadthFirstPaths 也都是有向图处理中的重要算法。可以用处理下面问题： 
单点有向路径：给定一个起点s，从s到给定目的顶点v是否存在一条有向路径。如果有就找出这条路径。
单点最短有向路径：给定一个起点s，从s到给定目的顶点v是否存在一条有向路径。如果有就找出最短的路径。 
下图给出了一个使用深度优先遍历在一幅有向图中寻找能够从顶点0到达的所有顶点的轨迹的示意图： 
四. 环和有向无环图(DFS和拓扑排序)
 
在有向图的应用场景中对于有向环的检测十分重要，因为有向环就代表着死循环，然后实际的项目中由于依赖关系的复杂，几乎不可能肉眼检测有向环，所以检测有向环是否存在就至关重要。 
对于有向环的检测主要有两种方法：DSF和拓扑排序。下面以实际例子来分析 
1. 调度问题(拓扑排序)
 
一个广泛使用的模型就是给定一组任务并安排它们的执行顺序，限制条件是这些任务的执行方法和起始时间。限制条件可能还包括任务的耗时以及消耗的其他资源。最重要的一种限制条件叫做优先级限制，它指明了哪些任务必须在哪些任务之前完成。 不同类型的限制条件会产生不同类型不同难度的调度问题 
下面以一个正在安排课程的大学生为例，有些课程是其余课程的先导课程：如图： 
再假设该学生一次只能修一门课，问题就可以抽象成以下模型： 
优先级限制下的調度问题：给定一组需要完成的任务，以及一组关于任务完成的先后次序的优先级顺序。在满足条件下以最优方案完成任务。为了简化模型，以数字标识顶点，顶点代表任务。可以等价成下图: 
 拓扑排序：给定一幅有向图，将所有顶点排序，使得所有的有向边均从排在前面元素指向排在后面的元素。 
上面的实例的拓扑排序图如下：所有边都朝下，清晰描绘了这幅有向图模型代表的优先级限制下調度问题的解决方法： 
拓扑排序有很多典型的应用，比如任务調度，继承等等。 
2. 有向环的检测方法一：DFS
 
 定义。有向无环图就是一幅不包含环的有向图。 
有向环的检测，我们可以借助于DFS算法，也可以借助拓扑排序。算法DirectedCycle 实现了环的检测，API如下: 
public class DirectedCycle 
DirectedCycle(Digraph digraph) 寻找有向环的构造函数
boolean hasCycle() digraph是否有环
Iterable<Integer> cycle() 有向环中的所有顶点 
下图是一个在有向环中寻找环的过程示意图： 
算法实现如下： 
package com.example.algorithm4.graphs;
import java.util.Stack;
 * 有向图环的检测：DFS算法
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
public class DirectedCycle {
     * 从起点开始DFS访问过的路径标记
    private boolean[] marked;
     * 从起点到一个顶点v的已知路径上的最后一个顶点
    private int[] edgeTo;
     * 如果存在有向环，就保存有向环中的所有顶点。
    private Stack<Integer> cycle;
     * 递归调用栈上的所有顶点
     * 这里类似于Java里面的一个set，里面保存了所有已经访问过的顶点
    private boolean[] onStack;
     * 构造器
     * @param digraph 有向图
    public DirectedCycle(Digraph digraph) {
        this.marked = new boolean[digraph.V()];
        this.edgeTo = new int[digraph.V()];
        this.onStack = new boolean[digraph.V()];
        for (int v=0; v<digraph.V(); v++) {
            if( !marked[v] ) {
                dfs(digraph, v);
     * 从节点v 开始有向图的DFS
     * @param digraph 有向图
     * @param v 结点
    private void dfs(Digraph digraph, int v){
        // 标记当前结点在堆栈路径上
        this.onStack[v] = true;
        this.marked[v] = true;
        for (int w : digraph.adj(v)){
            // 如果当前图已经有环就直接返回
            if (this.hasCycle(w)){
                return;
            } else if(!this.marked[w]){
                // 如果当前结点没有被标记过，递归dfs
                edgeTo[w] = v;
                dfs(digraph, w);
            } else if (onStack[w]){
                // (1)当前结点被标记过来了，(2)而且在已经访问过得堆栈上，则存在环
                cycle = new Stack<>();
                for(int x = v; x!=w; x = this.edgeTo[x]) {
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
        // 递归回溯时，当前结点重置为不在环的堆栈上。
        this.onStack[v] = false;
    public boolean hasCycle(int v){
        return cycle!=null;
    public Iterable<Integer> cycle(){
        return cycle;
上面检测有向图是否有环的算法采用标准的递归dfs算法，添加了一个布尔型数组onStack[] 来保存递归调用期间栈上面的所有顶点。当找到一条边 v->w 且w在栈中时，就代表找到了有向环。环上所有顶点都可以通过edgeTo[]数组得到。




    
 
3. 顶点的深度优先次序与拓扑结构
 
在优先级限制下的調度问题等价于计算有向无环图中的所有顶点的拓扑排序，因此给出如下API： 
public class Topological 
Topological(Digraph digraph) 拓扑排序的构造函数
boolean isDAG() 图digraph是有向无环图嘛？
Iterable<Integer> order() 拓扑排序的所有顶点 
 定理：当且仅当一幅图是有向无环图时才能进行拓扑排序。也就是有向无环图才有拓扑排序。 
首先我们先来看看 有向图中基于深度优先搜索的顶点排序 的DepthFirstOrder算法。 
其基本思想是：深度优先搜索正好只会访问每个顶点一次，如果将dfs()的参数顶点保存在一个数据结构中，遍历这个数据结构实际上就能访问图中的所有顶点，遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是调用之后进行保存。在应用中我们关注的是以下3种排列顺序： 
前序：在递归调用之前将顶点加入队列
后序：在递归调用之后将顶点加入队列
逆后续：在递归调用之后将顶点压入栈。 
下图是用DepthFirstOrder 算法处理有序无环图产生的轨迹。实现简单，支持处理图的高级算法中十分有用的pre()、post()和reversePost()方法。 例如Topological类中order()方法就调用了reversePost()方法。 
算法实现如下： 
package com.example.algorithm4.graphs;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
 * 有向图中基于深度优先搜索的顶点排序
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
public class DepthFirstOrder {
     * 从起点开始DFS访问过的路径标记
    private boolean[] marked;
     * 所有顶点的前序排列
    private Queue<Integer> pre;
     * 所有顶点的后序排列
    private Queue<Integer> post;
     * 所有顶点的逆后序排列
    private Stack<Integer> reversePost;
    public DepthFirstOrder(Digraph digraph) {
        marked = new boolean[digraph.V()];
        pre = new LinkedList<>();
        post = new LinkedList<>();
        reversePost = new Stack<>();
        for (int v=0; v<digraph.V(); v++){
            if ( !marked[v] ) {
                dfs(digraph, v);
     * 从节点v 开始有向图的DFS
     * @param digraph 有向图
     * @param v 结点
    private void dfs(Digraph digraph, int v){
        pre.add(v);
        this.marked[v] = true;
        for (int w : digraph.adj(v)){
            if(!this.marked[w]){
                dfs(digraph, w);
        post.add(v);
        reversePost.push(v);
    public Iterable<Integer> pre(){
        return pre;
    public Iterable<Integer> post(){
        return post;
    public Iterable<Integer> reversePost(){
        return reversePost;
该类允许使用各种顺序遍历DFS经过的顶点。这在高级的有向图处理算法中非常有用，因为搜索的递归性是的我们能够证明这段计算的许多性质。 
下面给出拓扑排序==Topological==的实现算法： 
package com.example.algorithm4.graphs;
 * 有向无环图的 拓扑排序
 * @author 惜暮
 * @email chris.lyt@alibaba-inc.com
 * @date 2017/12/7
public class Topological {
     * 顶点的拓扑排序
    private Iterable<Integer> order;
    public Topological(Digraph digraph){
        DirectedCycle cycleFinder = new DirectedCycle(digraph);
        if( !cycleFinder.hasCycle() ) {
            DepthFirstOrder dfs = new DepthFirstOrder(digraph);
            order = dfs.reversePost();
    public Iterable<Integer> order() {
        return order;
    public boolean isDAG(){
        return order!=null;
Topological的实现借助了DirectedCycle 检测环是否存在，借助DepthFirstOrder的逆后续来获取拓扑排序。 
 定理：一幅有向无环图的拓扑排序就是所有顶点的逆后续排列。 
 在任意一条边v->w， 在调用dfs(v) 时，下面三种情况，必有一种成立： 
 （1）dfs(w) 已经被调用过了，且已经返回了。 (w节点已经被标记true了) 
 （2）dfs(w)还没有被调用(w还没被标记)， 因此v->w 会直接或则间接调用并返回dfs(w)，且dfs(w)会在dfs(v)之前返回。 
 （3）dfs(w)已经被调用但还没返回。证明的关键在于，在DAG中，这种情况是不可能出现的。由于递归调用链的特性意味着存在从w到v的路径，但又存在v->w的边，所以存在一个环。 
 在上面(1)(2)两种情况中dfs(w) 会在dfs(v)之前完成，也就是后续排列中w排在v之前。 所以在逆后序中w排在v之后，因此任意一条边v->w 都如我们所愿地从排名比较靠前的顶点指向排名靠后的顶点。 
 定理：使用深度优先算法对有向无环图进行拓扑排序所需要时间和 (V+E) 成正比。 
 证明：从DirectedCycle和DepthFirstOrder的实现可知，两次搜索都访问了所有顶点和边，所以时间和（V+E）成正比。 
下面给出了一个示例 DAG 的逆后续是拓扑排序的轨迹图： 
五. 有向图中的强连通性
 
 定义：有向图中，如果两个顶点v和w是互相可达的，则称它们为强连通的。也就是说存在一条从v到w的有向路径，也存在一条从w到v的有向路径。 如果一幅有向图中任意两个顶点都是强连通的，则称这幅有向图也是强连通的。 
1. 强连通分量
 
有向图的强连通性也是一种顶点之间的平等关系，因为其有着如下性质： 
自反性：任意顶点v和自己都是强连通的。
对称性：如果v和w是强连通的， 那么w和v也是强连通的。
传递性：如果v和w是强连通的且w和x也是强连通的 ，那么v和x也是强连通的。 
强连通分量就是：有向图的极大强连通子图 
2.强连通分量应用
 
最典型应用就是网络，以顶点代表网页，超链接代表边。 下面给强连通分量的API： 
public class SCC 
SCC(Digraph digraph) 预处理构造函数
boolean stronglyConnected(int v, int w) v和w是强连通的吗？
int count() 图中强连通分量的总数
int id(int v) v所在强连通分量的标识符(0至count()-1 之间) 
3. 计算强连通分量的Kosaraju算法(无)
 
4. 再谈可达性(无)
 
六. 总结(无)

                    有向图一. 有向图的相关术语在有向图中，边是单向的：每条边连接的两个顶点都是一个有序对，它们的邻接性是单向的。我们开发过程中碰到的很多场景都是有向图：比如任务調度的依赖关系，社交网络的任务关系等等都是天然的有向图。以下概念都是针对有向图的：（1）==有向图==：一幅有向图是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点。（2）==顶点的出度==：该顶...
了解不同的数据结构的优势和弱点，考虑如何利用它们改进编程的效率 
学会如何用面向对象的编程简化数据结构和算法 
本书以一种易懂的方式教授如何安排和操纵数据的问题，其中不乏一些难题；了解这些知识以期使计算机的应用获得最好的表现。
不管使用何种语言或平台，掌握了数据结构和算法将改进程序的质量和性能。 
书中提供了一套独创的可视讨论专题用以阐明主要的论题；它使用JAVA语言说明重要的概念，而避免了C/C++语言的复杂性，以便集中精力论述数据结构和算法。 
经验丰富的作者Robert Lafore先生提供了许多简单明了的例子，避免了对于这类命题常见的冗长、繁琐的数学证明。在第二版中，他利用Java语言最新特性，修改并扩充了他的例子。在每一章后都有问题和练习，使读者有机会测试自己的理解程序。
【原 书 名】 Data Structures & Algorithms in Java 
【原出版社】 SAMS 
【作　　者】[美]Robert Lafore [同作者作品] [作译者介绍] 
【译　　者】 计晓云[同译者作品] 赵研 曾希 狄小菡 
【丛 书 名】 国外经典计算机科学教材 
【出 版 社】 中国电力出版社　 【书 号】 7508319117 
【出版日期】 2004年2月 【开 本】 16开 【页 码】 560 【版 次】2-1 
本书以一种易懂的方式教授如何安排和操纵数据的问题，其中不乏一些难题；了解这些知识以期使计算机的应用获得最好的表现。不管使用何种语言或平台，掌握了数据结构和算法将改进程序的质量和性能。 
书中提供了一套独创的可视讨论专题用以阐明主要的论题；它使用Java语言说明重要的概念，而避免C/C++语言的复杂性，以便集中精力论述数据结构和算法。 
经验丰富的作者Robert Lafore先生提供了许多简单明了的例子，避免了对于这类命题常见的冗长、繁琐的数学证明。在第二版中，他利用Java语言最新特性，修改并扩充了他的例子。在每一章后都有问题和练习，使读者有机会测试自己的理解程序。 
第1章 综述 
数据结构和算法能起到什么作用？ 
数据结构的概述 
算法的概述 
面向对象编程 
对于C++程序员的Java 
Java数据结构的类库 
第2章 数组 
Array专题Applet 
Java中数组的基础知识 
将程序划分成类 
Ordered专题applet 
有序数组的Java代码 
大O表示法 
为什么不用数组表示一切？ 
第3章 简单排序 
如何排序？ 
几种简单排序之间的比较 
第4章 栈和队列 
不同的结构类型 
优先级队列 
解析算术表达式 
第5章 链表 
链结点（Link） 
LinkList专题Applet 
查找和删除指定链结点 
链表的效率 
抽象数据类型 
第6章 递归 
递归的二分查找 
汉诺（Hanoi）塔问题 
一些有趣的递归应用 
第7章 高级排序 
第8章 二叉树 
为什么使用二叉树？ 
二叉搜索树如何工作 
插入一个节点 
查找最大值和最小值 
二叉树的效率 
用数组表示树 
重复关键字 
完整的tree.java程序 
哈夫曼（Huffman）编码 
第9章 红-黑树 
本章讨论的方法 
平衡树和非平衡树 
使用RBTree专题applet 
用专题applet做试验 
插入一个新节点 
红-黑树的效率 
红-黑树的实现 
其他平衡树 
第10章 2-3-4树和外部存储 
2-3-4树的介绍 
Tree234专题applet 
2-3-4树的Java代码 
2-3-4树和红-黑树 
2-3-4树的效率 
第11章 哈希表 
哈希化简介 
开放地址法 
哈希化的效率 
哈希化和外部存储 
第12章 堆 
Heap专题applet 
堆的Java代码 
基于树的堆 
第13章 图 
最小生成树 
有向图的拓扑排序 
有向图的连通性 
第14章 带权图 
带权图的最小生成树 
最短路径问题 
每一对顶点之间的最短路径问题 
第15章 应用场合 
通过数据结构 
专用数据结构 
附录A 运行专题applet和示例程序 
专题applet 
Sun Microsystem软件开发工具集 
重名的类文件 
其他开发系统 
附录B 进一步学习 
数据结构和算法 
面向对象程序语言 
面向对象设计（OOD）和软件工程 
附录C 问题答案 
第1章，综述 
第2章，数组 
第3章，简单排序 
第4章，栈与队列 
第5章，链表 
第6章，递归 
第7章，高级排序 
第8章，二叉树 
第9章，红-黑树 
第10章，2-3-4树和外部存储 
第11章，哈希表 
第12章，堆 
第13章，图 
第14章，带权图
				数据结构是计算机软件的一门基础课程,计算机科学各个领域及有关的应用软件都要用到各种数据结构．语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表、集合、搜索树及各种有向图等等。学习数据结构目的是要熟悉一些最常用的数据结构，明确数据结构内在的逻辑关系，知道它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，进一步提高软件计和编程水平。通过对不同存储结构和相应算法的对比，增强我们根据求解问题的性质选择合理的数据结构，并将问题求解算法的空间、时间及复杂性控制在一定范围的能力。同时，对于考研复习也是一份不错的知识总结哦！
				最短路（Bellman-Ford，Dijsktra，SPFA，Johnson，Floyd），差分约束，最小生成树（Kruskal，Prim，Boruvka），有向图与无向图连通性（割点，割边，E-BCC 和 SCC 的缩点），欧拉回路。
适合刚接触C++，并对基础数据结构有所了解（栈，二叉树，队列等），对建图有一定要求，需要熟练运用编程语言，掌握如vector,set,map等
				数据结构是计算机软件的一门基础课程,计算机科学各个领域及有关的应用软件都要用到各种数据结构．语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统运用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表、集合、搜索树及各种有向图等等。学习数据结构目的是要熟悉一些最常用的数据结构，明确数据结构内在的逻辑关系，知道它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，进一步提高软件计和编程水平。通过对不同存储结构和相应算法的对比，增强我们根据求解问题的性质选择合理的数据结构，并将问题求解算法的空间、时间及复杂性控制在一定范围的能力。
一幅有方向的图（或有向图）是由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点
处理有向图就如同在一座只有单行道的城市中穿梭，而且这些单行道的方向是杂乱无章的。
我们使用邻接表来表示有向图。
有向图取反的操作很有用，它返回该有向图的一个副本，但将其中所有的边反转。这样用例就可以找出“指向”每个顶点的所有边。
class 
出版时间：2012年版
　　《现代数学译丛（21）：欧拉图与相关专题》是迄今为止唯一的一本全面阐述欧拉图理论的主要研究成果和研究方法及其与其他图论问题之间的联系的专著。本书包含两卷共十章。第一卷从欧拉的哥尼斯堡七桥问题开始，由浅入深地介绍了欧拉问题的起源，给出图的基本概念和预备知识，然后相继地介绍了无向图、有向图以及混合图中欧拉迹的结构性定理，欧拉迹的若干推广，各种类型的欧拉迹，欧拉迹的变换。在第二卷中，详尽地介绍了著名的中国邮递员问题，欧拉迹的计数问题，最后讨论了与欧拉问题相关的算法和计算复杂性。每章后面配有习题，帮助读者理解和掌握本章的主要内容。《现代数学译丛（21）：欧拉图与相关专题》适合从事图论研究的研究生和科研工作者使用，也是其他数学和计算机科学研究人员很好的参考书。
第1章 引言
第2章 欧拉图理论的三个支柱
第3章 基本概念和预备知识
3.1 混合图与它们的基本要素
3.2 图与混合有向图的子图
3.3 导出子图
3.4 路径、迹、路、圈、树；连通度
3.5 相容性，K*V的循环序和对应的欧拉迹
3.6 匹配、1-因子、2-因子、1-因子分解、2-因子分解、二部图
3.7 图的曲面嵌入、同构
3.8 平面图的着色
3.9 哈密顿圈
3.10 关联矩阵和邻接矩阵、流和张力
3.11 算法及其复杂性
3.12 注记
第4章 特征定理和推论
4.1 图
4.2 有向图
4.3 混合图
4.4 习题
第5章 再论欧拉迹及其推广展望
5.1 迹分解，路、圈分解
5.2 奇偶性结果
5.3 双迹
5.4 交叉边界：图的分拆
5.5 习题
第6章 欧拉迹的各种类型
6.1 回避特定转移的欧拉迹
6.1.1 有向图中户（0）相容欧拉迹
6.1.2 双欧拉有向图中的反欧拉迹和图的双欧拉定向
6.1.3 有向图中的do-偏好欧拉迹
6.2 两两相容欧拉迹
6.2.1 有向图中的两两相容欧拉迹
6.3 平面欧拉图中的斗迹
6.3.1 平面欧拉图中的a-迹和平面3-正则图中的哈密顿圈之间的对偶性
6.3.2 欧拉图中的a-迹和哈密顿圈
6.3.3 如何找出a-迹：一些复杂性讨论和算法的建议
6.3.4 关于非交叉欧拉迹和a-迹的注记以及另一问题
6.4 习题
第7章 欧拉迹的变换
7.1 图中任意欧拉迹的变换
7.2 特殊的欧拉迹的变换
7.2.1 特殊类型的欧拉迹和k1-变换的应用
7.3 有向图中的欧拉迹的变换
7.4 最终注解及一些未解决的问题
7.5 习题
第8章 各种类型的闭覆盖途径
8.1 双迹
8.2 图中的值-真途径和整流
8.3 中国邮递员问题
8.3.1 关于图上的中国邮递员问题
8.3.2 有向邮递员问题
8.3.3 混合邮递员问题
8.3.4 带风向的邮递员问题和最后注记
8.4 习题
第9章 欧拉迹及其数目
9.1 有向图和（混合）图的奇偶性的结果
9.1.1 矩阵代数的一个应用
9.2 计数初涉
9.2.1 矩阵树定理
9.2.2 有向图和图的欧拉迹计数
9.2.3 关于欧拉定向的数目
9.2.4 拜斯特定理的应用和推广
9.2.5 其他说明
9.3 习题
第10章 欧拉迹和圈分解的算法及迷宫搜索算法
10.1 欧拉迹的算法
10.2 圈分解算法
10.3 迷宫
10.4 习题
对第一卷的更正和补录
人名译名表
《欧拉图与相关专题》是迄今为止唯一的一本全面阐述欧拉图理论的主要研究成果和研究方法及其与其他图论问题之间的联系的专著。《欧拉图与相关专题》包含两卷共十章。第一卷从欧拉的哥尼斯堡七桥问题开始，由浅入深地介绍了欧拉问题的起源，给出图的基本概念和预备知识，然后相继地介绍了无向图、有向图以及混合图中欧拉迹的结构性定理，欧拉迹的若干推广，各种类型的欧拉迹，欧拉迹的变换。在第二卷中，详尽地介绍了著名的中国邮递员问题，欧拉迹的计数问题，最后讨论了与欧拉问题相关的算法和计算复杂性。每章后面配有习题，帮助读者理解和掌握本章的主要内容。
《欧拉图与相关专题》适合从事图论研究的研究生和科研工作者使用，也是其他数学和计算机科学研究人员很好的参考书。
				有向图、无向图
有向图和无向图是我们常用到的术语，本文属于简单的科普帖。
全部由无向边构成图称为无向图（Undirected Graph）,全部由有向边构成图称为无向图（Directed Graph）。有向，顾名思义，有方向。本文中顶点Vertex（V），边Edge（E）
（1）出度和入度：如图D，以点A为例子，在所有与A关联的边中，以A为起点的边的条数称为出度。而入度则刚好相反，以A为终点的边的...
定义1：有向图
设V是一个非空集合，A是一个由V中元素的有序对构成的多重集，有序对D = &lt;V, A&gt;称为一个有向图，其中，V称为顶点集，其中的元素称为顶点或点；A称为弧集，其中的元素是弧。
  由定义可见，有向图和无向图的区别仅仅在于有向图的弧集是有序对的多重集，而无向图的边集是无序顶点对的多重集，无向图的一切概念均可平移到有向图。
定义2：入度、出度
设D是一个有向图，D...
### 回答2：
Python的networkx库是一个广泛使用的Python软件包，用于创建、操作和分析复杂的网络。 它支持多种类型的网络，包括带权值和无权值的有向图、无向图和多图。 进一步，它可以应用于网络分析、图形可视化、生物信息学、社交网络分析、计算机视觉等领域。
网络图是由节点和边（连接节点的线或箭头）组成的图，可以很好地表达各种关系。 通过将节点和边连接成图，网络可视化可以帮助我们轻松地理解各种关系和模式。
在Python中，我们可以使用networkx库创建和可视化有向图。下面的代码演示了如何创建和可视化一个简单的有向图：
```python
import networkx as nx
import matplotlib.pyplot as plt
# 创建一个空有向图
G = nx.DiGraph()
# 添加节点
G.add_node("A")
G.add_node("B")
G.add_node("C")
G.add_node("D")
# 添加边
G.add_edge("A", "B")
G.add_edge("B", "C")
G.add_edge("C", "D")
G.add_edge("D", "A")
# 可视化图形
nx.draw(G, with_labels=True)
plt.show()
在这个例子中，我们首先导入了networkx和matplotlib.pyplot库。然后，我们创建了一个名为G的空有向图。我们添加了四个节点A、B、C和D，然后添加了四个边连接这些节点。最后，我们使用nx.draw函数将图可视化。
当我们运行上面的代码时，我们可以看到一个正方形的有向图，其中四个节点A、B、C和D通过箭头连接起来。节点有标签，边没有。
我们还可以改变节点的形状、颜色和大小，添加标签和权重等。networkx库拥有丰富的可视化选项和函数，可以帮助我们创建更复杂的图形。   
### 回答3：
Python Networkx是一个基于Python语言的强大图形可视化工具。它被广泛用于在Python中创建和操作不同类型的图，包括有向图。通过使用Python语言和Networkx库的强大功能，可以轻松地创建高质量、具有可视化效果的有向图。
要使用Python Networkx来画有向图，需要按照以下步骤：
1.  首先，需要安装Python Networkx。通过pip安装即可。
2.  创建一个空的有向图。这可以通过使用networkx库中的DiGraph（）方法实现。
3.  添加有向图中的节点。可以用add_node()方法。
4.  建立有向边。 可以使用add_edge()方法，指定起点和终点。
5.  通过使用matplotlib或其他可视化库，可以使有向图更容易可视化，并可进行必要的图形布局和排版。
下面是一个示例代码，该示例代码将通过Networkx和matplotlib绘制有向图：
```python
import networkx as nx
import matplotlib.pyplot as plt
# 创建一个有向图
G = nx.DiGraph()
# 添加节点
G.add_node('A')
G.add_node('B')
G.add_node('C')
# 添加边
G.add_edge('A', 'B')
G.add_edge('B', 'C')
# 绘制图形
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_size=500, node_color='lightblue')
nx.draw_networkx_edges(G, pos, width=2, arrowstyle='->', arrowsize=10)
nx.draw_networkx_labels(G, pos, font_size=12, font_family='sans-serif')
plt.axis('off')
plt.show()
在上面的代码中，首先导入了网络X和matplotlib库。然后通过DiGraph()方法创建一个空的有向图，并使用add_node()方法添加节点。然后，使用add_edge()方法添加边，并使用spring_layout使用Spring布局算法分配节点位置。最后，通过使用matplotlib函数draw_networkx_nodes、draw_networkx_edges和draw_networkx_labels绘制图形。
绘制有向图是python Networkx中最常见的操作之一，python Networkx帮助我们轻松地创建和操作不同类型的图，从而创建具有可视化效果的图形。无论是作为工程师还是数据科学家，每个人都能够受益于Networkx强大的可视化能力。
public class DirectedDFS
DirectedDFS(DiGraph G, int s)	在G中找到从s可达的所有顶点
`DirectedDFS(DiGraph G, Iterable<Integer> sources)`	在G中找到从sources的所有顶点中可达的所有顶点
boolean reachable(int v)	d顶点v是可达的嘛
public class DirectedCycle
DirectedCycle(Digraph digraph)	寻找有向环的构造函数
boolean hasCycle()	digraph是否有环
`Iterable<Integer> cycle()`	有向环中的所有顶点
public class Topological
Topological(Digraph digraph)	拓扑排序的构造函数
boolean isDAG()	图digraph是有向无环图嘛？
`Iterable<Integer> order()`	拓扑排序的所有顶点
public class SCC
SCC(Digraph digraph)	预处理构造函数
boolean stronglyConnected(int v, int w)	v和w是强连通的吗？
int count()	图中强连通分量的总数
int id(int v)	v所在强连通分量的标识符(0至count()-1 之间)