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

* 广度优先周游算法 1、每个顶点包含一个mark字段，在周游前所有顶点的mark字段均被置为FALSE，周游到该结点时将相应的mark字段改为TRUE。 2、在bft中调用函数bfs ( g , v )，从顶点v出发按广度优先周游g中能访问的各个顶点。 具体实现中使用一个队列q，队列元素的类型为Vertex。 * 广度优先算法的实现 void bfs ( Graph g , Vertex v ){ Vertex v1, v2; Queue q = createEmptyQueue ( ); /* 队列元素的类型为Vertex */ enQueue ( q ,v ) ; while ( !isEmptyQueue(q) ) { v1 =frontQueue ( q ) ; deQueue ( q ); //get a node from queue v1.mark = TRUE ; //set start from mark v2 = firstAdjacent ( g ,v1 ); //get nodes, enQueue while ( v2!=NULL ) { if ( v2.mark == FALSE ) enQueue ( q, v2 ); v2 = nextAdjacent ( g , v1 , v2 ) ; } } } AAG（Attributed Adjacency Graph） * * * * * 图基本概念、图遍历算法 * 主要内容 图的基本概念 图的相邻矩阵及邻接表的表示方法 图抽象数据类型 图的周游方法 求图的最小生成树（林） * 图的基本概念 反映连通关系 反映连通属性 应用：约束求解（二维参数化草图、三维装配），三维模型特征识别，三维模型的B_Rep表达（点、线、面）； * 图与其他数据结构的关系 线性结构：唯一前驱，唯一后继，线性关系 树形结构：唯一前驱，多个后继，层次关系 图形结构：多对多、任意，网状关系 图结构中结点(图中通常称为顶点)的前驱和后继结点个数不再限制，即结点之间的关系是任意的 图是更复杂的非线性结构。 * 图由顶点（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 * 在有向图中，V1，V3 表示从V1到V3的一条边，也称弧（尖括号表示）。V1为弧尾或始点，V3为弧头或终点。 在无向图中，(V1，V3)表示V1和V3之间的一条边。 (V1,V3) = (V3,V1) 无序对 V1 V3 V2 V4 V1 V3 V2 V4 有向图无向图 * 图顶点与边的关系 图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 * ‘度’ 的定义 关联：由一个顶点发出的边构成与该定点的一个关联。 顶点的度：与该顶点关联的所有的边或弧的数目。 (邻接点的个数定义为顶点的度。) 入度：（仅对有向图）以该顶点为头的弧数。 V3 V1 V2 V4 V5 V6 * 路径 无向图中的顶点序列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，则称该序列为回路； 路径上边或弧的数目称为该路径的路径长度。 * 连通图 在无（有）向图G =( V, E )中，若对任何两个不同顶点v、u都存在从v到u的路径，则称G是连通图。 V5 V1 V2 V4 V3 连通图 V3 V1 V2 V4 V5 V6 非连通图 * 图的其他一些相关概念 子图： 对于 G=(V，E) ， G’ =(V’，E’) 如果有 V’ in V E’ in E， 则称G’为