给定图G=.设G中定点和边的交替序列为v0e1e2…el.若T满足如下条件:v(i-1)和vi是ei的端点(G为有向图时要求v(i-1)是ei的始点,vi是ei的终点),i=1,2…,l,则称T为v0到vl的通路。vo,vl分别称为此通路的起点和终点。T中所含边的数目l称为T的长度。当v0=vl时,称通路为回路。在无向图G中,若顶点vi与vj之间存在通路,则称vi与vj是连通的。规定vi与自身是连通的。设D为一个有向图。如果略去D中各边的方向所得的无向图是连通图,则称D是弱连通图或连通图。若D中任意2顶点至少一个可达另一个,则称D是单向连通图。若D中任意2顶点都是相互可达的,则称D是强连通图。通过以上定义我们容易知道:有向图的强连通图一定是回路,否则不可互达。无向图的连通图不是回路,但是有回路的无向图一定是连通的。连通分量是指无向图中的极大连通子图。有向图中的极大强连通子图称做有向图的强连通分量。所以只需对所给出的图做分解就可得出。