(算法几何和设计）图基本概念、图遍历算法.ppt

图基本概念、图遍历算法
2
主要内容
图的基本概念
图的相邻矩阵及邻接表的表示方法
图抽象数据类型
图的周游方法
求图的最小生成树(林)
3
图的基本概念
反映连通关系
反映连通属性
应用:约束求解(二维参数化草图、三维装配),三维模型特征识别,三维模型的B_Rep表达(点、线、面);
4
图与其他数据结构的关系
线性结构:唯一前驱,唯一后继,线性关系
树形结构:唯一前驱,多个后继,层次关系
图形结构:多对多、任意,网状关系
图结构中结点(图中通常称为顶点)的前驱和后继结点个数不再限制,即结点之间的关系是任意的
图是更复杂的非线性结构。
5
图由顶点(vertex)集合和边(edge)集合E组成,
记为G=(V,E)。
每条边就是一个顶点的偶对,所以E也就是V上的一个二元关系。
例如:
V = { a,b,c,d};
E = {<a,b>, <a,d>, <c,d>, <d,a>}
图的形式化定义
a
b
c
d
6
在有向图中,<V1,V3> 表示从V1到V3的一条边,也称弧(尖括号表示)。V1为弧尾或始点,V3为弧头或终点。
在无向图中,(V1,V3)表示V1和V3之间的一条边。
(V1,V3) = (V3,V1) 无序对
V1
V3
V2
V4
V1
V3
V2
V4
有向图无向图
7
图顶点与边的关系
图G的顶点数n和边数e满足以下关系∶
若G是有向图,则0≤e≤n(n-1)
有向完全图:有n(n-1)条边的有向图
若G是无向图,则0≤e≤n(n-1)/2
无向完全图:有n(n-1)/2条边的无向图
在顶点个数相同的图中,完全图具有最多的边数
V1
V3
V2
V4
8
‘度’的定义
关联:由一个顶点发出的边构成与该定点的一个关联。
顶点的度:与该顶点关联的所有的边或弧的数目。
(邻接点的个数定义为顶点的度。)
入度:(仅对有向图)以该顶点为头的弧数。
V3
V1
V2
V4
V5
V6
9
路径
无向图中的顶点序列v1,v2,…,vk,若(vi,vi+1)E( i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路;
有向图中的顶点序列v1,v2,…,vk, 若<vi,vi+1>E ( i=1,2,…k-1),
v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径;若v=u,则称该序列为回路;
路径上边或弧的数目称为该路径的路径长度。
10
连通图
在无(有)向图G =( V, E )中,若对任何两个不同顶点v、u都存在从v到u的路径,则称G是连通图。
V5
V1
V2
V4
V3
连通图
V3
V1
V2
V4
V5
V6
非连通图