@buoge 2017-09-28T11:26:02.000000Z 字数 756 阅读 949

图

模型算法

定义14.20 设D=为一个有向图。vi,vj∈V，若从vi到vj存在通路，则称vi可达vj，记作vi→vj，规定vi总是可达自身的，即vi→vi.若vi→vj且vj→vi，则称vi与vj是相互可达的，记作vivj.规定vivi.
　　 →与都是V上的二元关系，并且不难看出是V上的等价关系。
定义14.21 设D=为有向图，vi,vj∈V，若vi→vj，称vi到vj长度最短的通路为vi到vj的短程线，短程线的长度为vi到vj的距离，记作d.

　　与无向图中顶点vi与vj之间的距离d(vi,vj)相比，d除无对称性外，具有d(vi,vj)所具有的一切性质。
定义14.22 设D=为一个有向图。若D的基图是连通图，则称D是弱连通图，简称为连通图。若vi,vj∈V ，vi→vj与vj→vi至少成立其一，则称D是单向连通图。若均有vivj，则称D是强连通图。
在图14.11中，（1）为强连通图，（2）为单连通图，（3）是弱连通图。由定义可知，强连通图一定是单向连通图，单向连通图一定是弱连通图

邻接表，邻接矩阵，十字链表，关注的是顶点信息
邻接多重表，边集数组，关注的是边的信息