数据结构第讲图的定义与存储结构

数据结构第讲图的定义与存储结构第1页，课件共45页，创作于2023年2月课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11第2页，课件共45页，创作于2023年2月第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第3页，课件共45页，创作于2023年2月7.1图的定义和术语1.基本术语(1)顶点图中的数据元素通常称为顶点。V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。(2)有向图若称<v,w>∈VR表示从v到w的一条弧，且称v为弧尾或初始点，称w为弧头或终端结点，则该图称为有向图。第4页，课件共45页，创作于2023年2月(3)无向图若<v,w>∈VR，必有<w,v>∈VR，即VR是对称的，则以无序对（v,w)代替这两个有序对，表示v和w之间的一条边，则该图称为无向图。第5页，课件共45页，创作于2023年2月(4)权/网有时图的边或弧具有与它相关的数，这些数称为权值（通常表示顶点间的距离或耗费），则带权值的图称为网。(5)子图假设有两个图G=（V，{VR}）和G’=（V’，{VR’}），若V’

是V的子集，且VR’

是VR的子集，则称G’

为G的子图。第6页，课件共45页，创作于2023年2月G1的子图G2的子图第7页，课件共45页，创作于2023年2月(6)完全图假设用n表示图中顶点的数目，用e表示边或弧的数目。忽略自身弧/边，即若﹤vi,vj﹥∈VR，则vi≠vj。对于无向图，有(n(n-1))/2条边的无向图称为完全图。对于有向图，有n(n-1)条弧的有向图称为有向完全图。(7)稀疏图/稠密图边或弧很少（如e＜nlogn）的图称稀疏图，反之称稠密图。第8页，课件共45页，创作于2023年2月(8)邻接点对于无向图G=(V,{E})，若边(v,v’)∈E，则称顶点v和v’互为邻接点，即v和v’相邻接。或称边（v,v’）依附于顶点v和v’，或称（v,v’）和顶点v和v’

相关联。对于有向图G=(V，{E})，若弧<v，v’>∈E，则称顶点v邻接到顶点v’，或称顶点v’邻接自顶点v，或弧<v，v’>和顶点v，v’

相关联。(a)(b)第9页，课件共45页，创作于2023年2月顶点的入度/出度以顶点v为头的弧的数目称v的入度，记为ID(v)；以顶点v为尾的弧的数目称v的出度，记为OD(v)。顶点v的度TD（v）=ID（v）＋OD（v）(9)顶点v的度(Degree)是和v相关联的边的数目，记为TD（v）。(a)(b)第10页，课件共45页，创作于2023年2月(10)路径(Path)无向图G=(V,{E})中，从顶点v到v’的路径是顶点序列(v=vi0,vi1,…,vim=v’)，其中(vij-1,vij)∈E，1≤j≤m。若G是有向图，则路径也是有向的，顶点序列应满足：<vij-1,vij>∈E，1≤j≤m。路径的长度是路径上的边或弧的数目。第11页，课件共45页，创作于2023年2月(11)回路/环/简单路径第一个顶点和最后一个顶点相同的路径称为回路/环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。第12页，课件共45页，创作于2023年2月(12)连通图/连通分量在无向图G中，如果从顶点V到顶点V’

有路径，则称V和V’

是连通的。若图中任意两个顶点vi、vj∈V，vi和vj都是连通的，则称G是连通图。无向图中的极大连通子图称之为连通分量。第13页，课件共45页，创作于2023年2月左图：连通图下图：非连通图，但有三个连通分量第14页，课件共45页，创作于2023年2月(13)强连通图/强连通分量在有向图G中，若对于每一对vi、vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。第15页，课件共45页，创作于2023年2月非强连通图

④

①

②

③

④①②③两个强连通分量第16页，课件共45页，创作于2023年2月一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。(14)生成树第17页，课件共45页，创作于2023年2月如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。(15)生成森林第18页，课件共45页，创作于2023年2月2.图的抽象类型定义ADTGraph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}VR={<v,w>|v,w∈V且P(v,w)，<v,w>

表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}

基本操作P：}ADTGraph第19页，课件共45页，创作于2023年2月基本操作CreateGraph(&G,V,VR);//按V和VR的定义构造图GDestroyGraph(&G);//销毁图GLocateVex(G,u);//若G中存在顶点u，则返回该顶点//在图中位置；否则返回其它信息GetVex(G,v);//返回v的值PutVex(&G,v,value);//对v赋值valueFirstAdjVex(G,v);//返回v的第一个邻接点。//若v在G中没有邻接点，则返回“空”第20页，课件共45页，创作于2023年2月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>第21页，课件共45页，创作于2023年2月DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每个顶点调用//函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每个顶点调用//函数Visit一次且仅一次。第22页，课件共45页，创作于2023年2月第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第23页，课件共45页，创作于2023年2月7.2图的存储结构图的数组(邻接矩阵)存储表示图的邻接表存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示第24页，课件共45页，创作于2023年2月1.图的数组(邻接矩阵)存储表示邻接矩阵是用于描述图中顶点之间关系(即弧或边的权)的矩阵。假设图中顶点数为n，则邻接矩阵An×n：1若Vi和Vj之间有弧或边A[i][j]=0反之第25页，课件共45页，创作于2023年2月

CADB

CABDCBAA=0111101111011110A

B

C

DA

B

C

