有向图

方向记录“谁作用于谁”。若 $u\to v$ 表示一个页面能直接跳转到另一个页面，从 $u$ 到 $v$ 可点击过去，并不保证可以沿同一条边回来；若表示任务依赖，还需要说明箭头到底指向依赖项还是被依赖者，不能只凭图形猜约定。

无向边仅记录两个端点的连接，方向信息则可能改变整个问题。把单向道路抹去箭头后，地图看起来连通，并不说明驾车可以从任意地点到任意地点。相应地，有限简单无向图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。与有向图可以相互转换表示，但转换是否保留要研究的性质，需要逐项检查。

直接相邻与经过多步能到达也不是同一关系。只有 $u\to v$ 与 $v\to w$ 两条弧时，$u$ 能到达 $w$，但弧 $u\to w$ 不存在。若把所有不同的可达顶点对补成弧，就保留了可达性，却改变了入度、出度以及按边数计算的最短距离：原先从 $u$ 到 $w$ 要走两步，补弧后只需一步。因此按可达性补边不能在所有算法中替换原图。若直接把下文的自反传递闭包当作弧集，还会为每个顶点加入自环，须切换到允许自环的图模型。

路线、长度与可达关系 ​

有向游走是顶点序列 $v_0,\dots ,v_k$，满足每个相邻有序对 $v_{i-1}\to v_i$ 都是弧，长度为 $k$。游走允许重复顶点；简单有向路径要求顶点不重复。若存在从 $u$ 到 $v$ 的游走，就称 $v$ 从 $u$ 可达，记作 $u⇝v$。对不同端点，删除重复段可以把一条可达游走变成简单路径。

本条目允许长度 $0$ 的路径，所以总有 $u⇝u$。因此可达关系是弧关系的自反传递闭包：

这里 $A^k$ 表示恰有 $k$ 步游走连接的端点对。只从 $A$ 开始取正长度的并集得到 $A^{+}$，称传递闭包；它不一定含每个 $(v,v)$。例如一条单弧 $u\to v$ 的图中，$u$ 在长度 $0$ 意义下可达自身，却没有从 $u$ 回到 $u$ 的正长度游走。

有向环是一条正长度闭合游走，除首尾重合外各顶点不同。在无自环约定下，有向环最少长 $2$：$u\to v$ 与 $v\to u$ 可以构成二元环。这与简单无向图通常至少三条边的环不同。

弱连通不等于强连通 ​

忽略方向后连通，称弱连通；任意两顶点都能沿方向互相到达，称强连通。取

逐点统计可得出度依次为 $1,2,1,1$，入度依次为 $1,1,2,1$，两组总和都是弧数 $5$。从 $a$ 出发可沿 $a\to b\to c\to d$ 访问全部顶点；从 $c$ 出发却只能在 $c,d$ 之间往返，因为没有弧从这两个顶点离开该集合。

忽略方向后是一条连通链。强连通分量是 $\{a,b\}$ 与 $\{c,d\}$，分量之间只有从前者到后者的方向。这个例子也说明：“存在一个能到达所有点的起点”仍弱于强连通，后者要求每一个起点都能做到。

定义 $u\sim v$ 当且仅当 $u⇝v$ 且 $v⇝u$。长度 $0$ 路径保证自反，定义本身保证对称，拼接路径保证传递，因此它是等价关系，等价类恰好给出强连通分量。每个顶点，包括孤立顶点，都属于一个分量。

方向化与双向化是不同转换 ​

给无向图每条边选择一个方向，得到它的一个定向；把每条无向边 $\{u,v\}$ 替成两条反向弧，则得到双向表示。后一转换保留了无向路径的可通行性，却会使每条边都产生有向二元环。所以“原图是一棵树”并不意味着这种双向有向图是 DAG。

弧权也不能与弧的存在混为一谈。权重为 $0$ 的弧仍是弧；没有弧不应在最短路距离矩阵中被无条件编码成 $0$，否则会凭空产生免费的通路。

压缩循环后得到 DAG ​

将每个强连通分量缩成一个顶点，删掉分量内部弧，并把跨分量弧按端点去重，得到凝聚图。它一定是DAG公理库有向无环图Directed acyclic graph · DAG不含有向环的有向图。：如果几个不同分量在凝聚图中构成有向环，它们之间便能互相到达，应该本来就是同一个强连通分量，矛盾。

因此许多有循环的依赖系统可以先分出“内部互相影响的块”，再研究块之间的无环顺序。这没有消除块内部的反馈；它只是把循环与非循环部分分开处理。

拓扑排序尊重方向，而不是忽略方向 ​

DAG 的拓扑序是一个顶点排列，使每条弧 $u\to v$ 的起点都出现在终点之前。有限有向图存在拓扑序，当且仅当没有有向环。无环时，总能找到一个入度为 $0$ 的顶点：若每个顶点都有前驱，不断追溯前驱就会因顶点有限而重复，产生环。删除一个零入度顶点后继续此过程即可排序。

邻接表能让一次完整 DFS 或 BFS 在 $O(|V|+|A|)$ 时间内扫描图；反向图交换所有弧的起终点，可把“谁能到达目标”转成从目标出发的可达搜索。最短路、网络流和程序控制流都在这些基本对象上增加各自的约束，方向、权重和路径允许规则需在应用入口处说明。

代数中还可在每个顶点放一个向量空间、每条箭放一个线性映射，形成箭图表示公理库箭图表示Quiver representation · Representation of a quiver从协同换基定义箭图表示，分类单箭头矩阵，并用平行箭参数与复合秩说明维数和各箭秩为何不足。；其有限箭图采用上面 $(V,A,s,t)$ 的有向多重图变体，平行箭保留各自的线性映射，环对应同一空间的自同态。路径代数公理库路径代数Path algebra由可复合路径构造代数，证明箭图表示与模的双向对应，并将三顶点链落实为六维下三角矩阵代数。则把可连接路线作为基，把路径串接变成乘法。