有向图与无向图
图是由一组顶点和边组成的数学结构。图表示通过某些链接(由边表示)连接的一组对象(由顶点表示)。使用数学符号,图可以用G表示,其中G=(V,E),V是顶点集,E是边集。在无向图中,没有与连接顶点的边相关联的方向。在有向图中,有一个方向与连接顶点的边相关联。
无向图
如前所述,无向图是一个图,其中在连接图中顶点的边上没有方向。图1描述了一个无向图,其中有一组顶点V={V1,V2,V3}。上图中的一组边可以写成V={(V1,V2),(V2,V3),(V1,V3)}。还可以注意到,由于边没有方向,因此没有任何东西可以阻止将边集写入V={(V2,V1),(V3,V2),(V3,V1)}。因此,无向图中的边不是有序对。这是无向图的主要特征。无向图可以用来表示由顶点表示的对象之间的对称关系。例如,连接一组城市的双向道路网可以用无向图表示。城市可以用图中的顶点表示,边表示连接城市的双向道路。
有向图
有向图是图中连接顶点的边有一个方向的图。图2描述了一个有向图,其中有一组顶点V={V1,V2,V3}。上图中的一组边可以写成V={(V1,V2),(V2,V3),(V1,V3)}。无向图中的边是有序对。形式上,有向图中的边e可以用有序对e=(x,y)表示,其中x是称为边e的原点、源或初始点的顶点,而顶点y称为终点、终点或终点。例如,使用单向道路连接一组城市的道路网可以使用无向图表示。城市可以用图中的顶点表示,有向边表示连接城市的道路,考虑到道路上交通流的方向。
有向图和无向图的区别是什么?