在现实世界中,有种关联关系难以用数据库的表结构来表示,比如微博的粉丝关系、偶像剧中的N角恋、多个域名之间的注册关系等,于是图这种古老的数据结构就派上了用场。一般认为,如果给图的每条边规定一个方向,那么得到的图称为有向图,其边也称为有向边。在有向图中,与一个节点相关联的边有出边和入边之分,而与一个有向边关联的两个点也有始点和终点之分。相反,边没有方向的图称为无向图。我们拿一个实际的例子来讲解下用途最为广泛的有向图的一些基础知识。
微博中的好友关注关系就是典型的有向图(如图13-1所示),因为关注是有方向性的,比如我关注了钟丽缇,但是钟丽缇不一定关注了我。假定关注关系如下描述:
·A关注了C;
·B关注了A;
·C关注D;
·D关注了A和B。
图13-1 图算法原理图
D关注了两个人,所以他的出度为2,D被1个人关注,所以他的入度为1。
图的聚类算法,最简单的一种实现叫做连通分支,其原理如图13-2所示。所谓连通分支,指的是图中由边连接在一起的一组顶点,不要求顶点之间必须两两相连,但是连通分支的任意两个顶点之间,至少存在一条路径,计算连通分支时不区分有向图和无向图。
图13-2 图的连通分支原理图