数据结构--图-期末考试复习

第十二章图

12.1图的定义

(1)图是由一个顶点集和连接各顶点的边集组成。它可以用二元组G=(V,E)表示，其中

V表示顶点集，E表示边集。

(2)如果边有方向，则称有向图，＜u,v＞表示从u出发到v的一条边；与之对应的是无

向图，(u,v)

(3)有时边还有第三个属性，称为边的代价或权值，用来表示经过这条边所花费的代

价，这样的图称为加权图(有向加权图、无向加权图)加权图中的每条边由3个分量表

示：两个顶点和权值

(4)稀疏图：|E|远远小于|V?|

理想下的边数|E|=|V2|-|V|,例如右图:|E|=32=3=6

12.2图的基本术语

⑴邻接

如(Vi,Vj)是无向图中的一条边，则称Vi和Vj邻接

(2)度

在无向图中，结点的度是与该结点关联的边数；在有向图中，度分为出度和入度。

(3)子图

假设G=(V,E)和GJ(V',E如果V'包含于V,E'包含于E,,则称G'是G的子图。

(4)路径和路径长度

路径是指图中由边连接而成的结点序列。

非加权的路径长度就是指组成路径的边数，为N-l(N为结点个数)

加权的路径长度就是指路径上所有边的权值之和。

(5)连通图和连通分量

如果一个无向图G的任意两个结点之间都是连通的（即有路径），则称G是连通图；每

一个非连通图都可以分成几个极大的连通的部分，每一个极大的连通子图称为一个连通

分量。

0------------------©

©----©

（6）强连通图和强连通分量

如果有向图G的任意两个结点之间都是连通的，则称G是强连通图。

对于非强连通图，会有强连通分量。

（7）完全图

每两个结点之间都有边的无向图称为无向完全图；每两个结点之间都有两条弧的有向图

称为有向完全图。

（8）生成树

生成树是国同连通图的极小连通子图，n-l条边使得n个结点互相连通，在生成树中添

加一条边，必定会形成回路或环。

12.3图的基本运算

构成图；判断两条边之间是否有边的存在exist；在图中添加或删除一条边insert/remove；

返回图中的结点数或边数；遍历图中所有结点。

12.4图的存储

12.4.1邻接矩阵表示法

（1）若顶点i、j之间存在一条自i到j的有向边或无向边，那么A[i]0]=l,否则A「Hj]=O

或者无穷大。

01010

11010

01010

11010

01010

11010

(2)对于无向图，邻接矩阵第i行或第i列的元素之和是第i个结点的度；

对于有向图，邻接矩阵的第i行元素之和是出度，第j列元素之和是入度。

(3)图的邻接矩阵存储需要两个部分：一个是存储结点值的数组；一个是存储边的邻

接矩阵。

12-2基于邻接矩阵的图类定义

template<classTypeOfVer,classTypeOfEdge>

classadjMatrixGraph:publicgraph<TypeOfEdge>{〃7意味着“继承自”，邻接矩阵继承自

图的抽象类

public:〃公有成员函数

adjMatrixGraph(intvSize,constTypeOfVerd[],constTypeOfEdgenoEdgeFlag);

〃构造函数，三个参数，vSize顶点个数，顶点值数组，结点间不存在边的标志

boolinsert(intujntv,TypeOfEdgew);〃插入一条边

boolremove(intu,intv);〃删除条边

boolexist(intu,intv)const;〃彳j尔类型，fepoL非真即假，返回常数，是否存

在边

~adjMatrixGraph();〃析构函数

private:〃私有成员变址

TypeOfEdge**edge;〃存放邻接处:阵,二维数组

TypeOfVer*ver;〃仃

TypeOfEdgenoedge;〃结点间不存在边的标志

12-3adjMatrixGraph类的构造函数

template<classTypeOfVer,classTypeOfEdge>

adjMatrixGraph<TypeOfVer,TypeOfEdge>：：adjMatrixGraph(intvSize,constTypeOfVerd[],

constTypeOfEdgenoEdgeFlag)〃构造函数有3个参数：结点数、结点值和邻接矩阵中表

示结点间无边的标记，构造函数根据这3个参数构造•个只有结点没有边的图

{inti,j;

Vers=vSize;//设置存储结点数

Edges=0;〃边数

noEdge=noEdgeFlag;〃无边标记

ver=newTypeOfVer[vSize];〃申请一个存储结点的一维数组ver,

for(i=0;i<vSize;++i)ver[i]=d[i];//for循环把参数中给出的结点值保存在数组ver中

edge=newTypeOfEdge*[vSize];

〃邻接矩阵egde是一个vSize*vSize的矩阵，而二维数组可以看成一个指向一维数组的

指针数组，所以此行为申请一个指向一维数组的指针数组edge

for(i=0;i<vSize;++i){〃对邻接矩阵111的每一行进行初始化

edge[i]=newTypeOfEdge[vSize];〃为邻接矩阵的这•行申请空间

for(j=0;j<vSize;++j)edge[i][j]=noEdge;〃将每个元素都设成“没有边”

edge「Hi]=O；〃把自己到自己的边的权值设为0

)

)

12-4adjMatrixGraph类的析构函数

template<classTypeOfVer,classTypeOfEdge>

adjMatrixGraph<TypeOfVer,TypeOfEdge>::~adjMatrixGraph()

(

delete[]ver;〃释放了存放站点俏.的•维数组的空间

for(inti=O;i<Vers;++i)delete[]edge。];〃循环释放保存邻接矩阵的空间,edge是邻接

