我们也可以在有向图中寻找欧拉回路与欧拉路径。与无向图中类似,我们只要抓住进入每个点和离开每个点的边数关系,就能得到有向图中存在欧拉回路或欧拉路径的判定条件。
对于欧拉回路,进入每个点和离开每个点的边数是一样的,因此有向图存在欧拉回路的判定条件为:
一张有向图中存在欧拉回路,当且仅当所有非零度节点是弱连通的(把所有有向边都看成无向边后,得到的无向图是连通的,则称原来的有向图是弱连通的),且每个节点的出度(以该点为起点的边数)等于入度(以该点为终点的边数)。
对于欧拉路径,除了起点和终点以外,进入每个点和离开每个点的边数是一样的。而对于起点,进入起点的边数要恰好比离开起点的边数少 1。对于终点,进入终点的边数要恰好比离开终点的边数多 。因此有向图存在欧拉路径的判定条件为:
一张有向图中存在欧拉路径,当且仅当所有非零度节点是弱连通的,且至多一个节点的入度比出度少 ,至多一个节点的入度比出度多 ,剩下的点入度等于出度。
仍然可以使用 Hierholzer 算法寻找有向图中的欧拉回路与欧拉路径,只要从路径起点开始深度优先搜索即可。若所有节点入度等于出度,路径起点就是任意一个非零度节点,否则路径起点就是入度比出度少 的那个节点。另外,因为是有向边,因此 Hierholzer 算法不需要删除反向边。