资源描述：
《图—基本概念与抽象数据类型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图—基本概念与抽象数据类型2008/05/20主要内容图的基本概念图抽象数据类型图的周游方法图的相邻矩阵及邻接表的表示方法求图的最小生成树（林）2图的基本概念反映连通关系反映连通属性V1V3V2V4e1e3e234图与其他数据结构的关系线性结构：唯一前驱，唯一后继，线性关系树形结构：唯一前驱，多个后继，层次关系图形结构：多对多、任意，网状关系图结构中结点(图中通常称为顶点)的前驱和后继结点个数不再限制，即结点之间的关系是任意的图是更复杂的非线性结构。4图由顶点（vertex）集合和边（edge）集合E组成，记为G=(V，E)。每条边就是一个顶点的偶对，所以E
2、也就是V上的一个二元关系。例如：V={a,b,c,d};E={,,,}图的形式化定义abcd5在有向图中，表示从V1到V3的一条边，也称弧（尖括号表示）。V1为弧尾或始点，V3为弧头或终点。在无向图中，(V1，V3)表示V1和V3之间的一条边。(V1,V3)=(V3,V1)无序对V1V3V2V4V1V3V2V4有向图无向图6图顶点与边的关系图G的顶点数n和边数e满足以下关系∶若G是有向图，则0≤e≤n(n-1)有向完全图：有n(n-1)条边的有向图若G是无向图，则0≤e≤n(n-1)/2无向完全图：有n(
3、n-1)/2条边的无向图在顶点个数相同的图中，完全图具有最多的边数V1V3V2V47‘度’的定义关联：由一个顶点发出的边构成与该定点的一个关联。顶点的度：与该顶点关联的所有的边或弧的数目。(邻接点的个数定义为顶点的度。)入度：（仅对有向图）以该顶点为头的弧数。V3V1V2V4V5V68路径无向图中的顶点序列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,
4、u=vk,则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路；路径上边或弧的数目称为该路径的路径长度。9连通图在无（有）向图G=(V,E)中，若对任何两个不同顶点v、u都存在从v到u的路径，则称G是连通图。V5V1V2V4V3连通图V3V1V2V4V5V6非连通图10图的其他一些相关概念子图：对于G=(V，E)，G’=(V’，E’)如果有V’inV&&E’inE，则称G’为G的子图。带权图（网络）：每条边加上权值信息。带权图也常被称为‘加权图’。带权图中的路径通常定义为路径之上所有边的权值总和。BACD63215411ADTGraphisoper
5、ationsGraphcreateGraph(void)//创建一个空图intisNullGraph(Graphg)//判断图g是否空图VertexfirstVertex(Graphg)//找图中的一个顶点VertexnextVertex(Graphg,vi)//找图中顶点vi的下一个连通顶点VertexsearchVertex(Graphg,DataTypevalue)//查找图中值为value的顶点GraphaddVertex(Graphg,DataTypevalue)//在图g中增加一个值为value的顶点intfindEdge(Graphg,Vert
6、exvi,Vertexvj)//返回顶点v相关联的第一条、下一条边。VertexfirstAdjacent(Graphg,Vertexv)/*v与返回顶点构成的边也称为与v相关联的第一条边。*/找图g中与vi相邻的，相对相邻顶点vj的，下一个相邻顶点VertexnextAdjacent(Graphg,Vertexvi,Vertexvj)/*vi与返回值构成的边也称为是vi与vj构成的边的下一条边。*/图的操作与抽象数据类型…12基于抽象数据类型的图的周游算法图的周游是一种按某种方式系统地访问图中的所有结点的过程，它使每个结点都被且只被访问一次。图的周游也称图
7、的遍历。若图是连通（无向）图或强连通（有向）图，则从图中任意一顶点出发，都可以延某一路径找到图中所有顶点。否则就不然。深度优先：类似于二叉树的深度优先。广度优先：类似于二叉树的广度优先。13深度优先周游先访问图中某个（未访问过的）结点V，然后选择一个V邻接到的未被访问过的结点W，再访问W，并按同样方法前进；当遇到一个所有邻接于它的结点都被访问过了的结点时，退回到已访问结点序列中最后—个拥有相邻结点未被访问过的结点，访问它的一个未被访问过的相邻结点U，再从U出发按同样方法前进。当所有已被访问过的结点的相邻结点都被访问时，如果图中还有未被访问的顶点，则从另一未被
8、访问过的顶点出发重复上述过程，直到图中所有顶点都被访
