数据结构与算法课件

数据结构（数据结构及其算法）

冯耀霖数据结构（数据结构及其算法）冯耀霖1

Chap7

图

图的基本概念

图的实现

图的遍历

最短路径问题

最小生成树Chap7图图的基本概念2§1图的基本概念

▲图的定义▲图的相关术语▲图的基本操作§1图的基本概念▲图的定义3图（graph）是一种复杂的数据结构，它能够为解决许多具体问题提供非常理想的非数值数学模型。当今，图结构已广泛应用于计算机科学、系统工程、管理工程、通信与网络理论、自动控制、运筹学以至社会科学等诸多学科。图形结构所研究的图并非生活中所说的图画或地图，而是用一些点和线来表示事物之间关系的某种抽象模型，本质上是数据集合与其上关系的图形表示。图（graph）是一种复杂的数据结构，它能够为解决许多41.1图的定义

图G由两个非空集合V和E组成。V是顶点（Vertex）的有限集，在图中数据元素称为顶点或结点。E是边（Edge）的有限集，边是顶点的无序对或有序对，描述了顶点之间的逻辑关系，每一条边连接V中两个不同的顶点。图的形式化定义为G=(V,E)V={vi|vi∈ElemType}

E={(vi,vj)|vi,vj∈V}或E={<vi,vj>|vi,vj∈V}其中，(vi,vj)为无序对，表示一条无向边，简称边；

<vi,vj>为有序对，表示一条有向边，简称弧。1.1图的定义图G由两个非空集合V和E组成。V是顶51.2图的相关术语

1.

无向图在一个图中，如果连接任意2个顶点的是一条无向边(vi,vj)，即顶点之间的连线是无方向的，则称该图为无向图。如图7.1。

G1=(V1,E1)

V1={A,B,C,D,E}

E1={(A,B),(A,D),(B,C),(B,E),(C,D),(C,E)}1.2图的相关术语1.无向图6ABCDEABCD图7.1无向图G1图7.2有向图G2ABCDEABCD图7.1无向图G1图7.2有向图G72.有向图在一个图中，如果连接任意2个顶点的是一条弧<vi

,vj>，即顶点之间的连线是有方向的，则称该图为有向图。对于弧<vi,vj>，vi被称为起点（弧尾），vj被称为终点（弧头）。如图7.2。

G1=(V1,E1)

V1={A,B,C,D}

E1={<A,B>,<A,C>,<C,D>,<D,A>,<D,C>}

3.

混合图混合图是既含有边又含有弧的图。2.有向图8

4.

无向完全图在一个无向图中，如果任意2个顶点之间都有一条边连接，则称该图为无向完全图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

5.

有向完全图在一个有向图中，如果任意2个顶点之间都有方向互为相反的2条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条弧。4.无向完全图9

6.

顶点的度顶点的度是指依附于某顶点v的边数，记作deg(v)。在有向图中，顶点的度有入度和出度之分。对于任意顶点v，以v为起点的弧的数目称为v的出度，记为OD(v)；而以v为终点的弧的数目称为v的入度，记为ID(v)。各个顶点的度都相等的无向图也称为正则图，并记作k-正则图，其中k是各顶点的度。图7.3是个3-正则图，也被称为“彼得森图”。

7.

权（weight）与图的边或弧相关的数值，用于表示从一个顶点到另一个顶点的距离、所需的时间或花费的代价等。6.顶点的度10图7.3彼得森图图7.3彼得森图11

8.

网络网络也称带权图，即图中的边（弧）都是带权的边（弧）。实际上，所有的图都可以看成作网络的一种特殊情况，即一个图可以被看作是一个所有边（弧）具有相同权的网络。带权图的结构与现实生活紧密联系，因此它通常具有更加广泛的应用。图7.4给出了一个无向带权图的例子，它表示一张区域地图，图中的顶点为城市，边代表两个城市之间的连通关系，边上的权代表公路造价。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最低？这是典型的无向图最小生成树问题。8.网络121082118567251933图7.4城市连接图1082118567251933图7.4城市连接图13

9.