CBAB=010100110第26页，课件共45页，创作于2023年2月注意：1)图中无邻接到自身的弧，因此邻接矩阵主对角线为全零。2)无向图的邻接矩阵必然是对称矩阵。3)无向图中，顶点的度是邻接矩阵对应行（或列）的非零元素之和；有向图中，对应行的非零元素之和是该顶点的出度；对应列的非零元素之和是该顶点的入度；则该顶点的度是对应行和对应列的非零元素之和。第27页，课件共45页，创作于2023年2月V1V2V3V4V5V65485931567网的邻接矩阵

∞反之权值若Vi和Vj之间有弧或边A[i][j]=第28页，课件共45页，创作于2023年2月图的数组（邻接矩阵）存储表示#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//图类型（有向图/网,无向图/网）typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0

表示相邻否；对带权图，则为权值类型。InfoType*info;//指向该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//描述顶点的数组AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧(边)数GraphKindkind;//图的种类标志}MGraph;第29页，课件共45页，创作于2023年2月构造图的算法StatusCreateGraph(Mgraph&G){//采用数组(邻接矩阵)表示法，构造图G。

scanf(&G.kind)；

switch(G.kind){

caseDG：returnCreateDG(G)；//构造有向图G

caseDN：returnCreateDN(G)；//构造有向网G

caseUDG：returnCreateUDG(G)；//构造无向图G

caseUDN：returnCreateUDN(G)；//构造无向网G

default：returnERROR；

}}//CreateGraph第30页，课件共45页，创作于2023年2月采用数组表示法，构造无向网GStatusCreateUDN(MGraph&G){

sacnf(&G.vexnum,&G.arcnum,&IncInfo);

for(i=0;i<G.vexnum;++i)scanf(&G.vexs[i]);//构造顶点向量

for(i=0；i<G.vexnum；++i)

//初始化邻接矩阵

for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info}

for(k=0；k<G.arcnum；++k){

//构造邻接矩阵

scanf(&v1，&v2，&w)；//输入一条边依附的顶点及权值

i=LocateVex(G,v1);j=LocateVex(G,v2);//v1和v2在G中位置

G.arcs[i][j].adj=w；//弧<v1，v2>的权值

if(IncInfo)Input(*G.arcs[i][j].info);G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的对称弧<v2,v1>}returnOK;}//CreateUDN第31页，课件共45页，创作于2023年2月2.图的邻接表存储表示类似树的孩子链表。即对图中的每个顶点vi建立一个单链表，表中结点表示依附于该顶点vi的边或弧。邻接点域链域数据域指示与顶点vi邻接的点在图中的位置指示下一条边或弧的结点存储和边或弧相关的信息数据域链域指向链表第一个结点存储顶点vi和其他有关信息表结点表头结点第32页，课件共45页，创作于2023年2月V1V3V2V4V1V3V2V4例如：∧1∧3∧4

4

3

2

1∧4

4

3

2

121∧113∧4∧4∧2第33页，课件共45页，创作于2023年2月注意：在无向图的邻接表中，1）第i个链表中结点数目为顶点i的度；2）所有链表中结点数目的一半为图中边数；3）占用的存储单元数目为n+2e。在有向图的邻接表中，1）第i个链表中结点数目为顶点i的出度；2）所有链表中结点数目为图中弧数；3）占用的存储单元数目为n+e。第34页，课件共45页，创作于2023年2月为求出每一个顶点的入度，必须另外建立有向图的逆邻接表。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。2∧4

4

3

2

1∧1

∧

逆邻接表∧3V1V3V2V4第35页，课件共45页，创作于2023年2月图的邻接表存储表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图的种类标志}ALGraph;第36页，课件共45页，创作于2023年2月3.有向图的十字链表存储表示十字链表是有向图的另一种链式存储结构。可以理解成有向图的邻接表和逆邻接表的结合，在十字链表中，有两种结点结构：尾域tailvex头域headvex链域hlink链域tlink信息域info数据域data链域firstin链域firstout顶点结点弧结点第37页，课件共45页，创作于2023年2月尾域tv指示弧尾顶点在图中的位置头域hv指示弧头顶点在图中的位置链域h指向弧头相同的下一条弧链域t指向弧尾相同的下一条弧信息域指向该弧的相关信息尾域tailvex头域headvex链域hlink链域tlink信息域info数据域data链域firstin链域firstout数据域存储和顶点相关信息链域fin指向以该顶点为弧头的第一个弧结点链域fout指向以该顶点为弧尾的第一个弧结点第38页，课件共45页，创作于2023年2月v1v2v3v4

012310/\20v3v1v4v2/\03/\13/\/\2302/\/\32例：datafirstinfirstouttailvexheadvexhlinktlink/\第39页，课件共45页，创作于2023年2月有向图的十字链表存储表示#defineMAX_VERTEX_NUM20typedefstructArcBox{inttailvex,headvex;//该弧的尾和头顶点的位置structArcBox*hlink,*tlink;//分别指向下一个弧头相同

和弧尾相同的弧的指针域InfoType*info;//该弧相关信息的指针}ArcBox;typedefstructVexNode{VertexTypedata;

ArcBox*firstin,*firstout;//分别指向该顶点第一条入弧和出弧}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表头向量intvexnum,arcnum;//有向图的当前顶点数和弧数}OLGraph;第40页，课件共45页，创作于2023年2月4.无向图的邻接多重表存储表示在无向图的邻接表中，每条边（Vi，Vj）由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表较方便。

邻接多重表中结点分为：