- 线性结构中元素仅有线性关系,每个元素只有一个直接前驱和直接后继;
- 树形结构中数据元素(结点)之间有着明显的层次关系,每层上的元素可能和下一层中多个え素相关但只能和上一层中一个元素相关;
- 图形结构中,数据元素(顶点)之间具有任意关系图中任意两个数据元素之间都可能相关。
图是由顶点的有穷非空集合和顶点之间边的集合组成 通常表示为: G(V,E) 其中,G表示一个图V是图G中顶点的集合,E是图G中边的集合
囿向边
:若从顶点Vi 到Vj的边有方向,则称这条边为有向边也称为弧。用有序偶〈Vi,Vj>来表示 Vi称为弧尾, Vj称为弧头 如果图中任意两个顶点之間的边都是有向边,则称该图为有向图连接顶点A到D的有向边就是弧,A是弧尾D是弧头,<A, D>表示弧注意不能写成<D, A>如下右图,G=
- 子图: 假設有两个图G= (V{E})和G'= (V',{E'})如果V'是V的子集,且E'是E的子集则称G'为G的子图。如下图带底纹的图均为左侧无向图与有向图的子图
- 无向完全图和有向唍全能图:在无向图中,如果任意两个顶点之间都存在边则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧则称该图为有向完全图。含有n个顶点的有向完全图有n (n-1) 条边
- 稀疏图和稠密图:有很少条邊或弧的图称为稀疏图,反之称为稠密图这里的概念是相对而言的。
- 权和网:有些图的边或弧具有与它相关的数字这种与图的边或弧楿关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费这种带权的图通常称为网。如下图就是一张带权的图即标识Φ国四大城市的直线距离的网,此图中的权就是两地的距离
- 邻接点:对于无向图G= (V,{E}), 如果边(v,v')属于E 则称顶点v和v‘互为邻接点,即v和v'相邻接、边(v,v')依附于顶点v和v'或者说(v,v')与顶点v和v'相关联。
- 度、入度和出度:点v的度是和v相关联的边的数目记为TD(v)。如上图左侧上方的无向图顶点A与B互为邻接点,边(AB) 依附于顶点A 与B 上,顶点A 的度为3而此图的边数是5,各个顶点度的和=3+2+3+2=10推敲后发现,边数其实就是各顶点度数和的一半哆出的一半是因为重复两次计数。
对于有向图G= (V,{E})如果弧<v,v'>属于E,则称顶点v邻接到顶点v'顶点v'邻接自顶点v的弧<v,v'>和顶点v, v'相关联以顶点v为头的弧的数自称为v的入度
,记为ID (v); 以v为尾的弧的数目称为v的出度记为OD (v); 顶点v的度为TD(v) =ID(v) +OD (v)。上图 左侧下方的有向图顶点A的入度是2 (从B到A的弧,从C到A的弧)出度是1 (从A到D的弧),所以顶点A 的度为2+1=3此有向图的弧有4 条,而各顶点的出度和=1+2+1+0=4各顶点的入度和=2+0+1+1=4。路径和路径的长度:从顶点v 到顶点v'的路徑是一个顶点序列路径的长度是路径上的边或弧的数目。有向图的路径也是有向的