路径（path）顶点vi与vj之间的通路称为从vi到vj的路径。路径中边（弧）的数目称为路径长度。路径可以简便地用顶点序列表示，如(a,b,c,d)或a→b→c→d。路径中有连接边（弧）的两个顶点称为邻接顶点。如果路径中没有重复边（弧），那么该路径叫做简单路径。如果路径中没有重复顶点，则该路径叫做基本路径。显然，基本路径一定是简单路径。如果始点与终点相同，那么该路径称为回路。没有重复边（弧）的回路称为简单回路，而除始点与终点外，没有其他重复顶点的回路称为基本回路。9.路径（path）14例如：a→b→c→d是一条基本路径a→b→c→d→b→e是一条简单路径a→b→c→a是一条基本回路例如：15

10.

子图如果图G=(V,E)和图G’=(V’,E’)，满足V’⊆V和E’⊆E，则称G’为G的子图。如果G’为G的子图，且G’≠G，则称G’是G的真子图。当V’＝V，E’⊆E时，则称G’是G的生成子图。10.子图16

ABECD(a)G1的2个子图ABCED(b)G1的生成子图图7.5子图ABECD(a)G1的2个子图ABCED(b)G1的生17

11.

连通与连通图如果从顶点v到顶点w有一条路径，则说v和w是连通的。如果无向图中任意两个顶点都是连通的，则称该图是连通图。对于一个非连通图的无向图，其中的每一个连通部分称作一个连通分量，即连通分量是无向图中的极大连通子图。图7.6(a)是一个非连通的无向图，它有2个连通分量，如图7.6(b)。对于有向图来说，如果任意一对顶点vi和vj（i≠j）都存在从vi到vj的一条路径，也存在从vj到vi的一条路径，则称该有向图是强连通图。对于一个非强连通图的有向图，其中的每一个强连通部分称作一个强连通分量，即强连通分量是有向图中的极大强连通子图。如图7.7是图7.2的强连通分量。

11.连通与连通图18

ABCDEFABCDEF图7.6无向图及连通分量(a)非连通的无向图(b)2个连通分量ABCDEFABCDEF图7.6无向图及连通分量19

12.

生成树生成树是无向连通图的极小连通子图。它包含了图的所有n个顶点，但只包含图的n-1条边。这n-1条边使这n个顶点互相连通。在生成树中添加任意一条属于原图中的边必定会产生回路。而减少生成树中的任意一条边，则必然成为非连通的。12.生成树20

13.

稀疏图和稠密图稀疏图和稠密图是两个相对的定义。通常认为边（弧）较少的图就是一个稀疏图；相对地，接近完全图的图就是稠密图。注意这里给出的定义仅仅是一个形式化的描述，没有一个十分完备的标准来界定到底多少才算稀疏。之所以提出稀疏图和稠密图的概念，是因为稀疏图可以使用稀疏矩阵来表示，进而节省存储空间。13.稀疏图和稠密图211.3图的基本操作

1.

非带权图的基本操作■GetElem功能：求顶点的元素值■SetElem功能：设置顶点的元素值■GetVexNum功能：返回顶点个数■GetEdgeNum功能：返回边的个数■GetArcNum功能：返回弧的个数1.3图的基本操作1.非带权图的基本操作22■FirstAdjVex功能：返回指定顶点的第一个邻接顶点■NextAdjVex功能：返回下一个邻接顶点■InsertEdge功能：插入一条边■DeleteEdge功能：删除一条边■InsertArc功能：插入一条弧■DeleteArc功能：删除一条弧■EdgeExist功能：判断指定顶点之间是否存在边■FirstAdjVex23■ArcExist功能：判断指定顶点之间是否存在弧■DFTraverse功能：深度优先遍历■BFTraverse功能：广度优先遍历■ArcExist24

2.带权图（网）的基本操作除上述操作外，还应提供如下基本操作：■SetWeight功能：设置指定边（弧）的权值■GetWeight功能：返回指定边（弧）的权值■InsrtWeiEdge功能：插入一条带权边■InsrtWeiArc功能：插入一条带权弧

2.带权图（网）的基本操作除上述操作外，还应提供如下基25§2图的实现

▲邻接矩阵▲邻接矩阵图的实现▲邻接表▲邻接表图的实现§2图的实现▲邻接矩阵262.1邻接矩阵图可以有多种存储表示方法，但最常用的只有两种：邻接矩阵和邻接表。

