第7章1(7172图的定义及存储结构)

第7章图本章教学目的与要求：掌握图的基本概念、存储方法、基本操作。掌握与图相关的一些算法，如遍历、最短路径、最小生成树等。7.1图的定义和术语图的实例其中用圆圈标示的是数据元素，在图中称为顶点。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图G1图G2图G37.1图的定义和术语顶点之间的连线，表示数据元素之间的关系。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图G1图G2图G32023/2/44图(Graph)——图G是由两个集合V(G)和E(G)组成

的,记为G=(V,E)其中：V(G)是顶点的非空有限集

E(G)是关系的有限集合，关系是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成

V(G)是顶点的非空有限集，E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<vi,vj>，vi,vj是顶点，vi为弧尾，vj为弧头无向图——无向图G是由两个集合V(G)和E(G)组成

V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶

点的无序对，记为（vi,vj）或（vj,vi)，并且（vi,vj)=(vj,vi)

图的概念v1v2v3v4v1v2v3v4v5图G1图G2G1=(V1,{A1})其中，V1={v1,v2,v3.v4}A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}G2=(V2,{E2})其中，V2={v1,v2,v3.v4,v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}7.1图的定义和术语在G1中，连线上有箭头表示方向，则该连线称为弧。我们可以用<v1,v2>表示一条弧，v1称为弧尾，v2称为弧头。相应的，图G1称为有向图。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图G1图G2图G37.1图的定义和术语在G2中，没有箭头的连线称为边。图G2称为无向图。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图G1图G2图G37.1图的定义和术语在G3中，连线上标有与之相关联的数值（称为权），这种形式的图通常称为网。v1v2v3v4v1v2v3v4v5v1v2v4v3v5v616662345图G1图G2图G37.1图的定义和术语有n个顶点，且每两个顶点之间均有边的无向图，称为完全图。完全图共有n*（n-1）/2条边。几个完全图的例子如下：v1v2v3v4v1v1v2v1v2v37.1图的定义和术语有n个顶点，且每两个顶点之间均有边的有向图，称为有向完全图。有向完全图共有n*（n-1）条边。几个有向完全图的例子如下：v1v2v3v4v1v1v2v1v2v3子图——如果图G(V,E)和图G’(V’,E’),满足：V’V，E’E

则称G’为G的子图24513635621v1v3v4v2v1v3v2v3v47.1图的定义和术语7.1图的定义和术语在无向图中，若(v,w)是一条边，(v,w)∈E则v,w互为邻接点uvw7.1图的定义和术语在无向图中，顶点v的度是指与v相连的边的条数。uvw7.1图的定义和术语在有向图中，顶点v的出度是指v作为弧尾的弧的条数。记为OD(v)uvw7.1图的定义和术语在有向图中，顶点v的入度是指v作为弧头的弧的条数。记为ID(v)uvw7.1图的定义和术语在有向图中，顶点v的度是指v的入度和出度之和。记为TD(v)TD(v)=ID(v)+OD(v)uvw7.1图的定义和术语顶点v到顶点w的路径指从v出发沿着边或者弧到达w所经过的顶点序列。如上图中v-v2-w是从v到w的一条路经路径上边或者弧的数目称为路径的长度。序列中顶点不重复的路径称为简单路径vv2v3v4w7.1图的定义和术语第一个顶点和最后一个顶点相同的路径称为回路或者环。路径v-v2-v3-v4-v就是一条回路除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或者简单环vv2v3v4w7.1图的定义和术语在无向图中，如果从v到w之间有路径，则称顶点v和顶点w是连通的。如果图中任意两个顶点都是连通的，则称该图为连通图。vv2v3v4w连通图7.1图的定义和术语上图看作一个整体，不是连通图。v1v2v3v4v5v6v77.1图的定义和术语无向图中的一个极大连通子图，称为该图的连通分量。v1v2v3v4v5v6v3v6v1v2v4v52个连通分量G0上图G0不是连通图，有两个连通分量.强连通图——有向图中，如果对每一对Vi,VjV,ViVj,从Vi到Vj

