有向图 · aiwiki.page

有向图（英文为 directed graph，亦称 digraph）是由顶点及连接有序顶点对的有向边组成的数学结构。边 $u\to v$ 从 $u$ 指向 $v$ ，并不意味着存在反方向的边。有向图是图论的研究对象。(algs4.cs.princeton.edu)

定义与约定

对于不含平行边的有向图，标准的集合表示为

G=(V,E),\qquad E\subseteq V\times V,

其中， $V$ 是顶点集， $V\times V$ 是它的笛卡尔积。每条边都是一个有序对 $(u,v)$ ，其中 $u$ 为尾顶点， $v$ 为头顶点。因此，边集也可以看作 $V$ 上的一个二元关系。(networkx.org)

对于允许出现哪些边，不同定义有不同约定。自环是连接一个顶点与其自身的边。平行边具有相同的有序端点；允许平行边便得到有向多重图，此时必须区分每一条边，而不能仅记录端点对。方向相反的边 $u\to v$ 和 $v\to u$ 并不是平行边。定义时应明确是否允许自环和平行边。(algs4.cs.princeton.edu)

定向图（oriented graph）在一种常见的较狭义用法中，是对简单无向图的每条边指定方向后得到的图。因此，它不允许同一对顶点之间存在方向相反的两条边；并非所有有向图都是定向图。(en.wikipedia.org)

度

出度 $d^+(v)$ 是从 $v$ 出发的边数，入度 $d^-(v)$ 则是进入 $v$ 的边数。一个自环对出度和入度各贡献一次计数。对于有限有向图，

\sum_{v\in V}d^+(v)=\sum_{v\in V}d^-(v)=|E|.

这是因为每条边都恰好有一个尾顶点和一个头顶点。入度为零的顶点通常称为源点，出度为零的顶点称为汇点。(en.wikipedia.org)

游走、可达性与连通性

有向游走沿各条边指定的方向行进，可以重复经过顶点或边。按照本文采用的约定，有向路径不包含重复顶点。有向环是长度大于零的闭合有向游走，除起点与终点相同外，不重复经过任何顶点。不同文献对路径相关术语的用法有所不同。(arxiv.org)

如果存在从 $u$ 到 $v$ 的有向路径，就称从 $u$ 可达 $v$ ；当 $u=v$ 时，允许使用长度为零的路径。如果任意顶点都能到达其他任意顶点，则称该图是强连通的。图的强连通分量是由相互可达的顶点组成的极大顶点集合。相互可达是一种等价关系，因此这些分量构成顶点集的一个划分。(algs4.cs.princeton.edu)

如果忽略边的方向后得到的无向图是连通的，则称原图是弱连通的。弱连通并不意味着强连通：单独一条边 $u\to v$ 在忽略方向时连接了这两个顶点，却没有提供从 $v$ 到 $u$ 的路径。(en.wikipedia.org)

表示方法

对于顶点 $v_1,\ldots,v_n$ ，邻接矩阵是满足下式的矩阵 $A$ ：

A_{ij}=\text{从 }v_i\text{ 到 }v_j\text{ 的边数}.

若没有平行边，矩阵元素只能为零或一。各行元素之和给出相应顶点的出度，各列元素之和给出相应顶点的入度。与无向图的邻接矩阵不同， $A$ 不一定对称。对于正整数 $k$ ， $(A^k)_{ij}$ 表示长度为 $k$ 的有向游走的数量，这些游走不一定是不含重复顶点的路径。(math.mit.edu)

邻接表表示法存储每个顶点的出邻居，即从该顶点出发的边所指向的顶点。这种表示法需要 $O(|V|+|E|)$ 的空间，遍历某个顶点的所有出边所需的时间与该顶点的出度成正比。将每条边的方向反转便得到反向图，它可用于找出哪些顶点能够到达某个指定顶点。(github.com)

无环图与算法

有向无环图（DAG）不包含有向环。有限有向图存在拓扑排序，当且仅当它是有向无环图；在这种顶点排序中，每条边都从排在前面的顶点指向排在后面的顶点。这样的排序不一定唯一。(algs4.cs.princeton.edu)

基本算法包括用于判断可达性和检测环的深度优先搜索、用于求解无权图中最短路径问题的广度优先搜索，以及求强连通分量的算法。采用邻接表时，这些任务都可以在 $O(|V|+|E|)$ 时间内完成。(algs4.cs.princeton.edu)

应用

有向图用于表示非对称关系，例如网页之间的超链接、单向通行的交通连接，以及任务之间的依赖关系。在调度问题中，一条边可以表示某项任务必须先于另一项任务完成；当依赖图无环时，拓扑排序便能给出一个有效的执行顺序。有向图还用于表示马尔可夫链中可能发生的状态转移，以及计算机内存中对象之间的引用关系。(algs4.cs.princeton.edu)

参考来源

Directed Graphsalgs4.cs.princeton.edu
DiGraph—Directed graphs with self loops — NetworkX documentationnetworkx.org
Digraph.java — algs4github.com
Directed graphen.wikipedia.org
Directed Graphs — lecture slidesalgs4.cs.princeton.edu
Number of paths in a grapharxiv.org
Adjacency matrix of G — MIT lecture notesmath.mit.edu
Evaluating Matrix Functions by Resummations on Graphs: the Method of Path-Sumsarxiv.org
Topological.javaalgs4.cs.princeton.edu