有向图youxiangtu

图1

图2

（吴文虎）

比树更为一般化的数据结构.图中的数据元素通常称为顶点.数据元素间的关系，就是顶点间的邻接关系.有向图的顶点间的邻接关系称为弧，用带箭头的线表示.下图1表示一个有向图.假如图中的五个顶点分别表示城市1，城市2，…，城市5.顶点间的连线表示航线，箭头指出方向.从顶点1至顶点2，起点处称为弧尾，终点处称为弧头对城市1，有一条航线可达城市2，有一条航线可达城市5；对应图中有弧尾的数目为2，称顶点1的出度为2.只有城市3有一航线可达城市1，图中指向顶点1的弧头的数目为1，称顶点1的入度为1.

图1

图1

只有一个顶点的入度为0，而其余顶点的入度均为1的有向图，是一棵有向树，如图2，只有顶点1的入度为0.从这一点也可以说树是图的特例，图是比树更为一般化的数据结构.
图的应用极为广泛，诸如电子线路分析、系统工程、控制论、遗传学、逻辑学、语言学、计算机科学，以至社会科学中的许多学科，都把图结构作为解决问题的手段之一.

有向图

由若干点以及连接某些点所对的（有方向）弧构成的图。