西安商城网站制作,青岛网站网站建设,书店网站的建设,做网站宽高怎么决定一、数据结构的回忆
线性结构#xff1a;#xff08;一对一#xff09; 除首结点没有前驱、末尾结点没有后继外#xff0c;一个结点只有唯一的一个直接前驱和唯一的一个直接后继。
树结构#xff1a;#xff08;一对多#xff09; 除根节点没有前驱节点外#xff0c;…一、数据结构的回忆
线性结构一对一 除首结点没有前驱、末尾结点没有后继外一个结点只有唯一的一个直接前驱和唯一的一个直接后继。
树结构一对多 除根节点没有前驱节点外其余的每个节点只有唯一的一个前驱节点和多个后继结点。
图多对多
任意两个节点之间都可能有直接的关系图中一个节点的前驱节点和后继结点的数目没有限定。 二、图的定义
图是由集合V和E构成的二元组记作G(V, E) 。
V图中定点的非空有限集合数据元素
E图中边的有限集合数据元素之间的关系
示例 出度有向图有某个顶点为起点的边的个数称为该顶点的出度。
入度无向图有某个顶点为终点的边的个数称为该顶点的出度。
度有向图、无向图入度 出度 无向图、有向图 边数e 每个顶点的度相加/2 路径指图中从一个顶点出发依次经过若干个顶点到达另一个顶点的一条路线。其中经过的每个顶点在路径中只出现一次
路径长度路径上边、弧的数目
回路指从某个顶点出发经过若干个顶点后回到该顶点的路径。其中经过的每个顶点在路径中只出现一次除了起点和终点重合的情形。
简单路径在一个图中从一个顶点到另一个顶点之间没有重复经过任何顶点的路径。简单路径是一条路径其中顶点没有重复出现。 三、特殊的图
3-1、有向图
图中每条边都是有方向的顶点之间的关系用Vi, Vj表示它说明从Vi到Vj的一条有向边(也称为弧)。Vi是有向边的起点称为弧尾Vj是有向边的终点称为弧头。 Vi, Vj和Vj, Vi分别表示两条边。 示例 3-1-1、强连通图
有向图中每一对顶点ViVj从顶点 Vi到顶点Vj和从顶点 Vj到顶点Vi都存在路径。 强连通图n个节点最少有n条边最多有n(n-1)条边 3-2、无向图
图中的每条边都是无方向的顶点Vi和Vj之间的边用(ViVj) 表示。 在无向图中(ViVj) 与(VjVi) 表示的是同条边。 示例 3-2-1、连通图
无向图中任意两个顶点都是连通的任意两个顶点都有路径
【注意】
不一定非的是直接路径
例如顶点1到顶点5有路径(v1, v3)、(V3, V5) 无向连通图n个节点最少有n-1条边最多有n(n-1)/2条边 3-3、完全图
一个图中有n个顶点每个顶点和其他n-1个顶点之间都有边。直接的边 完全图的分类 无向完全图 有向完全图 含有n个顶点的无向完全图共有n(n-1)/2条边。
含有n个顶点的有向完全图共有n(n-1)条边。 四、真题
真题1D 有向图、无向图边数为e所有顶点的度数之和为2e 真题2
