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

1、( (算法几何和设计图根本概念、图遍历算法算法几何和设计图根本概念、图遍历算法7图顶点与边的关系图顶点与边的关系 图G的顶点数n和边数e满足以下关系 假设G是有向图，那么0en(n-1) 有向完全图：有n(n-1)条边的有向图 假设G是无向图，那么0en(n-1)/2 无向完全图：有n(n-1)/2条边的无向图 在顶点个数相同的图中，完全图具有最多的边数V1V3V2V48度度 的定义的定义关联：由一个顶点发出的边构成与该定点的一个关联。顶点的度：与该顶点关联的所有的边或弧的数目。 (邻接点的个数定义为顶点的度。)入度：仅对有向图以该顶点为头的弧数。 V3V3 V1V1 V2V2 V4V4 V5

2、V5 V6V69路径路径无向图中的顶点序列v1,v2, ,vk,假设(vi,vi+1)E( i=1,2,k-1), v =v1, u =vk, 那么称该序列是从顶点v到顶点u的路径；假设v=u，那么称该序列为回路；有向图中的顶点序列v1,v2, ,vk, 假设E ( i=1,2,k-1), v =v1, u =vk, 那么称该序列是从顶点v到顶点u的路径；假设v=u，那么称该序列为回路；路径上边或弧的数目称为该路径的路径长度。10连通图连通图 在无有向图G =( V, E )中，假设对任何两个不同顶点v、u都存在从v到u的路径，那么称G是连通图。 V5V5 V1V1 V2V2 V4V4 V3V

3、3连通图 V3V3 V1V1 V2V2 V4V4 V5V5 V6V6非连通图11图的其他一些相关概念图的其他一些相关概念子图： 对于 G=(V，E) ， G =(V，E) 如果有 V in V & E in E， 那么称G为G的子图。 带权图网络： 每条边加上权值信息。带权图也常被称为加权图。带权图中的路径通常定义为路径之上所有边的权值总和。BACD63215412图的存储结构图的存储结构1 邻接矩阵表示法邻接矩阵表示法 设图 G = (V,E) = (V,E) 一个有 n n个顶点的图 , , 图的邻接矩阵是一个二维数组 edgennedgenn，定义： 的边不是图或若的边是图或若Gvvvv

4、Gvvvvjiedgejijijiji,),(, 0,),(, 1,13vexs1=a, b, c, d ; vexs2=v1,v2,v3,v4,v500001001001000000101110002edge00110011110111101edge假定不存在指向自身的弧14邻接矩阵表示法的特点邻接矩阵表示法的特点 (1)无向图的关系矩阵一定是一对称矩阵。(2)无向图的关系矩阵的第i行(或第i列)非零元素个数为第i个顶点的度D(vi)。(3) 有向图的关系矩阵的第i行非零元素个数为第i个顶点的出度OD(vi)，第i列非零元素个数就是第i个顶点的入度ID(vi)。(4) 从图的邻接矩阵表示，很

5、容易确定图中任意两个顶点之间是否有边相连。添加或删除边也很方便。15 如果G是带权的图，wij是边(vi,vj)或的权，那么其关系矩阵定义为带权图的邻接矩阵表示带权图的邻接矩阵表示)(,),(,)(,),(,jiGvvvvjiGvvvvwjiweightjijijijiij的边不是图或若的边是图或若16邻接矩阵表示法结构定义邻接矩阵表示法结构定义typedef char VexType;typedef float AdjType;typedef struct int n; /* 图的顶点个数 */ VexType *vexs; /* 顶点信息 */ AdjType *arcs ; /* 边信息

6、，二维数组 */ GraphMatrix; 17带权图的邻接矩阵表示带权图的邻接矩阵表示用来存顶点信息18带权图的邻接矩阵表示带权图的邻接矩阵表示 矩阵初始化：19邻接矩阵操作函数邻接矩阵操作函数20邻接表表示法邻接表表示法 对图中每个顶点建立一个对图中每个顶点建立一个单链表，单链表， 第第i个单链表中的结点表示依附于个单链表中的结点表示依附于该顶点该顶点Vi的边或弧的边或弧21无向图邻接表无向图邻接表 v0 v1 v2 v3 v4 v5 v6 v7 v0 v1 v2 1 0 1 2 3 7 v3 v4 v5 v6 2 2 6 5 v7 3 4 4 0 5 6 1 7 22struct Edg

7、eNode;typedef struct EdgeNode * PEdgeNode; /edgeNode的指针typedef struct EdgeNode * EdgeList; /edgeNode 链表指针struct EdgeNodeint endvex;/* 相邻顶点在顶点表中下标 */AdjType weight; /* 边的权，非带权图应该省略 */PEdgeNode nextedge;/* 链字段 */;/* 边表中的结点 */typedef structVexType vertex;/* 顶点信息 */EdgeList edgelist;/* 边表头指针 */ VexNode;

8、/* 顶点表中的结点 */typedef structint n;/* 图的顶点个数 */VexNode *vexs; /*顶点表 */GraphList; /* 图的邻接表表示 */邻接表表示法结构定义23矩阵两种存储表示的空间开销比较矩阵两种存储表示的空间开销比较设图G有n个顶点，e条边. 图的邻接矩阵表示的空间代价为O(n2)；假设图G是无向图， 那么图的邻接表表示的空间代价为O(n+2e)；假设图G是有向图， 那么图的邻接表表示的空间代价为O(n+e);假设图中en2，那么用邻接表表示图比较节省空间，如果e到达n2数量级时，由于邻接表中增加了辅助的链域，采用邻接矩阵表示图更节省空间。特

9、别对于无权图而言，关系矩阵的每个元素实际上只要一个二进制位就可以表示。 24ADT Graph isoperationsGraph createGraph (void) /创立一个空图创立一个空图 int isNullGraph (Graph g ) /判断图判断图g是否空图是否空图Vertex firstVertex (Graph g ) /找图中的一个顶点找图中的一个顶点Vertex nextVertex (Graph g , vi ) /找图中顶点找图中顶点vi的下一个连通顶点的下一个连通顶点Vertex searchVertex (Graph g , DataType value )

10、/查找图中值为查找图中值为value的顶点的顶点Graph addVertex (Graph g , DataType value ) /在图在图g中增加一个值为中增加一个值为value的顶点的顶点int findEdge (Graph g , Vertex vi , Vertex vj ) /返回顶点返回顶点v相关联的第一条、下一条边。相关联的第一条、下一条边。Vertex firstAdjacent (Graph g , Vertex v ) /*v与返回顶点构成的边也称为与与返回顶点构成的边也称为与v相关联的第一条边。相关联的第一条边。*/找图找图g中与中与vi相邻的，相对相邻顶点相邻的

11、，相对相邻顶点vj的，下一个相邻顶点的，下一个相邻顶点Vertex nextAdjacent (Graph g , Vertex vi , Vertex vj ) /* vi与返回值构成的边也称为是与返回值构成的边也称为是vi与与vj构成的边的下一条边。构成的边的下一条边。*/图的操作与抽象数据类型图的操作与抽象数据类型25深度优先周游深度优先周游先访问图中某个未访问过的结点V，然后选择一个V邻接到的未被访问过的结点W，再访问W，并按同样方法前进；当遇到一个所有邻接于它的结点都被访问过了的结点时，退回到已访问结点序列中最后个拥有相邻结点未被访问过的结点，访问它的一个未被访问过的相邻结点U，再从

12、U出发按同样方法前进。当所有已被访问过的结点的相邻结点都被访问时，如果图中还有未被访问的顶点，那么从另一未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过时，周游结束。26深度优先周游深度优先周游算法算法从顶点v0出发进行深度优先周游，得到的一个DFS序列为v0，v1，v3，v7，v4，v2，v5，v6int marked8;27深度优先周游深度优先周游算法算法l需要对已访问的顶点作标记。l在顶点中增设一个标记字段mark。l需要用到栈结构或采用递归算法。l从一个顶点出发的搜索不一定能够访问到图中所有顶点。28从节点从节点v出发，出发，dfsg , vvoid dfs ( Graph

13、 g , Vertex v ) Vertex v1; v.mark = TRUE ; /标记字段markfor ( v1 = firstAdjacent ( g,v ); v1 != NULL; v1= nextAdjacent (g,v,v1) if ( v1.mark = FALSE ) dfs ( g ,v1 ); /*递归调用*/void dft ( Graph g ) Vertex v ; for ( v =firstVertex ( g ) ; v != NULL ; v = nextVertex ( g , v ) )if ( v.mark = FALSE ) dfs ( g ,

14、 v ) ; /尝试所有结点，图g不一定连通29非递归的深度优先周游图算法非递归的深度优先周游图算法1. 用栈记录走过的路径上的节点2. 访问过的节点作标记3. 走不通的时候通过退栈操作弹出节点，并用 nextAdjacent (g,v,v1)函数得到下一个分支的子树的头节点；如果v1不空，v再压回栈里。否那么，继续出栈，步骤330广度优先周游广度优先周游从图的某个未访问过的顶点v出发，先访问顶点v将其标记为已访问，接着依次访问v的所有未访问过的相邻结点w1，w2，wx，然后，再依次访问与w1，w2，wx邻接的所有未被访问过的顶点，以此类推，直到所有已访问顶点的相邻结点都被访问过。这时，如果图

15、中还有未被访问过的顶点，那么从某个未被访问过的顶点出发进行同样方法搜索，直到图中所有顶点都被访问过时，周游结束31广度优先周游算法广度优先周游算法从顶点v0出发的一个BFS序列为 v0, v1, v2, v3, v4, v5, v6, v7queue32广度优先周游算法广度优先周游算法 1、每个顶点包含一个mark字段，在周游前所有顶点的mark字段均被置为FALSE，周游到该结点时将相应的mark字段改为TRUE。2、在bft中调用函数bfs ( g , v )，从顶点v出发按广度优先周游g中能访问的各个顶点。 具体实现中使用一个队列q，队列元素的类型为Vertex。33广度优先广度优先算法的实现算法的实现void bfs ( Graph g , Vertex v )Vertex v1, v2;Queue q = createEmptyQueue ( );/* 队列元素的类型为Vertex */enQueue ( q ,v ) ;while ( !isEmptyQueue(q) ) v1 =frontQueue ( q ) ; deQu