和从Vj到Vi都存在路径，则称G是强连通图强连通图356245136非强连通图7.1图的定义和术语v1v2v3v4v5v1v2v3v47.1图的定义和术语上图G1不是强连通图，有两个强连通分量：G1-1和G1-2v1v2v3v4图G1v1v3v4图G1-1v2图G1-2有向图中的极大强连通子图称为有向图的强连通分量。7.1图的定义和术语连通图的生成树是一个极小连通子图。生成树中包含图的全部顶点（假定为n个），包含能够连接起n个顶点的n-1条边，使得生成树也是一个连通图。如上面图G2-1为图G2的一棵生成树。v1v2v3v4v5图G2v1v2v3v4v5图G2-12023/2/425一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。一棵有n个顶点的生成树有且仅有n-1条边。15732461573246连通图生成树26抽象数据类型---图ADTGraph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={<v,w>|v,wV且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作P：

GraphCreat(G,，V，VR)；//创建图

GraphDestory(G)；//销毁图

GraphLocateVertex(G，v)；//寻找顶点v

GraphGetVertex(G，v)；//返回顶点v的值

GraphPutVertex(&G，v,value)；//为顶点v赋值

GraphFirstAdjVex(G，v)；//返回v的第一个邻接顶点

GraphNextAdjVex(G，v，w)；//返回v的下一个邻接顶点

GraphInsertVertex(G，v)；//在图中添加新顶点v

GraphDeleteVertex(G，v)；//删除顶点v及相关的弧

GraphInsertArc(G，v，w)；//在图中增加弧<v,w>

GraphDeleteArc(G，v，w)；//删除图中v和w之间的弧

DFSTtraverse(G，v，Visit())；//深度优先遍历

BFSTtraverse(G，v，Visit())；//广度优先遍历

}ADTGraph

7.2图的存储结构

