一个有向图D是指一个有序
三元组(V(D)，A(D)，ψD)，其中ψD)为
关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对．
相关概念
孤立点：V中不与E中任一条边关联的点称为D的孤立点．
简单图：不含平行边的图称为简单图．
完备图：图中任两个顶点U与u之间，恰有两条有向边(u，v)，及(v，u)，则称该有向图D为完备图．
基本图：把有向图D的每条边除去定向就得到一个相应的无向图G，称G为D的基本图．称D为G的定向图．
强连通图：给定有向图G=(VE)，并且给定该图G中的任意两个
结点u和v，如果结点u与结点v相互
可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止，那么就称该有向图G是强连通图。
弱连通图:若至少有一对结点不满足单向连通，但去掉边的方向后从无向图的观点看是
连通图，则D称为弱连通图．
单向连通图:若每对结点至少有一个方向是连通的，则D称为单向连通图.
强连通分支:有向图G的极大强连通子图称为该有向图的强连通分支。
有向通路：
邻接矩阵
除了孤立顶点外，任意顶点都至少与一条边相关联，因此，任何有向图，不考虑孤立顶点，可以由其边集完全描述．例如，如果D的边如下：
(1，1)，(1，2)，(1，3)，(1，4)，(2，2)，(2，3)，(2，4)，(3，3)，(3，4)，(4，4)，
注意，我们是按照字典序列出D的边的，只不过这里不是a，b，c，…，而是1，2，3.....
依照这种思想，我们可以用
矩阵来完全地描述任何有向图，这就是有向图的邻接矩阵．
最短路的求解
对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：
路径和
路权。
可达性
对于一个
无向图来说，如果它是
连通的，那么它的任意两个顶点之问必存在一条路径，因此，通过这一路径可从一个顶点“到达”另一个顶点，若从顶点“可以到达u，则从u也可以到达“，也即v和u之间是互相可以到达的。
对于有向图，情形就不同了，因为存在从u到v的路径，并不蕴涵也存在从v到u的路径。
设D是一个有向图，且u、v∈D，若存在从顶点u到顶点v的一条路径，则称从顶点v到顶点u可达。
可达的慨念与从u到v的各种路径的数目及路径的长度无关。另外，为了完备起见，规定任一顶点到达它自身的是可达的。
可达性是一个有向图顶点的二元关系，依照定义，它是自反的，且是传递的。一般来说，可达不是对称的，也不是反对称的。