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

图的基本概念及遍历图的运算

如果数据元素集合D中的各元素之间存在任意的前后件关系R,则此数据结构G=(D,R)称为图。

奥林匹克信息学联赛的许多试题,需要用图来描述数据元素间的联系,需要用图的经典算法来解题,例如:用结点代表城市,每条边代表连接两个城市间的公路,边长的权表示公路长度。这种公路网的表现形式就是属于图的数据结构。图的基本概念图的的定义

如果数据元素集合D中的各元素之间存在任意的前后件关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前件，这种前后件关系对应的边用(a，b)表示，即(a，b)∈E。⑵有向图：如果对于任意的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)∈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为一条回路连通图和最大连通子图对于无向图而言，若其中任两个结点之间的连通，则称该图为连通图。一个无向图的连通分支定义为此图的最大连通子图。上图所示的图是连通的，它的最大连通子图即为其本身。强连通图和强连通分支

若对于有向图的任意两个结点vi、vj间（vi≠vj），都有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称该有向图是强连通的。有向图中强连通的最大子图称为该图的强连通分支。上图不是强连通的,因为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]；{顶点的访问标志序列}相邻矩阵的特点

⑴无向图的相邻矩阵是对称的,而有向图则不是。无向图的相邻矩阵a1[i][j]=a1[j][i](1≤I,j≤n)且对角线上的a[i][i]均为0（或±∝）。正因为如此，在实际存储相邻矩阵时只需存储其上三角(或下三角)的元素。因此具有n个结点的无向图，其相邻矩阵的存储容量可节约至n(n-1)/2。而有向图的相邻矩阵中a2[i][j]不一定与a2[j][i](1≤i，j≤n)相同，且图中出现自反边时其对角线上的a2[i][i]也不一定是0（或±∝）。占用的存储单元数只与结点数有关而与边数无关。一个含n个结点的图，若其边数比n2少得多，那么其相邻矩阵是一个稀疏矩阵，占用许多空间来存储0（或±∝）当然是无端浪费。⑵相邻矩阵方便度数的计算。用相邻矩阵表示图，容易判定任意两个结点之间是否有边相联，并容易求得各个结点的度数。对于无权无向图的相邻矩阵，第i行元素值的和就是Vi的度数；对于有权无向图的相邻矩阵，第i行（或第i列）中元素值<>±∝的元素个数就是Vi的度数；对于无权有向图的相邻矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；对于有权有向图的相邻矩阵，第i行中元素值<>±∝的元素个数就是Vi的出度；第i列元素值<>±∝的元素个数就是Vi的入度。⑶容易计算路径的存在性。在无权有向图或无向图中，判定两个结点Vi、Vj之间是否存在长度为m的路径，只要考虑am=a*a*……*a（m个a矩阵相乘后的乘积矩阵）中（i，j）的元素值是否为0就行了。(4)占用的存储单元数只与结点数有关而与边数无关。一个含n个结点的图，若其边数比n2少得多，那么其相邻矩阵是一个稀疏矩阵，占用许多空间来存储0（或±∝

）当然是无端浪费。深度优先搜索深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。其搜索过程如下：假设初始时所有结点未曾被访问。深度优先搜索从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先搜索遍历图的过程是以V0为起始点，由左而右，依次访问由V0出发的每条路径。从v3出发，按深度优先搜索的顺序遍历，得到的结点序列是v3→v2→v1→v5→v4。深度优先搜索相邻矩阵初始化；voiddfs(inti)//深搜{intj;访问处理结点i;f[i]=true;//置结点i为已访问标记for(j=1;j<=n;j++)//按深度优先搜索的顺序遍历vi所有子树if(!f[j]&&a[i][j]==1)dfs(j);}调用一次dfs(i),可按深度优先搜索的顺序访问处理结点i所在的连通分支(或强连通分支)。整个图按深度优先搜索顺序遍历的过程如下：voidtravel(){memset(f,0,sizeof(f));//置所有结点未访问标志for(i=1;i<=n;i++)if(!f[i])dfs(i);//深度优先搜索每一个未访问的结点}深度优先搜索广度优先搜索广度优先搜索类似于树的按层次遍历的过程，其搜索过程如下：假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度优先顺序搜索遍历图的过程是以v0为起始点，由近及远，依次访问和v0有路径相连且路径长度为1，2，3……的结点。

memset(f,0,sizeof(f));//访问标志初始化f[s]=true;q[1]=s;//访问源点，源点入队open=1;closed=1;//队列的首尾指针初始化while(open<=closed)//若队列非空,则访问与队首元素相连的未访问点,计算其路径长度,并将它们送入队列{for(i=1;i<=n;i++)if((f[i]==false)&&(a[q[open]][i]!=0)){访问顶点i;f[i]=true;closed++;q[closed]=i;}open++;//出队}}调用一次bfs(i)可按广度优先搜索的顺序访问处理结点i所在的连通分支(或强连通分支)。整个图按广度优先搜索顺序遍历的过程如下：

voidtravel(){memset(f,0,sizeof(f));//置所有结点未访问标志

for(i=1;i<=n;i++)

if(!f[i])bfs(i);//广度优先搜索每一个未访问的结点}14356782输入：81014151626273534375758编程实现：输入下图,按深度优先遍历和广度优先遍历输出图的结点。145Cin>>x>>y>>z;A[x][y]=z;犯罪团伙1703警察抓到了n个罪犯,警察根据经验知道他们属于不同的犯罪团伙,却不能判断有多少个团伙,但通过警察的审讯,知道其中的一些罪犯之间相互认识,已知同一犯罪团伙的成员之间直接或间接认识。有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系,确定犯罪团伙的数量。已知罪犯的编号从1至n。输入：第一行：n(<=1000,罪犯数量),第二行：m(<5000,关系数量)以下若干行：每行两个数：I和j,中间一个空格隔开,表示罪犯i和罪犯j相互认识。输出：一个整数,犯罪团伙的数量。样例输入：118124354135671051089输出：3说明：共三个犯罪团伙。【培训试题】位图1866#include<iostream>usingnamespacestd;intdx[4]={-1,0,1,0},dy[4]={0,1,0,-1};chara[200][200];intf[200][200],p[400][4],i,j,k,m,n,ans;boolused[200][200];voidbfs(intx,inty){inti,x1,y1,open,closed;p[1][1]=x;p[1][2]=y;p[1][3]=0;open=1;closed=1;memset(used,0,sizeof(used));if(a[x][y]=='1')return;while(open<=closed){for(i=0;i<4;i++){x1=p[open][1]+dx[i];y1=p[open][2]+dy[i];if(x1>0&&x1<=n&&y1>0&&y1<=m&&!used[x1][y1]){closed++;p[closed][1]=x1;p[closed][2]=y1;p[closed][3]=p[open][3]+1;used[x1][y1]=true;if(a[x1][y1]=='1'){ans=p[closed][3];return;}}}open++;}}【培训试题】位图1866intmain(){cin>>n>>