2.1邻接矩阵图可以有多种存储表示方法，但最常用的只271.邻接矩阵的定义邻接矩阵存储结构的基本思想是：用一维数组存储图中顶点的信息，而用矩阵表示各顶点之间的邻接关系。显然，该方法的关键是顶点之间的邻接关系的存储表示。1.邻接矩阵的定义邻接矩阵存储结构的基本思想是：28假设图G=(V,E)有n个确定的顶点，即V={v0,v1,…,vn

}，则可用一个n×n的矩阵来表示G中各顶点之间的邻接关系，故称邻接矩阵（AdjacencyMatrix）。对于非网图，矩阵元素的定义如下：

1

存在(vi,vj

)或<vi,vj

>

AM[i][j]=

0

不存在(vi,vj

)或<vi,vj

>对于网图，矩阵元素的定义如下：

wij

存在(vi,vj)或<vi,vj

>

AM[i][j]=

∞不存在(vi,vj

)或<vi,vj

>其中，∞是比任何权值更大的一个数值。假设图G=(V,E)有n个确定的顶点，即V={v0,v29图7.7一个无向图的邻接矩阵表示AM=0101101101001100V0V3V1V2图7.7一个无向图的邻接矩阵表示0101V0V3V30图7.8一个网图的邻接矩阵表示AM=∞964∞9∞45∞64∞

∞735∞

∞8∞∞78∞V0V3V1V2V49634578图7.8一个网图的邻接矩阵表示∞964∞V031邻接矩阵存储方法的特点：

■无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上／下三角矩阵的元素即可。■对于无向图，邻接矩阵的第i行／列非0元素（或非∞元素）的个数正好是第i个顶点的度。■对于有向图，邻接矩阵的第i行非0元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)，而第i列非0元素（或非∞元素）的个数正好是第i个顶点的入度ID(vi)。■用邻接矩阵方法存储图，很容易确定图中任意2个顶点之间是否有边（弧）相连；但要确定图中有多少条边（弧），则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是使用邻接矩阵存储方法的局限性。邻接矩阵存储方法的特点：■无向图的邻接矩阵一定是一个对称322.图的抽象类

