高中信息竞赛-数据结构-图基本概念及搜索遍历

《高中信息竞赛-数据结构-图基本概念及搜索遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的基本概念及遍历图的运算如果数据元素集合D中的各元素之间存在任意的前后件关系R,则此数据结构G=(D,R)称为图。奥林匹克信息学联赛的许多试题,需要用图来描述数据元素间的联系,需要用图的经典算法来解题,例如:用结点代表城市,每条边代表连接两个城市间的公路,边长的权表示公路长度。这种公路网的表现形式就是属于图的数据结构。图的基本概念图的的定义如果数据元素集合D中的各元素之间存在任意的前后件关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为

2、G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前件，这种前后件关系对应的边用(a，b)表示，即(a，b)∈E。无向图和有向图⑴无向图：在图G=（V，E）中，如果对于任意的a，b∈V，当(a，b)∈E时，必有（b，a）∈E（即关系R对称），对称此图为无向图。在一无向图中用不带箭头的边连接两个有关联的结点。在具有n个结点的无向图中，边的最大数目为n*(n-1)/2。而边数达到最大值的图称为无向完全图。在无向图中一个结点相连的边数称为该结点的度，无向完全图中，每一个顶点的

3、度为n-1。无向完全图。结点1、结点2、结点3、结点4的度分别为3⑵有向图：如果对于任意的a,b∈V,当(a,b)∈E时,(b,a)∈E未必成立，则称此图为有向图。在有向图中,通常用带箭头的边连接两个有关联的结点(方向由前件指向后件)。有向图中一个结点的后件个数称为该结点的出度,其前件个数称为该结点的入度。有向图结点1的出度和入度分别为1，结点1和结点1度都为2路径和连通集在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1……xk(k>1)⑴x1=a，xk=b⑵(xi，xi+1)

4、∈Ei=1‥k-1则称结点序列x1=a，x2，…，xk=b为结点a到结点b的一条路径，而路径上边的数目k-1称为该路径的长度，并称结点集合{x1，…，xk}为连通集。x1=ax2…xk=b简单路径和回路如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。x1=xk的简单路径称为回路（也称为环）。v1→v2→v3是一条简单路径，v1→v3→v4→v1→v3不是简单路径v1→v2→v1为一条回路有根图在一个有向图或无向图中，若存在一个结点w，它与其他结点都是连通

5、的，则称此图为有根图，结点w即为它的根。有根图，v1、v2、v3、v4都可以作为根有根图，v1或v2为它的根。连通图和最大连通子图对于无向图而言，若其中任两个结点之间的连通，则称该图为连通图。一个无向图的连通分支定义为此图的最大连通子图。上图所示的图是连通的，它的最大连通子图即为其本身。强连通图和强连通分支若对于有向图的任意两个结点vi、vj间（vi≠vj），都有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称该有向图是强连通的。有向图中强连通的最大子图称为该图的强连通分支。上图不

6、是强连通的,因为v3到v2不存在路径.它含有两个强连通分支图的存储结构图的相邻矩阵表示法相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*n;a[n+1][n+1]1(或权值)表示顶点i和顶点j有边(i和j的路程)a[i][j]=0表示顶点i和顶点j无边inta[maxn+1][maxn+1]；boolf[maxn+1]；{顶点的访问标志序列}有向图的相邻矩阵中[i][j]不一定与[j][i](1≤I,j≤n)相同,且图中出现

7、自反边时其对角线上的[i][i]也不一定是0（或±∝）。无向图的相邻矩阵[i][j]=[j][i](1≤I,j≤n)且对角线上的[i][i]均为0（或±∝）。正因为如此，在实际存储相邻矩阵时只需存储其上三角(或下三角)的元素。因此具有n个结点的无向图，其相邻矩阵的存储容量可节约至(n-1)n/2。相邻矩阵的特点⑴无向图的相邻矩阵是对称的,而有向图则不是。无向图的相邻矩阵a1[i][j]=a1[j][i](1≤I,j≤n)且对角线上的a[i][i]均为0（或±∝）。正因为如此，在实际存储相邻矩阵时只需存

8、储其上三角(或下三角)的元素。因此具有n个结点的无向图，其相邻矩阵的存储容量可节约至n(n-1)/2。而有向图的相邻矩阵中a2[i][j]不一定与a2[j][i](1≤i，j≤n)相同，且图中出现自反边时其对角线上的a2[i][i]也不一定是0（或±∝）。占用的存储单元数只与结点数有关而与边数无关。一个含n个结点的图，若其边数比n2少得多，那么其相邻矩阵是一个稀疏矩阵，占用许多空间来存储0（或±∝）当然是无端浪费。⑵相邻矩阵方便度数的计算。用相邻矩阵表示