第7章 图.

7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第7章图7.1图的定义和术语图：记为G＝(V,E)其中：V是G的顶点集合，是有穷非空集；E是G的边集合，是有穷集。问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。有向图：无向图：完全图：图G中的每条边都是有方向的；弧v,w图G中的每条边都是无方向的；边(v,w)图G任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图V=vertexE=edge证明：②完全有向图有n(n-1)条边。证明：若是完全有向图，则顶点1必与所有其他顶点各有2条连线，即有2(n-1)条边，顶点2有2(n-2)条边，…，顶点n-1有2条边,顶点n有0条边.总边数＝2(n-1＋n-2＋…＋1＋0)=2(n-1+0)n/2=n(n-1)①完全无向图有n(n-1)/2条边。证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，…，顶点n-1有1条边,顶点n有0条边.总边数＝n-1＋n-2＋…＋1＋0=（n-1+0)n/2=n(n-1)/2例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n(n-1)/2条边n(n-1)条边G1的顶点集合为V(G1)={0,1,2,3}边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图例245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={1,2,2,1,2,3,2,4,3,5,5,6,6,3}例157324G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}稀疏图：稠密图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。子图：边较少的图。通常边数n2enlogn边很多的图。无向图中，边数接近n(n-1)/2；有向图中，边数接近n(n-1)带权图：即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。＝带权图在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。强连通图：网络：有两类图形不在本章讨论之列：邻接点：有向边(u,v)称为弧，弧的始点u叫弧尾，终点v叫弧头顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。若(u,v)是E(G)中的一条边，则称u与v互为邻接点弧头和弧尾：度、入度和出度：生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。生成森林：问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。答：是树！而且是一棵有向树！简单路径：路径上各顶点v1,v2,...,vm均不互相重复。回路：例：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。路径：在图G＝(V,E)中,若从顶点vi出发,沿一些边经过一些顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vivp1vp2...vpmvj)为从顶点vi到顶点vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1连通图例245136强连通图356例非连通图连通分量例245136ADTGraph{数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}；VR={v,w|v,w∈V且P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}基本操作P：CreatGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中添加新顶点。………………（参见P156-157）}图的抽象数据类型注意：V的大小写含义不同！结构的建立和销毁插入或删除顶点对邻接点的操作对顶点的访问操作遍历插入和删除弧基本操作CreatGraph(&G,V,VR)://按定义(V,VR)构造图DestroyGraph(&G)://销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u);//若G中存在顶点u，则返回该顶点在//图中“位置”；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。对邻接点的操作FirstAdjVex(G,v);//返回v的“第一个邻接点”。若该顶点//在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接//点”。若w是v的最后一个邻接点，则//返回“空”。插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶点v及其相关的弧。插入和删除弧InsertArc(&G,v,w);//在G中增添弧v,w，若G是无向的，//则还增添对称弧w,v。DeleteArc(&G,v,w);//在G中删除弧v,w，若G是无向的，//则还删除对称弧w,v。遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。7.2图的存储结构图的特点：非线性结构（m:n）•邻接表•十字链表•邻接多重表设计为邻接矩阵链式存储结构：顺序存储结构：无！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法一、邻接矩阵（数组）表示法建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：v1v2v3v5v4v4A例1：无向图的邻接矩阵邻接矩阵：A.Edge=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。01010101010101110101011100101010101010111010101110顶点表：例2：有向图的邻接矩阵分析1：有向图的邻接矩阵一般是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A.Edge[i][j]顶点的入度=第i列元素之和。ID(Vi)=A.Edge[j][i]顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)v1v2v3v4A邻接矩阵：A.Edge=(v1v2v3v4)v1v2v3v40000000000000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：01100000000110000110000000011000容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。特别讨论：网（即有权图）的邻接矩阵定义为：A.Edge[i][j]=Wijvi,vj或（vi,vj）∈VR∞无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：邻接矩阵：∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞N.Edge=(v1v2v3v4v5v6)邻接矩阵法优点：邻接矩阵法缺点：顶点表：5748956531∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞3∞∞∞1∞注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数typedefenum{DG,DN,UDG,UDN}GraphKind;//有向图/网，无向图/网typedefstructArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可AdjMatrixarcs;//邻接矩阵intvernum,arcnum;//顶点总数，弧（边）总数GraphKindkind;//图的种类标志}Mgraph;图的邻接矩阵存储表示（参见教材P161）对于n个顶点的图或网，空间效率=O(n2)StatusCreateUDN(Mgraph&G){//无向网的构造，用邻接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);//输入总顶点数，总弧数和信息for(i=0;iG.vexnum,;++i)scanf(&G.vexs[i]);//输入顶点值，存入一维向量中for(i=0;iG.vexnum;++i)//对邻接矩阵n*n个单元初始化，adj=∞,info=NULLfor(j=0;jG.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;kG.arcnum;++k){//给邻接矩阵有关单元赋初值(循环次数＝边数scanf(&v1,&v2,&w);//输入边的两顶点以及对应权值i=LocateVex(G,v1);j=LocateVex(G,v2);//找到两顶点在矩阵中的位置G.arcs[i][j].adj=w;//输入对应权值if(IncInfo)Input(*G.arcs[i][j].info);//如果弧有信息则填入G.arcs[i][j]=G.arcs[j][i]；//无向网是对称矩阵}returnOK;}//CreateUDN例：用邻接矩阵生成无向网的算法（参见教材P162）对于n个顶点e条弧的网，建网时间效率=O