由于图的顶点之间存在多对多的关系，因此，图的存储结构相应的比较复杂。本节我们介绍两种最常用的存储结构，邻接矩阵表示法(数组表示法)和邻接表表示法。十字链表表示法邻接多重表表示法7.2.1邻接矩阵表示法（数组表示法）用一个一维数组存储顶点的信息。用一个二维数组存储数据元素之间关系(边或弧)的信息，这种表示方法我们称之为邻接矩阵法。7.2.1邻接矩阵表示法（数组表示法）一、举例说明邻接矩阵表示法1.有向图v1v2v3v4图G1v1v2v3v4边信息数组arcsv1v2v3v4v1v2v3v4顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）v1v2v3v4图G1v1v2v3v4边信息数组arcsv1v2v3v4v10110v20000v30001v41000顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）v1v2v3v4图G1v1v2v3v4边信息数组arcsv1v2v3v4v10110v20000v30001v41000思考：（1）如何从arcs寻找v1的出度、入度，邻接点；（2）是否能从arcs判断该图是否有向图。顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）边信息数组arcsv1v2v3v4v10110v20000v30001v41000解答：（1）如何从arcs寻找v1的出度、入度，邻接点；V1行所有1的个数为v1的出度；V1列所有1的个数为v1的入度；V1行所有1对应的下标在vexs中对应的顶点。（2）能否从arcs判断该图的类型，（有向图还是无向图）。当arcs数组关于主对角线不对称时，可以肯定其是有向图。否则不能判定。7.2.1邻接矩阵表示法（数组表示法）2.无向图v1v2v3v4v5边信息数组arcsv1v2v3v4v5v1v2v3v4v5顶点信息数组vexsv1v2v3v4v5图G27.2.1邻接矩阵表示法（数组表示法）v1v2v3v4v5边信息数组arcsv1v2v3v4v5v101010v210101v301011v41010001100v5顶点信息数组vexsv1v2v3v4v5图G27.2.1邻接矩阵表示法（数组表示法）思考：（1）如何从arcs寻找v1的度，邻接点；（2）是否能从arcs判断该图是否有向图。v1v2v3v4v5边信息数组arcsv1v2v3v4v5v101010v210101v301011v41010001100v5顶点信息数组vexsv1v2v3v4v5图G27.2.1邻接矩阵表示法（数组表示法）解答：（1）如何从arcs寻找v1的度，邻接点；V1行所有1的个数为v1的度；V1行所有1对应的下标在vexs中对应的顶点。（2）能否从arcs判断该图的类型，（有向图还是无向图）。当arcs数组关于主对角线不对称时，可以肯定其是有向图。否则不能判定。边信息数组arcsv1v2v3v4v5v101010v210101v301011v41010001100v57.2.1邻接矩阵表示法（数组表示法）3.网v1v2v3v4v5v61555346798v1v2v3v4v5v6顶点信息数组vexs7.2.1邻接矩阵表示法（数组表示法）v1v2v3v4v5v61555346798边信息数组arcsv1v2v3v4v5v6v157v24v389v4565v5v631二、用c语言描述图的存储结构及其操作1.存储结构为了简单起见，我们假设顶点所代表数据的数据类型是字符串，如“v1”、“v2”等；考虑到顶点之间的边上可能带有权值，则邻接矩阵的类型设为double。当然大家可以根据应用问题的不同，适当调整数据类型。structMGraph{ char*vexs[100];//存储顶点信息

doublearcs[100][100];//存储边的信息

intvexnum,arcnum;//顶点数目和边的数目};二、用c语言描述图的存储结构及其操作2.基本操作图的基本操作包括图的初始化、查找顶点是否存在、查找边是否存在、插入一个顶点，插入一条边，删除一个顶点，删除一条边，求顶点的邻接点等。voidInitGraph(MGraph&mg){//图的初始化

mg.arcnum=mg.vexnum=0;//顶点和边的数目均为0 for(inti=1;i<100;i++) for(intj=1;j<100;j++) mg.arcs[i][j]=0;//各个顶点之间初始情况下没有边相连}二、用c语言描述图的存储结构及其操作2.基本操作intFindVex(MGraphmg,char*vex){//查找顶点vex是否存在

for(inti=1;i<=mg.vexnum;i++){ if(strcmp(mg.vexs[i],vex)==0) returni;//顶点存在，返回i } return0;//顶点不存在，返回0}二、用c语言描述图的存储结构及其操作2.基本操作intFindArc(MGraphmg,char*v1,char*v2){//查找边或弧<v1,v2>是否存在

intx,y; x=FindVex(mg,v1); y=FindVex(mg,v2); if(x==0||y==0)return0;//某个顶点不存在,边肯定不存在，返回0 if(mg.arcs[x][y]==1)return1;//边存在，返回1}二、用c语言描述图的存储结构及其操作2.基本操作voidInsertVex(MGraph&mg,char*vex){//插入一个顶点vex

if(FindVex(mg,vex)==0)//顶点不存在

{ mg.vexnum++;

mg.vexs[mg.vexnum]=newchar[strlen(vex)]; strcpy(mg.vexs[mg.vexnum],vex);//新顶点加入

}}二、用c语言描述图的存储结构及其操作2.基本操作voidInsertArc(MGraph&mg,char*v1,char*v2){//插入一条边或弧<v1,v2> intx,y; x=FindVex(mg,v1); y=FindVex(mg,v2);

if(x&&y){mg.arcs[x][y]=1; mg.arcnum++; }}二、用c语言描述图的存储结构及其操作2.基本操作intFirstAdjVex(MGraphmg,intv){//在图mg中，求顶点v的第一个邻接点 //使用顶点的下标代替字符串，

//如顶点“v1“对应下标为v,则使用v代表“v1“

for(inti=1;i<=mg.vexnum;i++){if(mg.arcs[v][i]!=0) returni; } return0;//不存在邻接点时，返回0}二、用c语言描述图的存储结构及其操作2.基本操作intNextAdjVex(MGraphmg,intv,intw){//在图mg中，求顶点v的相对于顶点w的下一个邻接点

for(inti=w+1;i<=mg.vexnum;i++) if(mg.arcs[v][i]!=0) returni; return0;}二、用c语言描述图的存储结构及其操作2.基本操作对于左图，可以用右面代码来构造v1v2v3v4图G1intmain(intargc,char*argv[]){MGraphmg;InitGraph(mg);//图的初始化

InsertVex(mg,"v1");//插入顶点

InsertVex(mg,"v2"); InsertVex(mg,"v3"); InsertVex(mg,"v4"); InsertArc(mg,"v1","v2");//插入边

InsertArc(mg,"v1","v3"); InsertArc(mg,"v3","v4"); InsertArc(mg,"v4","v1");return0;}7.2.2邻接表表示法一、举例说明邻接表表示法1.有向图v1v2v3v4图G11v12v2^3v34v42^3^4^1^思考：根据右图1.如何求v1的出度、入度、以v1为弧尾的邻接点？2.如何求图中共有几条边？7.2.2邻接表表示法一、举例说明邻接表表示法1.有向图1v12v2^3v34v42^3^4^1^思考：1.如何求v1的出度、入度、以v1为弧尾的邻接点？解答：v1的出度是v1后面链表的长度。

V1的入度为所有链表中数据域为1的结点的个数。V1的邻接点就是v1后链表上的所有结点。2.如何求图中共有几条边？所有链表中所有结点的个数。7.2.2邻接表表示法一、举例说明邻接表表示法2.无向图1v12v23v34v45v524^41v1v2v3v4v5图G2135^25^3^23^思考：根据右图1.如何求v1的度、v1的邻接点？2.如何求图中共有几条边？7.2.2邻接表表示法一、用c语言描述图的邻接表存储结构及其操作1.存储结构从上面的例子可以看出，邻接表中存在两种结点，一种是链表的头结点，用来存储顶点信息；一种是表结点，用来存放邻接点以及边的信息。1v12v23v34v45v524^41135^25^3^23^7.2.2邻接表表示法一、用c语言描述图的邻接表存储结构及其操作1v12v23v34v45v524^41135^25^3^23^datafirstarc表头结点：顶点信息指向第1个邻接点的指针表结点adjvexinfonextarc邻接点边或弧的信息（如权值）指向下一条边或弧的结点7.2.2邻接表表示法一、用c语言描述图的邻接表存储结构及其操作//表结点-结构体类型structArcNode{ intadjvex;//邻接点

doubleweight;//边的信息(权)

ArcNode*nextarc;//指向下一条边的指针};7.2.2邻接表表示法一、用c语言描述图的邻接表存储结构及其操作//头结点-结构体类型typedefstructVexNode{ chardata[5];//顶点信息（字符串）

ArcNode*firstarc;//指向第一条边的指针}VexNode;//图-结构体类型typedefstruct{ VexNodevexs[100];//顶点的集合

intvexnum,arcnum;//顶点的数目，边的数目}ALGraph;7.2.2邻接表表示法一、用c语言描述图的邻接表存储结构及其操作

图的基本操作包括图的初始化、查找顶点是否存在、查找边是否存在、插入一个顶点，插入一条边，删除一个顶点，删除一条边，求顶点的邻接点等。

voidInitGraph(ALGraph&mg){//图的初始化

mg.arcnum=mg.vexnum=0; for(inti=1;i<100;i++) { strcpy(mg.vexs[i].data,""); mg.vexs[i].firstarc=0; }}intFindVex(ALGraphmg,char*vex){//查找顶点vex是否存在

for(inti=1;i<=mg.vexnum;i++) if(strcmp(mg.vexs[i].data,vex)==0) returni; return0;//不存在}intFindArc(ALGraphmg,char*v,char*w){//查找边或弧<v,w>是否存在

intv1=FindVex(mg,v); intw1=FindVex(mg,w); if(v1*w1==0)return0;//不存在

ArcNode*p=mg.vexs[v1].firstarc;//表结点p

while(p) { if(p->adjvex==w1)return1;//找到了

p=p->nextarc;//指向下一条边(下一个邻接点) } return0;//不存在 }voidInsertVex(ALGraph&mg,char*vex){//插入一个顶点vex intv=FindVex(mg,vex);

if(v!=0)return;//该顶点已经存在

mg.vexnum++; strcpy(mg.vexs[mg.vexnum].data,vex);return; }voidInsertArc(ALGraph&mg,char*v1,char*v2){//插入一条边或弧<v1,v2>

if(FindArc(mg,v1,v2)==0)//边不存在

{//此时我们假定顶点已经存在

ArcNode*p=newArcNode;//定义表结点

//生成一个新的结点p->adjvex=FindVex(mg,v2); p->nextarc=0; p->weight=0;

intv=FindVex(mg,v1);

//新结点作为链表第一个结点

p->nextarc=mg.vexs[v].firstarc; mg.vexs[v].firstarc=p; }}intFirstAdjVex(ALGraphmg,intv){//在图mg中，求顶点v的第一个邻接点

//使用顶点的下标代替字符串，如顶点“v1”对应下标为v,//则使用v代表“v1”,假定v存在

if(mg.vexs[v].firstarc!=0) returnmg.vexs[v].firstarc->adjvex; elsereturn0; }intNextAdjVex(ALGraphmg,intv,intw