矩阵，for的每个循环周期释放了邻接矩阵的一行

delete1]edge;//#^了指向邻接矩阵每一行首地址的指针―

)

12-5adjMatrixGraph类其它成员函数的实现

template<classTypeOfVer,classTypeOfEdge>

booladjMatrixGraph<TypeOfVer,TypeOfEdge>::|insert|(intu,intv,TypeOfEdgew)

〃插入函数，参数是边，起点为u,终点为v,权重为w

{if(u<O||u>Vers-l||v<O||v>Vers-l)returnflase;〃检查作为参数输入的边是否合法

if(edge[u][v]!=noEdge)returnfalse;〃检查被捅入的边是否存隹，如果存在,返回false

edge[u][v]=w;〃若不存在，则在邻接矩阵中添加相应的边

++Edge;〃边数+1

returntrue;〃返叵Itrue我示插入成功

)

template<classTypeOfVer,classTypeOfEdge>

booladjMatrixGraph<TypeOfVer,TypeOfEdge>::|remove|(intu,intv)

{if(u<0||u>Vers・l||v<0]|v>Vers-1)returnflase;〃检彳f作为参数输入的边是否合法

if(edge[u][v]==noEdge)returnfalse;〃检查所删除的边是否存在,如果不存在,返回

false

edge[u][v]=noEdge;〃如果存在,则将对应的数组无戈noEdge

-Edge;〃边数；

returntrue;//i£PItrue表示删除成功

)

template<classTypeOfVer,classTypeOfEdge>

booladjMatrixGraph<TypeOfVer,TypeOfEdge>::|exist|(intujntv)const

{if(u<0||u>Vers-l||v<0||v>Vers-l)returnflase;〃检查作为参数输入的边是否合法

if(edge[u][v]==noEdge)returnfalse;〃判断边是否存在，不存在返1nlfalse

elsereturntrue;〃存隹返回true

}

12.4.2邻接表表示法

(1)基本定义

将每个结点的邻接结点组成一个链表，链表的每个结点代表一条边。

左边图只是右边的部分表示

（2）保存方法

在邻接表表示法中，保存一个图同样分为两部分：保存顶点和保存边。

顶点集|用一个数组表示,数组中每个元素由两部分组成：顶点值和指向该顶点对应的链

表的首地址,即:data和link两部分。

睡由一组单链表表示。①非加权图②加权图

终止结点的编号后继指针

datalink

权值终止结点的编号后继指针

costdatalink

（3）有向图和无向图保存方法比较之处

①有向图

每条边都作为一个单链表的结点出现，所以所有顶点对应的单链表的结点总数=图的边

数

②无向图

每条边在邻接表中将出现两次，例如（x,y）,在x的单链表中有一个以y为终点的结点，

在y的单链表中有一个以x为终点的结点，所以所有顶点对应的单链表的结点总数=图

边数的两倍。

12-6邻接表类的定义

template<classTypeOfVers,classTypeOfEdge>

classadjListGraph:publicgraph<TypeOfEdge>{

public:

adjListGraph(intvSize,constTypeOfVerd[]);〃构造函数

boolinsert(intujntvJypeOfEdgew);〃插入边

boolremove(intujntv);〃删除边

boolexist(intujntv)const;〃是否存在

~adjListGraph。;〃析构函数

private:

structedgeNode{〃为了保存边的信息，定义一个单.链表中的结点类型edgeNode

intend;〃终止结点的编号

TypeOfEdgeweight;〃权重

edgeNode*next;〃后继指针

edgeNode(inte,TypeOfEdgew,edgeNode*n=NULL)

{end=e;weight=w;next=n;}

)；

structverNode{〃为了保存顶点的*定义了一个保存顶点的数组中的结点类型

verNode

TypeOfVerver;

edgeNode*head;〃顶点的首地址

verNode(edgeNode*n=NULL)〃后继指针

{head=h;}

)；

verNode*verList;//保存顶点数组的首地址

）；

verListedaeNode

12-7adjListGraph类的构造函数和析构函数

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::adjListGraphfintvSize,constTypeOfVerd[])

{Vers=vSize;Edges=O;〃根据参数表中给出的顶点个数中请•个存储顶点的数组，并设得

个顶点对应的单链表为空

verList=newverNode[vSize];〃把数组首地址赋给verList

for(inti=O;i<Vers;++i)verList[i].ver=d「];〃将参数表中给出的顶点值存入该数组

}

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::~adjListGraph|()

{inti;

edgeNode*p;〃临时指针

for(i=0;i<Vers;++i)//♦次循环删除•条单链表，即•个顶点的所有边

while((p=verList[i].head)!=NULL){(l)

verList[i].head=p->next;(2)

deletep;③〃三步删除一条单.链表中的一个结点

}

delete[]verList;〃释放存储顶点的数组的空间

}

verListedaeNode

12-8insert函数的实现

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::insert(intu,intv,TypeOfEdgew)

{verList[u].head=newedgeNode(v,w,verList[u].head);〃为新插入的边申请-~个单链表'I1的

结点，然后将新插入的边对应的结点插入到单链表的表头

++Edges;〃边数+工

returntrue;

}

12-9remove函数的实现

template<classTypeOfVers,classTypeOfEdge>

adjListGraph<TypeOfVers,TypeOfEdge>::|remove|(intu,intv)

{edgeNode*p=verList[u].head,*q;

verListedaeNode

if(p==NULL)returnfalse;

if(p->end==v)〃7；第一个结,就是要删除的结点

{verList[u].head=p->next;

deletep;--Edges;

returntrue;

)

4

whil