网站结构优化怎么做,网站开发美工,做电路方案设计的网站,下载的网站模板如何安装图是一种#xff1a; 数据元素间存在多对多关系的数据结构 加上一组基本操作构成的抽象数据类型。
图 (Graph) 是一种复杂的非线性数据结构#xff0c;由顶点集合及顶点间的关系#xff08;也称弧或边#xff09;集合组成。可以表示为#xff1a; G#xff1d;(V, V…图是一种 数据元素间存在多对多关系的数据结构 加上一组基本操作构成的抽象数据类型。
图 (Graph) 是一种复杂的非线性数据结构由顶点集合及顶点间的关系也称弧或边集合组成。可以表示为 G(V, VR)
其中 V 是顶点的有穷非空集合
VR 是顶点之间 关系的有穷集合也叫做弧或边集合。
弧是顶点的有序对边是顶点的无序对。 特点相对于线性结构
顶点之间的关系是任意的
图中任意两个顶点之间都可能相关
顶点的前驱和后继个数无限制 相关概念 顶点(Vertex)图中的数据元素。线性表中我们把数据元素叫元素树中将数据元素叫结点。
边顶点之间的逻辑关系用边来表示边集可以是空的。 无向边(Edge)若顶点V1到V2之间的边没有方向则称这条边为无向边。
无向图(Undirected graphs)图中任意两个顶点之间的边都是无向边。A,DD,A
无向图中边的取值范围0≤e≤n(n-1)/2
有向边若从顶点V1到V2的边有方向则称这条边为有向边也称弧(Arc)。用V1,V2表示V1为狐尾(Tail)V2为弧头(Head)。V1V2≠V2V1。
有向图(Directed graphs)图中任意两个顶点之间的边都是有向边。
有向图中弧的取值范围0≤e≤n(n-1) 注意无向边用“”而有向边用“ ”表示。 简单图图中不存在顶点到其自身的边且同一条边不重复出现。
无向完全图无向图中任意两个顶点之间都存在边。
有向完全图有向图中任意两个顶点之间都存在方向互为相反的两条弧。
稀疏图有很少条边。
稠密图有很多条边。 邻接点若 (v, v´) 是一条边则称顶点 v 和 v´互为 邻接点或称 v 和 v´相邻接称边 (v, v´) 依附于顶点 v 和 v´或称 (v, v´) 与顶点 v 和 v´ 相关联。 权Weight与图的边或弧相关的数。
网Network带权的图。
子图Subgraph假设GV,{E}和G‘V,{E}如果V包含于V且E包含于E则称G为G的子图。 入度有向图中以顶点 v 为头的弧的数目称为 v 的入度记为ID(v)。
出度有向图中以顶点 v 为尾的弧的数目称为 v 的出度记为OD(v)。
度Degree无向图中与顶点V相关联的边的数目。有向图中入度表示指向自己的边的数目出度表示指向其他边的数目该顶点的度等于入度与出度的和。 回路环第一个顶点和最后一个顶点相同的路径。
简单路径序列中顶点两端点除外不重复出现的路径。
简单回路简单环前后两端点相同的简单路径。
路径的长度一条路径上边或弧的数量。 连通从顶点 v 到 v´ 有路径则说 v 和 v´ 是连通的。
连通图图中任意两个顶点都是连通的。
连通分量无向图的极大连通子图不存在包含它的 更大的连通子图
任何连通图的连通分量只有一个即其本身非连通图有多个连通分量非连通图的每一个连通部分。
强连通图 任意两个顶点都连通的有向图。
强连通分量有向图的极大强连通子图任何强连通 图的强连通分量只有一个即其本身非强连通图有多个 强连通分量。 生成树所有顶点均由边连接在一起但不存在回路的图。n个顶点n-1条边