图的抽象类规定了图的最基本的操作。2.图的抽象类图的抽象类规定了图的最基本的操作。33template<classTypeOfVer>classGraph{protected:intverNum,edgeNum;//顶点数和边数public:

//插入／添加一个新顶点virtualvoidInsertVer(TypeOfVere)=0;//删除顶点v及其所有相关的边virtualboolDeleteVer(TypeOfVerv)=0;virtualboolInsertEdge(TypeOfVeru,TypeOfVerv)=0;virtualboolDeleteEdge(TypeOfVeru,TypeOfVerv)=0;virtualboolEdgeExsit(TypeOfVeru,TypeOfVerv)=0;virtualintGetVerNum(){returnverNum;}virtualintGetEdgeNum(){returnedgeNum;}};template<classTypeOfVer>343.邻接矩阵图的实现

template<classTypeOfEdge,classTypeOfVer>classAdjMatrixGraph:publicGraph<TypeOfVer>{protect:TypeOfVer*verList;//顶点元素表TypeOfWeight**edge;//存放边的邻接矩阵intGetVerPos(TypeOfVerv)；//获取顶点在图中的位置3.邻接矩阵图的实现template<classTyp35public:AdjMatrixGraph(intn;TypeOfVerv[]);~AdjMatrixGraph();intGetVerPos(TypeOfVerv)；//获取顶点在图中的位置voidInsertVer(TypeOfVere);voidDeleteVer(TypeOfVerv);boolInsertEdge(TypeOfVeru,TypeOfVerv);boolDeleteEdge(TypeOfVeru,TypeOfVerv);boolEdgeExsit(TypeOfVeru,TypeOfVerv);boolEmpty();boolSetElem(intv,TypeOfVere);boolGetElem(intv,TypeOfVer&e);intFirstAdjVer(intv);//返回顶点v的第一个邻接点intNextAdjVer(intv,intw);//返回v的邻接点w的下一个邻接点};public:36算法7.1AdjMatrixGraph

功能：（构造函数）图的初始化AdjMatrixGraph（intn,TypeOfVerelem[]）{inti,j;verNum=n;edgeNum=0;verList=newTypeOfVer[n];//初始化顶点元素表for(i=1;i<=n;i++)verList[i]=elem[i];edge=newTypeOfEdge*[n];//初始化邻接矩阵for(i=1;i<=n;i++){edge[i]=newTypeOfEdge[n];for(j=1;j<=n;j++)edge[i][j]=0;}}算法7.1AdjMatrixGraph

功能：（构造函37算法7.2~AdjMatrixGraph

功能：（析构函数）销毁图~AdjMatrixGraph(){intj;delete[]verList;for(j=1;j<=verNum;j++)delete[]edge[j];//释放邻接矩阵的行指针delete[]edge;//释放邻接矩阵}算法7.2~AdjMatrixGraph

功能：（析构38算法7.3GetVerPos

功能：获取顶点在图中的位置

intGetVerPos(TypeOfVerv){intj;for(j=1;j<=verNum;j++)if(verList[j]==v)returnj;return0;}算法7.3GetVerPos

功能：获取顶点在图中的位置39算法7.4InsertEdge

功能：插入一条边boolInsertEdge(TypeOfVeru,TypeOfVerv){inte1,e2;e1=GetVerPos(u);e2=GetVerPos(v);if(e1==0||e2==0)returnFALSE;if(edge[e1][e2]!=0)returnFALSE;edge[e1][e2]=1;edgeNum++;returnTRUE;}算法7.4InsertEdge

功能：插入一条边bool404.邻接矩阵网图的实现template<classTypeOfEdge,classTypeOfVer>classAdjMatrixNetwork:publicAdjMatrixGraph<TypeEdge,TypeOfVer>{private::TypeOfEdgenoEdge;//∞的表示public:AdjMatrixNetwork(intn;TypeOfVerv[]);~AdjMatrixNetwork();boolInsertEdge(TypeOfVeru,TypeOfVerv,TypeOfEdgew);};4.邻接矩阵网图的实现template<classTy41算法7.5InsertEdge

功能：插入一条带权边boolInsertEdge(TypeOfVeru,TypeOfVerv,TypeOfEdgew){inte1,e2;e1=GetVerPos(u);e2=GetVerPos(v);if(e1==0||e2==0)returnFALSE;if(edge[e1][e2]!=noEdge)returnFALSE;edge[e1][e2]=w;edgeNum++;returnTRUE;}算法7.5InsertEdge

功能：插入一条带权边bo42算法7.6FirstAdjVer

功能：返回顶点v的第一个邻接点的位置

intFirstAdjVer(intv){if(v>0&&v<=verNum){for(intj=1;j<=verNum;j++)if(edge[v][j]>0&&edge[v][j]<noEdge)returnj;}return0;}算法7.6FirstAdjVer

功能：返回顶点v的第一43算法7.7NextAdjVer

功能：返回v的邻接点w的下一个邻接点intNextAdjVer(intv){if(v>0&&v<=verNum){for(intj=w+1;j<=verNum;j++)if(edge[v][j]>0&&edge[v][j]<noEdge)returnj;}return0;}算法7.7NextAdjVer

功能：返回v的邻接点w的442.2邻接表邻接表是图的一种顺序存储与链式存储相结合的存储方法。2.2邻接表邻接表是图的一种顺序存储与链式存储相结合45It'sOverIt'sOver46数据结构（数据结构及其算法）

冯耀霖数据结构（数据结构及其算法）冯耀霖47

Chap7

图

图的基本概念

图的实现

图的遍历

最短路径问题

最小生成树Chap7图图的基本概念48§1图的基本概念

▲图的定义▲图的相关术语▲图的基本操作§1图的基本概念▲图的定义49图（graph）是一种复杂的数据结构，它能够为解决许多具体问题提供非常理想的非数值数学模型。当今，图结构已广泛应用于计算机科学、系统工程、管理工程、通信与网络理论、自动控制、运筹学以至社会科学等诸多学科。图形结构所研究的图并非生活中所说的图画或地图，而是用一些点和线来表示事物之间关系的某种抽象模型，本质上是数据集合与其上关系的图形表示。图（graph）是一种复杂的数据结构，它能够为解决许多501.1图的定义

图G由两个非空集合V和E组成。V是顶点（Vertex）的有限集，在图中数据元素称为顶点或结点。E是边（Edge）的有限集，边是顶点的无序对或有序对，描述了顶点之间的逻辑关系，每一条边连接V中两个不同的顶点。图的形式化定义为G=(V,E)V={vi|vi∈ElemType}

E={(vi,vj)|vi,vj∈V}或E={<vi,vj>|vi,vj∈V}其中，(vi,vj)为无序对，表示一条无向边，简称边；

<vi,vj>为有序对，表示一条有向边，简称弧。1.1图的定义图G由两个非空集合V和E组成。V是顶511.2图的相关术语

1.

无向图在一个图中，如果连接任意2个顶点的是一条无向边(vi,vj)，即顶点之间的连线是无方向的，则称该图为无向图。如图7.1。

G1=(V1,E1)

V1={A,B,C,D,E}

E1={(A,B),(A,D),(B,C),(B,E),(C,D),(C,E)}1.2图的相关术语1.无向图52ABCDEABCD图7.1无向图G1图7.2有向图G2ABCDEABCD图7.1无向图G1图7.2有向图G532.有向图在一个图中，如果连接任意2个顶点的是一条弧<vi

,vj>，即顶点之间的连线是有方向的，则称该图为有向图。对于弧<vi,vj>，vi被称为起点（弧尾），vj被称为终点（弧头）。如图7.2。

G1=(V1,E1)

V1={A,B,C,D}

E1={<A,B>,<A,C>,<C,D>,<D,A>,<D,C>}

3.

混合图混合图是既含有边又含有弧的图。2.有向图54

4.

无向完全图在一个无向图中，如果任意2个顶点之间都有一条边连接，则称该图为无向完全图。在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

5.

有向完全图在一个有向图中，如果任意2个顶点之间都有方向互为相反的2条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条弧。4.无向完全图55

6.

顶点的度顶点的度是指依附于某顶点v的边数，记作deg(v)。在有向图中，顶点的度有入度和出度之分。对于任意顶点v，以v为起点的弧的数目称为v的出度，记为OD(v)；而以v为终点的弧的数目称为v的入度，记为ID(v)。各个顶点的度都相等的无向图也称为正则图，并记作k-正则图，其中k是各顶点的度。图7.3是个3-正则图，也被称为“彼得森图”。

7.

权（weight）与图的边或弧相关的数值，用于表示从一个顶点到另一个顶点的距离、所需的时间或花费的代价等。6.顶点的度56图7.3彼得森图图7.3彼得森图57

8.

网络网络也称带权图，即图中的边（弧）都是带权的边（弧）。实际上，所有的图都可以看成作网络的一种特殊情况，即一个图可以被看作是一个所有边（弧）具有相同权的网络。带权图的结构与现实生活紧密联系，因此它通常具有更加广泛的应用。图7.4给出了一个无向带权图的例子，它表示一张区域地图，图中的顶点为城市，边代表两个城市之间的连通关系，边上的权代表公路造价。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最低？这是典型的无向图最小生成树问题。8.网络581082118567251933图7.4城市连接图1082118567251933图7.4城市连接图59

9.

路径（path）顶点vi与vj之间的通路称为从vi到vj的路径。路径中边（弧）的数目称为路径长度。路径可以简便地用顶点序列表示，如(a,b,c,d)或a→b→c→d。路径中有连接边（弧）的两个顶点称为邻接顶点。如果路径中没有重复边（弧），那么该路径叫做简单路径。如果路径中没有重复顶点，则该路径叫做基本路径。显然，基本路径一定是简单路径。如果始点与终点相同，那么该路径称为回路。没有重复边（弧）的回路称为简单回路，而除始点与终点外，没有其他重复顶点的回路称为基本回路。9.路径（path）60例如：a→b→c→d是一条基本路径a→b→c→d→b→e是一条简单路径a→b→c→a是一条基本回路例如：61

10.

子图如果图G=(V,E)和图G’=(V’,E’)，满足V’⊆V和E’⊆E，则称G’为G的子图。如果G’为G的子图，且G’≠G，则称G’是G的真子图。当V’＝V，E’⊆E时，则称G’是G的生成子图。10.子图62

ABECD(a)G1的2个子图ABCED(b)G1的生成子图图7.5子图ABECD(a)G1的2个子图ABCED(b)G1的生63

11.

连通与连通图如果从顶点v到顶点w有一条路径，则说v和w是连通的。如果无向图中任意两个顶点都是连通的，则称该图是连通图。对于一个非连通图的无向图，其中的每一个连通部分称作一个连通分量，即连通分量是无向图中的极大连通子图。图7.6(a)是一个非连通的无向图，它有2个连通分量，如图7.6(b)。对于有向图来说，如果任意一对顶点vi和vj（i≠j）都存在从vi到vj的一条路径，也存在从vj到vi的一条路径，则称该有向图是强连通图。对于一个非强连通图的有向图，其中的每一个强连通部分称作一个强连通分量，即强连通分量是有向图中的极大强连通子图。如图7.7是图7.2的强连通分量。

11.连通与连通图64

ABCDEFABCDEF图7.6无向图及连通分量(a)非连通的无向图(b)2个连通分量ABCDEFABCDEF图7.6无向图及连通分量65

12.

生成树生成树是无向连通图的极小连通子图。它包含了图的所有n个顶点，但只包含图的n-1条边。这n-1条边使这n个顶点互相连通。在生成树中添加任意一条属于原图中的边必定会产生回路。而减少生成树中的任意一条边，则必然成为非连通的。12.生成树66

13.

稀疏图和稠密图稀疏图和稠密图是两个相对的定义。通常认为边（弧）较少的图就是一个稀疏图；相对地，接近完全图的图就是稠密图。注意这里给出的定义仅仅是一个形式化的描述，没有一个十分完备的标准来界定到底多少才算稀疏。之所以提出稀疏图和稠密图的概念，是因为稀疏图可以使用稀疏矩阵来表示，进而节省存储空间。13.稀疏图和稠密图671.3图的基本操作

1.

非带权图的基本操作■GetElem功能：求顶点的元素值■SetElem功能：设置顶点的元素值■GetVexNum功能：返回顶点个数■GetEdgeNum功能：返回边的个数■GetArcNum功能：返回弧的个数1.3图的基本操作1.非带权图的基本操作68■FirstAdjVex功能：返回指定顶点的第一个邻接顶点■NextAdjVex功能：返回下一个邻接顶点■InsertEdge功能：插入一条边■DeleteEdge功能：删除一条边■InsertArc功能：插入一条弧■DeleteArc功能：删除一条弧■EdgeExist功能：判断指定顶点之间是否存在边■FirstAdjVex69■ArcExist功能：判断指定顶点之间是否存在弧■DFTraverse功能：深度优先遍历■BFTraverse功能：广度优先遍历■ArcExist70

2.带权图（网）的基本操作除上述操作外，还应提供如下基本操作：■SetWeight功能：设置指定边（弧）的权值■GetWeight功能：返回指定边（弧）的权值■InsrtWeiEdge功能：插入一条带权边■InsrtWeiArc功能：插入一条带权弧

2.带权图（网）的基本操作除上述操作外，还应提供如下基71§2图的实现

▲邻接矩阵▲邻接矩阵图的实现▲邻接表▲邻接表图的实现§2图的实现▲邻接矩阵722.1邻接矩阵图可以有多种存储表示方法，但最常用的只有两种：邻接矩阵和邻接表。

2.1邻接矩阵图可以有多种存储表示方法，但最常用的只731.邻接矩阵的定义邻接矩阵存储结构的基本思想是：用一维数组存储图中顶点的信息，而用矩阵表示各顶点之间的邻接关系。显然，该方法的关键是顶点之间的邻接关系的存储表示。1.邻接矩阵的定义邻接矩阵存储结构的基本思想是：74假设图G=(V,E)有n个确定的顶点，即V={v0,v1,…,vn

}，则可用一个n×n的矩阵来表示G中各顶点之间的邻接关系，故称邻接矩阵（AdjacencyMatrix）。对于非网图，矩阵元素的定义如下：

1

存在(vi,vj

)或<vi,vj

>

AM[i][j]=

0

不存在(vi,vj

)或<vi,vj

>对于网图，矩阵元素的定义如下：

wij

存在(vi,vj)或<vi,vj

>

AM[i][j]=

∞不存在(vi,vj

)或<vi,vj

>其中，∞是比任何权值更大的一个数值。假设图G=(V,E)有n个确定的顶点，即V={v0,v75图7.7一个无向图的邻接矩阵表示AM=0101101101001100V0V3V1V2图7.7一个无向图的邻接矩阵表示0101V0V3V76图7.8一个网图的邻接矩阵表示AM=∞964∞9∞45∞64∞

∞735∞

∞8∞∞78∞V0V3V1V2V49634578图7.8一个网图的邻接矩阵表示∞964∞V077邻接矩阵存储方法的特点：

■无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上／下三角矩阵的元素即可。■对于无向图，邻接矩阵的第i行／列非0元素（或非∞元素）的个数正好是第i个顶点的度。■对于有向图，邻接矩阵的第i行非0元素（或非∞元素）的个数正好是第i个顶点的出度OD(vi)，而第i列非0元素（或非∞元素）的个数正好是第i个顶点的入度ID(vi)。■用邻接矩阵方法存储图，很容易确定图中任意2个顶点之间是否有边（弧）相连；但要确定图中有多少条边（弧），则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是使用邻接矩阵存储方法的局限性。邻接矩阵存储方法的特点：■无向图的邻接矩阵一定是一个对称782.图的抽象类

图的抽象类规定了图的最基本的操作。2.图的抽象类图的抽象类规定了图的最基本的操作。79template<classTypeOfVer>classGraph{protected:intverNum,edgeNum;//顶点数和边数public:

//插入／添加一个新顶点virtualvoidInsertVer(TypeOfVere)=0;//删除顶点v及其所有相关的边virtualboolDeleteVer(TypeOfVerv)=0;virtualboolInsertEdge(TypeOfVeru,TypeOfVerv)=0;virtualboolDeleteEdge(TypeOfVeru,TypeOfVerv)=0;virtualboolEdgeExsit(TypeOfVeru,TypeOfVerv)=0;virtualintGetVerNum(){returnverNum;}virtualintGetEdgeNum(){returnedgeNum;}};template<classTypeOfVer>803.邻接矩阵图的实现

template<classTypeOfEdge,classTypeOfVer>classAdjMatrixGraph:publicGraph<TypeOfVer>{protect:TypeOfVer*verList;//顶点元素表TypeOfWeight**edge;//存放边的邻接矩阵intGetVerPos(TypeOfVerv)；//获取顶点在图中的位置3.邻接矩阵图的实现template<classTyp81public:AdjMatrixGraph(intn;TypeOfVerv[]);~AdjMatrixGraph();intGetVerPos(TypeOfVerv)；//获取顶点在图中的位置voidInsertVer(TypeOfVere);voidDeleteVer(TypeOfVerv);boolInsertEdge(TypeOfVeru,TypeOfVerv);boolDeleteEdge(TypeOfVeru,TypeOfVerv);boolEdgeExsit(TypeOfVeru,TypeOfVerv);boolEmpty();boolSetElem(intv,TypeOfVere);boolGetElem(intv,TypeOfVer&e);intFirstAdjVer(intv);//返回顶点v的第一个邻接点intNextAdjVer(intv,intw);//返回v的邻接点w的下一个邻接点};public:82算法7.1AdjMatrixGraph

功能：（构造函数）图的初始化AdjMatrixGraph（intn,TypeOfVerelem[]）{inti,j;verNum=n;edgeNum=0;verList=newTypeOfVer[n];//初始化顶点元素表for(i=1;i<=n;i++)verList[i]=elem[i];edge=newTypeOfEdge*[n];//初始化邻接矩阵for(i=1;i<=n;i++){edge[i]=newTypeOfEdge[n];for(j=1;j<=n;j++)edge[i][j]=0;}}算法7.1AdjMatrixGraph

功能：（构造函83算法7.2~AdjMatrixGraph

功能：（析构函数）销毁图~AdjMatrixGraph(