第7章 图及其应用精选PPT.ppt

《第7章 图及其应用精选PPT.ppt》由会员分享，可在线阅读，更多相关《第7章 图及其应用精选PPT.ppt（193页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 图及其应用第1页，本讲稿共193页 图图图图(Graph)(Graph)：是一种网状数据结构。是顶点集是一种网状数据结构。是顶点集V和连接这些顶点的弧集和连接这些顶点的弧集(边集边集)R所组成的结构记为所组成的结构记为:G=(V,R）有向图：有向图：有向图：有向图：若若图中的边是顶点的有序对图中的边是顶点的有序对图中的边是顶点的有序对图中的边是顶点的有序对,则称此图则称此图为有向图。为有向图。有向边又称为弧有向边又称为弧有向边又称为弧有向边又称为弧,通常用尖括弧表示一条通常用尖括弧表示一条有向边有向边,vi,vj表示从顶点表示从顶点vi到到vj的一段弧的一段弧,vi称为称为边的始点边的

2、始点(或弧尾或弧尾),vj称为边的终点称为边的终点(或弧头或弧头),vi,vj和和 vj,vi代表两条不同的弧。代表两条不同的弧。132第2页，本讲稿共193页无无无无向向向向图图图图：若若图图图图中中中中的的的的边边边边是是是是顶顶顶顶点点点点的的的的无无无无序序序序对对对对,则则称称此此图图为无向图。为无向图。通通常常用用圆圆圆圆括括括括号号号号表表表表示示示示无无无无向向向向边边边边,(vi,vj)表表示示顶顶点点vi和和vj间间相相连连的的边边。在在无无向向图图中中(vi,vj)和和(vj,vi)表表示示同同一一条条边边.2341第3页，本讲稿共193页完全图、稠密图、稀疏图完全图、稠

3、密图、稀疏图完全图、稠密图、稀疏图完全图、稠密图、稀疏图 具具有有n个个顶顶点点，n(n-1)/2条条边边的的图图，称称为为完完完完全全全全无无无无向向向向图图图图，具具有有n个个顶顶点点，n(n-1)条条弧弧的的有有向向图图,称称为为完完完完全全全全有有有有向向向向图图图图。完完全全无无向向图和完全有向图都称为图和完全有向图都称为完全图完全图完全图完全图。对对于于一一般般无无向向图图，顶顶点点数数为为n，边边数数为为e，则则 0e n(n-1)/2。对对于于一一般般有有向向图图，顶顶点点数数为为n，弧弧数数为为e，则则 0en(n-1)。当当一一个个图图接接近近完完全全图图时时，则则称称它它

4、为为稠稠稠稠密密密密图图图图，相相反反地地，当一个图中含有较少的边或弧时，则称它为当一个图中含有较少的边或弧时，则称它为稀疏图稀疏图稀疏图稀疏图。第4页，本讲稿共193页子图：子图：子图：子图：对于图对于图G=(V,R),G=(V,R),若有若有V V,R R,则称图则称图G是是G的一个子图。的一个子图。下图给出了下图给出了G与其子图与其子图G。2435167图G435167图G 第5页，本讲稿共193页邻接点邻接点邻接点邻接点 对对于于无无无无向向向向图图图图 G=(V,R)，如如如如果果果果边边边边(v(v，v)v)R R，则则则则称称称称顶顶顶顶点点点点v,v,vv互互互互为为为为邻邻邻

5、邻接接接接点点点点，即即v,v相相邻邻接接。边边（v,v）依依附附于于顶顶点点v和和v，或或者说边（者说边（v，v）与顶点）与顶点v和和v相关联。相关联。对对于于有有有有向向向向图图图图G=(V，R)而而言言，若若若若弧弧弧弧vvR R，则则则则称称称称顶顶顶顶点点点点v v邻邻邻邻接接接接到到到到顶顶顶顶点点点点vv，顶顶顶顶点点点点vv邻邻邻邻接接接接自自自自顶顶顶顶点点点点v v，或或者者说说弧弧与与顶顶点点v和和v相关联。相关联。2341132如：顶点如：顶点1、2互为邻接点互为邻接点如：顶点如：顶点1邻接到顶点邻接到顶点2 顶点顶点2邻接自顶点邻接自顶点1第6页，本讲稿共193页权与

6、网权与网权与网权与网 在在实实际际应应用用中中，图图的的边边或或弧弧上上往往往往与与具具有有一一定定意意义义的的数数有有关关，即即每每每每一一一一条条条条边边边边都都都都有有有有与与与与它它它它相相相相关关关关的的的的数数数数，称称为为权权权权，我们将我们将这种带权的图这种带权的图这种带权的图这种带权的图叫做叫做加权图加权图加权图加权图或或网网网网，如图所示。，如图所示。第7页，本讲稿共193页路径和回路路径和回路路径和回路路径和回路路径：路径：路径：路径：所谓顶点所谓顶点vp 到顶点到顶点vq之间的路径之间的路径,是指是指顶点序列顶点序列顶点序列顶点序列vp,vi1,vi2,vim,vq,其

7、中（其中（vp,vi1）,（vi1,vi2）,（vim,vq）分别为图中的边。）分别为图中的边。路径长度：路径长度：路径长度：路径长度：路径上边的数目路径上边的数目路径上边的数目路径上边的数目称为路径长度。称为路径长度。简单路径：简单路径：简单路径：简单路径：序列中序列中顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径称为简单路径。称为简单路径。回路回路回路回路或或或或环：环：环：环：如果如果路径的起点和终点相同路径的起点和终点相同路径的起点和终点相同路径的起点和终点相同(即即vp=vq),则称此则称此路径为回路或环。路径为回路或环。第8页，本讲稿共193页 如

8、图所示的无向图中如图所示的无向图中,顶点顶点顶点顶点v1v1到顶点到顶点到顶点到顶点v5v5的路径有两条的路径有两条的路径有两条的路径有两条,分别为分别为v1,v2,v3,v4与与v1,v5,v4,路径长度分别为路径长度分别为路径长度分别为路径长度分别为3 3和和和和2 2。v1到到v5的两条路径都为的两条路径都为简单路简单路简单路简单路径径径径。简单回路：简单回路：简单回路：简单回路：除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外,其它顶点不重复其它顶点不重复其它顶点不重复其它顶点不重复出现的回路出现的回路出现的回路出现的回路

9、为为简单回路简单回路或者或者简单环简单环。第9页，本讲稿共193页 连通图和强连通图连通图和强连通图连通图和强连通图连通图和强连通图 在在无向图无向图无向图无向图中，若从顶点中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和顶和顶点点j是是连通的连通的。若任意两个顶点都是连通的，则称此无向图。若任意两个顶点都是连通的，则称此无向图为为连通图连通图，否则称为，否则称为非连通图非连通图。连通图和非连通图示例见图连通图和非连通图示例见图:第10页，本讲稿共193页 对对于于有有有有向向向向图图图图来来说说,若若图图中中任任任任意意意意一一一一对对对对顶顶顶顶点点点点v vi i和和和和

10、v vj j(ij)(ij)均均均均有有有有从从从从v vi i到到到到 v vj j及及及及从从从从 v vj j到到到到 v vi i的的的的有有有有向向向向路路路路径径径径,则则称称该该有有有有向向向向图图图图是是是是强强强强连连连连通通通通的的的的。强连通图和非强连通图示例见图强连通图和非强连通图示例见图:第11页，本讲稿共193页连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量 无无无无向向向向图图图图中中，极极大大的的连连通通子子图图为为该该图图的的连连通通分分量量。显显然然，任任何何连连通通图图的的连连通通分分量量只只有有一一个个，即即它它本本身身

11、，而而非非连连通通图图有多个连通分量。有多个连通分量。24351672435167第12页，本讲稿共193页 有有向向图图中中的的极极极极大大大大强强强强连连连连通通通通子子子子图图图图称称为为该该有有向向图图的的强强强强连连连连通通通通分分分分量量量量。显显然然，任任何何强强连连通通图图的的强强连连通通分分量量只只有有一一个个，即即它本身，而非强连通图有多个强连通分量。它本身，而非强连通图有多个强连通分量。下图不是强连通的下图不是强连通的,但它有两个强连通分量但它有两个强连通分量:132321第13页，本讲稿共193页顶点的度顶点的度顶点的度顶点的度2341如：顶点如：顶点1的度为的度为3顶

12、点的顶点的度度度度 是指是指依附于某顶点依附于某顶点依附于某顶点依附于某顶点v vi i的边数的边数的边数的边数,通常记通常记 为为D(v)第14页，本讲稿共193页顶点的度顶点的度顶点的度顶点的度132如：顶点如：顶点2的入度为的入度为2 出度为出度为1有向图有向图有向图有向图中中,要区别顶点的入度和出度的概念。要区别顶点的入度和出度的概念。顶点顶点v的的入度入度入度入度 是指是指以以以以v v为终点的弧的数目为终点的弧的数目为终点的弧的数目为终点的弧的数目记为记为ID(v)顶点顶点v的的出度出度出度出度 是指是指以以以以v v为始点的弧的数目为始点的弧的数目为始点的弧的数目为始点的弧的数目

13、记为记为OD(v)显然：显然：D(v)=ID(v)+OD(v)第15页，本讲稿共193页 7.2.1 邻接矩阵存储法 7.2.2 邻接表表示法7.2 图的存储第16页，本讲稿共193页图的抽象数据类型图的抽象数据类型class Graph/对象对象:由一个顶点的非空集合和一个边集合构成由一个顶点的非空集合和一个边集合构成/每条边由一对顶点来表示。每条边由一对顶点来表示。public:Graph();/建立一个空的图建立一个空的图 void InsertVertex(const T vertex);/插入一个顶点插入一个顶点vertex,该顶点暂时没有入边该顶点暂时没有入边 void Inser

14、tEdge(int v1,int v2,int weight);/在图中插入一条边在图中插入一条边(v1,v2,w)void RemoveVertex(int v);/在图中删除顶点在图中删除顶点v和所有关联到它的边和所有关联到它的边 第17页，本讲稿共193页 void RemoveEdge(int v1,int v2);/在图中删去边在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点若图中没有顶点,则返回则返回true,否则返回否则返回false T GetWeight(int v1,int v2);/函数返回边函数返回边(v1,v2)的权值的权值 int GetFi

15、rstNeighbor(int v);/给出顶点给出顶点 v 第一个邻接顶点的位置第一个邻接顶点的位置 int GetNextNeighbor(int v,int w);/给出顶点给出顶点 v 的某邻接顶点的某邻接顶点 w 的下一个邻接顶的下一个邻接顶点点;第18页，本讲稿共193页图的存储表示图的存储表示图的模板基类图的模板基类 在模板类定义中的数据类型参数表在模板类定义中的数据类型参数表 中，中，T是顶点数据的类型，是顶点数据的类型，E是边上所附数据的是边上所附数据的类型。类型。这个模板基类是按照最复杂的情况（即带权无向图）来这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要

16、使用非带权图，可将数据类型参数定义的，如果需要使用非带权图，可将数据类型参数表表 改为改为。如果使用的是有向图，也可以对程序做相应的改动。如果使用的是有向图，也可以对程序做相应的改动。第19页，本讲稿共193页图的模板基类图的模板基类 const int maxWeight=0 x7fffffff;/无穷大的值(=)const int DefaultVertices=30;/最大顶点数(=n)template class Graph /图的类定义protected:int maxVertices;/图中最大顶点数 int numEdges;/当前边数 int numVertices;/当前顶点

17、数 int GetVertexPos(T vertex);/给出顶点vertex在图中位置public:第20页，本讲稿共193页 Graph(int sz=DefaultVertices);/构造函数 Graph();/析构函数 bool IsEmpty()/判图空否 return numEdges=0;int NumberOfVertices()return numVertices;/返回当前顶点数 int NumberOfEdges()return numEdges;/返回当前边数virtual T GetValue(int i);/取顶点 i 的值 virtual E GetWeigh

18、t(int v1,int v2);/取边上权值 virtual int GetFirstNeighbor(int v);/取顶点 v 的第一个邻接顶点第21页，本讲稿共193页virtual int GetNextNeighbor(int v,int w);/取邻接顶点 w 的下一邻接顶点 virtual bool InsertVertex(const T vertex);/插入一个顶点vertex virtual bool InsertEdge(int v1,int v2,E cost);/插入边(v1,v2),权为cost virtual bool RemoveVertex(int v);

19、/删去顶点 v 和所有与相关联边 virtual bool RemoveEdge(int v1,int v2);/在图中删去边(v1,v2);第22页，本讲稿共193页邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：用一个二维数组（矩阵）来表示图中顶点之间的相邻关系。设图设图G=(V,R)有有n(n1)个顶点个顶点,则则G的邻接矩阵是按如下定义的邻接矩阵是按如下定义的的n阶方阵阶方阵:1 若若(vi,vj)或或R(G)aij=0 反之反之第23页，本讲稿共193页例例例例:图图G1、G2的的邻邻接接矩矩阵阵分分别别表表示示为为A1和和A2,矩矩阵阵的的行、行、列号对应于图中结点的号。列号对应于图中结点

20、的号。0 1 1 11 0 1 01 1 0 11 0 1 00 1 10 0 10 1 02341132G1G2第24页，本讲稿共193页从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：（1）矩阵是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很很容容易易判判断断顶顶点点i 和和顶顶点点j之之间间是是否否有有边

21、边相相连连(看看矩矩阵阵中中i行行j列值是否为列值是否为1)。第25页，本讲稿共193页从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论:（1）矩阵不一定是对称的矩阵不一定是对称的;（2）第第i 行中行中1的个数为顶点的个数为顶点i 的出度的出度;（3）第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4）矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目;（5）很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是否有弧相连.第26页，本讲稿共193页 网的邻接矩阵表示：网的邻接矩阵

22、表示：网的邻接矩阵表示：网的邻接矩阵表示：若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具有个顶点的网，则它的邻接矩阵是具有如下性质的如下性质的nn矩阵矩阵A：若若或或(vi,vj)VR(G)反之 第27页，本讲稿共193页 5 7 4 8 5 234158475例：例：例：例：一个有向网一个有向网N及其邻接矩阵的示例。及其邻接矩阵的示例。第28页，本讲稿共193页 n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率空间效率为为O(nO(n2 2)。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间

23、。邻接矩阵法优点：邻接矩阵法缺点：容易实现图的操作，如：求某顶点的度、判断顶容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。点之间是否有边（弧）、找顶点的邻接点等等。第29页，本讲稿共193页邻接矩阵表示法的邻接矩阵表示法的C+语言类型描述如下：语言类型描述如下：template class Graphmtx:public Graph private:T*VerticesList;/顶点表顶点表 E*Edge;/邻接矩阵邻接矩阵int GetVertexPos(T vertex)/给出顶点给出顶点vertex在图中的位置在图中的位置 for(int i=0;

24、i=0&i=numVertices?VerticesListi:NULL;E GetWeight(int v1,int v2)/取边取边(v1,v2)上权值上权值 return v1!=-1&v2!=-1?Edgev1v2:0;第31页，本讲稿共193页 int GetFirstNeighbor(int v);/取顶点取顶点 v 的第一个邻接顶点的第一个邻接顶点 int GetNextNeighbor(int v,int w);/取取 v 的邻接顶点的邻接顶点 w 的下一邻接顶点的下一邻接顶点 bool InsertVertex(const T vertex);/插入顶点插入顶点vertex

25、bool InsertEdge(int v1,int v2,E cost);/插入边插入边(v1,v2),权值为权值为cost bool RemoveVertex(int v);/删去顶点删去顶点 v 和所有与它相关联的边和所有与它相关联的边 bool RemoveEdge(int v1,int v2);/在图中删去边在图中删去边(v1,v2);第32页，本讲稿共193页template Graphmtx:Graphmtx(int sz)/构造函数构造函数 maxVertices=sz;numVertices=0;numEdges=0;int i,j;VerticesList=new Tmax

26、Vertices;/创建顶点表 Edge=new E*maxVertices;for(i=0;i maxVertices;i+)Edgei=new EmaxVertices;/邻接矩阵 for(i=0;i maxVertices;i+)/矩阵初始化 for(j=0;j maxVertices;j+)Edgeij=(E)(i=j)？0:maxWeight);第33页，本讲稿共193页template int Graphmtx:GetFirstNeighbor(int v)/给出顶点位置为给出顶点位置为v的第一个邻接顶点的位置的第一个邻接顶点的位置,/如果找不到如果找不到,则函数返回则函数返回-1

27、 if(v=-1)return-1；for(int col=0;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return-1;获取第一个邻接点获取第一个邻接点第34页，本讲稿共193页template int Graphmtx:getNextNeighbor(int v,int w)/给出顶点给出顶点 v 的某邻接顶点的某邻接顶点 w 的下一个邻接顶点的下一个邻接顶点 if(v=-1|w=-1)return -1；for(int col=w+1;col numVertices;col+)if(Edgevcol&E

28、dgevcol maxWeight)return col;return -1;获取下一个邻接点获取下一个邻接点第35页，本讲稿共193页 邻接表邻接表（Adjacency List）表示法是图的一种链式存储结构。）表示法是图的一种链式存储结构。它包括两个部分它包括两个部分,一部分是一部分是链表链表链表链表,另一部分是另一部分是向量向量向量向量。在在链表部分中共有链表部分中共有链表部分中共有链表部分中共有n n个链表个链表个链表个链表(n为顶点数为顶点数),用来存放边的信息。用来存放边的信息。将将每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点

29、顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中。2341第36页，本讲稿共193页 这这样样，一一个个n个个顶顶点点的的图图的的邻邻接接表表表表示示由由表表表表头头头头结结结结点点点点表表表表与与边链表边链表边链表边链表两部分构成：两部分构成：(1)(1)表头结点表：表头结点表：表头结点表：表头结点表：由所有表头结点以顺序结构（向由所有表头结点以顺序结构（向量）的形式存储量）的形式存储.。表头结点的结构如图所示，由两部分构成：表头结点的结构如图所示，由两部分构成：数据域数据域数据域数据域（vexdatavexdata）用于存储顶点的名用于存储顶点的名(值值)；指针域（指针域（指针

30、域（指针域（firstarcfirstarc）用于指向链表中第一个顶点（即与顶点用于指向链表中第一个顶点（即与顶点vi邻接的第一个邻接的第一个邻接点）。邻接点）。vexdatavexdatafirstarcfirstarc第37页，本讲稿共193页(2)(2)边链表：边链表：边链表：边链表：由邻接点链式存储的单链表。由邻接点链式存储的单链表。单链表中每个结点由三个域组成单链表中每个结点由三个域组成:邻接点域邻接点域邻接点域邻接点域(adjvex)(adjvex)指示与顶点指示与顶点vi 邻接的点在图中的位置；邻接的点在图中的位置；数据域数据域数据域数据域(info)(info)存存储和边储和边

31、(或弧或弧)相关的信息相关的信息,如权值等；如权值等；链域链域链域链域(next)(next)指向指向顶点顶点vi 的下一个邻接点的下一个邻接点。adjvexadjvexinfoinfonextarcnextarc第38页，本讲稿共193页例：例：例：例：2341第39页，本讲稿共193页5423415第40页，本讲稿共193页从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有链表中结点数目的一半为图中边数；）所有链表中结点数

32、目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e(e为边数为边数)。第41页，本讲稿共193页从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论:（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。若要求从有向图的邻接表可知，不能求出顶点的入度。若要求第第i个顶点的个顶点的入度入度入度入度，必须，必须

33、遍历整个邻接表遍历整个邻接表遍历整个邻接表遍历整个邻接表，在所有边链表，在所有边链表中查找中查找邻接点域的值为邻接点域的值为邻接点域的值为邻接点域的值为i i的结点并计数的结点并计数的结点并计数的结点并计数求和。由此可见，求和。由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不对于用邻接表方式存储的有向图，求顶点的入度并不方便，方便，它需要通过扫描整个邻接表才能得到结果。它需要通过扫描整个邻接表才能得到结果。第42页，本讲稿共193页 解解解解决决决决的的的的方方方方法法法法：逆逆逆逆邻邻邻邻接接接接表表表表法法，对对每每一一顶顶点点vi再再建建立立一一个个逆逆邻邻接接表表，即即对对每每

34、个个顶顶点点vi建建立立一一个个所所有有以以顶顶点点vi为为弧弧头头的弧的表，如图所示：的弧的表，如图所示：2341第43页，本讲稿共193页邻接表的邻接表的邻接表的邻接表的缺点：缺点：缺点：缺点：邻接表的邻接表的邻接表的邻接表的优点：优点：优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。应的单链表，没有邻接矩阵方便。第44页，本讲稿共193页用邻接表表示的图的类定义用邻接表表示的图的类定义 template struct Edge /边链表结点的定义边

35、链表结点的定义 int adjvex;/边的另一顶点位置边的另一顶点位置 E info;/边上的权值边上的权值 Edge*nextarc;/指向下一个边链表结点的指指向下一个边链表结点的指针针 Edge()/构造函数构造函数 Edge(int num,E cost=0)/构造函数构造函数 :adjvex(num),info(cost),nextarc(NULL)bool operator!=(Edge&R)const return dest!=R.dest;/判边等否判边等否;第45页，本讲稿共193页template struct Vertex /顶点的定义顶点的定义 T vexdata;/

36、顶点的名字顶点的名字Edge*firstarc;/边链表的头指针边链表的头指针;template class Graphlnk:public Graph /图的类定义图的类定义private:Vertex*NodeTable;/顶点表顶点表(各边链表的头结点各边链表的头结点)第46页，本讲稿共193页int GetVertexPos(const T vertx)/给出顶点给出顶点vertex在图中的位置在图中的位置 for(int i=0;i=0&i NumVertices)?NodeTablei.vexdata:0;bool InsertVertex(const T&vertex);bool

37、 RemoveVertex(int v);bool InsertEdge(int v1,int v2,E cost);bool RemoveEdge(int v1,int v2);int GetFirstNeighbor(int v);int GetNextNeighbor(int v,int w);第48页，本讲稿共193页template Graphlnk:Graphlnk(int sz)/构造函数：建立一个空的邻接表构造函数：建立一个空的邻接表 maxVertices=sz;NodeTable=new VertexmaxVertices;/创建顶点表数组创建顶点表数组 assert(No

38、deTable);numVertices=0;numEdges=0;for(int i=0;i maxVertices;i+)NodeTablei.firstarc=NULL;第49页，本讲稿共193页template Graphlnk:Graphlnk()/析构函数：删除一个邻接表析构函数：删除一个邻接表 for(int i=0;i numVertices;i+)Edge*p=NodeTablei.firstarc;while(p!=NULL)NodeTablei.firstarc=p-next;delete p;p=NodeTablei.firstarc;delete NodeTable;

39、/删除顶点表数删除顶点表数组组;边链表边链表(单单链表链表)的析的析构构第50页，本讲稿共193页获取第一个邻接点获取第一个邻接点template int Graphlnk:GetFirstNeighbor(int v)/给出顶点位置为给出顶点位置为 v 的第一个邻接顶点的位置的第一个邻接顶点的位置,/如果找不到如果找不到,则函数返回则函数返回-1 if(v=-1)return -1;/顶点顶点v不存在不存在 Edge*p=NodeTablev.firstarc;/对应边链表对应边链表第一个边结点第一个边结点if(p!=NULL)return p-adjvex;/存在存在,返回第返回第一个邻接

40、顶点一个邻接顶点 return -1;/第一个邻接顶点不存在第一个邻接顶点不存在;第51页，本讲稿共193页获取下一个邻接点获取下一个邻接点template int Graphlnk:GetNextNeighbor(int v,int w)/给出顶点给出顶点v的邻接顶点的邻接顶点w的下一个邻接顶点的位置的下一个邻接顶点的位置,/若没有下一个邻接顶点若没有下一个邻接顶点,则函数返回则函数返回-1 if(v!=-1)/顶点顶点v存在存在 Edge*p=NodeTablev.firstarc;while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p!=NULL&p-nex

41、tarc!=NULL)return p-nextarc-adjvex;/返回下一个邻接顶点返回下一个邻接顶点 return-1;/下一邻接顶点不存在下一邻接顶点不存在;第52页，本讲稿共193页讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.1.1.联系：联系：联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.2.2.区别：区别：区别：区别：对于任一确定的

42、无向图，邻接矩阵是唯一的（行列号对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂而邻接表的空间复杂度为度为O(n+e)。第53页，本讲稿共193页分析分析分析分析:在图的链接存储在图的链接存储(邻接表、逆邻接表邻接表、逆邻接表)中，表头向量需中，表头向量需要占用要占用n个存储单元，所有边结点需要占用个存储单元，所有边结点需要占用2e或或e存储单元，存储单元，所以最多需要（所以最多需要（n+2e）个存储单元

43、，稀疏图采用这种存储）个存储单元，稀疏图采用这种存储方式可节省存储空间。方式可节省存储空间。第54页，本讲稿共193页图图图图的的的的遍遍遍遍历历历历：沿沿着着某某条条搜搜索索路路径径对对图图中中所所有有顶顶点点各作一次访问。各作一次访问。图图的的遍遍历历比比起起树树的的遍遍历历要要复复杂杂得得多多。图图中中顶顶点点关关系系是是多多对对多多的的关关系系，图图可可能能是是非非连连通通图图，图图中中还还可可能能有有回回路路存存在在，因因此此在在访访问问了了某某个个顶顶点点后后，可可能能沿沿着着某某条路径搜索后又回到该顶点上。条路径搜索后又回到该顶点上。为为为为了了了了保保保保证证证证图图图图中中中

44、中的的的的各各各各顶顶顶顶点点点点在在在在遍遍遍遍历历历历过过过过程程程程中中中中访访访访问问问问且且且且仅仅仅仅访访访访问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志。图的遍历图的遍历第55页，本讲稿共193页 为为此此 我我们们设设置置一一个个访访访访问问问问标标标标志志志志数数数数组组组组visitednvisitedn，用用于于标标示示图图中中每每个个顶顶点点是是否否被被访访问问过过，它它它它的的的的初初初初始始始始值值值值为为为为0(“0(“假假假假”)”)，表表表表示示示示顶顶顶顶点点

45、点点均均均均未未未未被被被被访访访访问问问问；一一一一旦旦旦旦访访访访问问问问过过过过顶顶顶顶点点点点vivi，则则置置访访问问标标志志数数组组中中的的visitedivisitedi为为为为1(“1(“真真真真”)”)，以以表表示示该该顶顶点点已访问。已访问。根据搜索路径的不同，图的遍历又分：根据搜索路径的不同，图的遍历又分：深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历 广度优先搜索遍历广度优先搜索遍历广度优先搜索遍历广度优先搜索遍历第56页，本讲稿共193页 7.3.1 深度优先搜索遍历 7.3.2 广度优先搜索遍历 7.3 7.3 图的遍历图的遍历第57页，本讲稿共1

46、93页 深深深深度度度度优优优优先先先先搜搜搜搜索索索索（Depth-First Search）是是指指按按照照深深度度方方向向搜搜索索，它它类类似似于于树树的的先先根根遍遍历历，是是树树的的先先根根遍遍历历的推广。的推广。特点：特点：特点：特点：尽可能先对纵深方向进行搜索。尽可能先对纵深方向进行搜索。算法描述：算法描述：算法描述：算法描述：从某个顶点从某个顶点v0出发，进行出发，进行dfs的算法描述如下：的算法描述如下：(1)(1)访问访问访问访问v v0 0 。(2)(2)依次从依次从依次从依次从v0v0的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发

47、作深度遍历的未被访问的邻接点出发作深度遍历第58页，本讲稿共193页BAGDCFHEI 下图给出了一个深度优先搜索的过程图示，其中下图给出了一个深度优先搜索的过程图示，其中实箭实箭实箭实箭头代表访问方向，虚箭头代表回溯方向头代表访问方向，虚箭头代表回溯方向头代表访问方向，虚箭头代表回溯方向头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字，箭头旁边的数字代表搜索顺序，代表搜索顺序，A A为起始顶点为起始顶点为起始顶点为起始顶点。BAGDCFHEI遍历过程遍历过程深度优先生成树深度优先生成树第59页，本讲稿共193页 若若若若图图图图是是是是连连连连通通通通的的的的或或或或强强强强连连连连通通通

48、通的的的的，则则从从图图中中某某一一个个顶顶点点出出发发可可以访问到图中所有顶点，否则只能访问到一部分顶点。以访问到图中所有顶点，否则只能访问到一部分顶点。另外，从刚才写出的遍历结果可以看出，从某一另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是个顶点出发的遍历结果是不唯一的。但是,若我们给定若我们给定图的存储结构图的存储结构,则从某一顶点出发的遍历结果应是唯一则从某一顶点出发的遍历结果应是唯一的。的。分析与总结：分析与总结：分析与总结：分析与总结：第60页，本讲稿共193页分析连通图的深度遍历算法的实现分析连通图的深度遍历算法的实现分析连通图的深度遍历算法的实现

49、分析连通图的深度遍历算法的实现:(1)为为防防止止重重复复访访问问顶顶点点，需需为为为为每每每每个个个个顶顶顶顶点点点点设设设设置置置置一一一一个个个个访访访访问问问问标标标标志志志志 visitedivisitedi，其其值值为为 0 时时，表表示示顶顶点点 i 未未被被访访问问过；值为过；值为 1 时，表示顶点时，表示顶点 i 已被访问过。已被访问过。(2)算算法法中中需需依依依依次次次次找找找找v0v0的的的的各各各各邻邻邻邻接接接接点点点点，可可根根据据不不同同的的存存储结构具体实现。储结构具体实现。第61页，本讲稿共193页访问 v0置访问标志visitedv0=1w=GetFirs

50、tNeighbor(v0)w=0 w 已被访问过dfs(w)w=GetNextNeighbor(v0,w)N NN NY YY Y结束结束结束结束第62页，本讲稿共193页图的深度优先搜索算法图的深度优先搜索算法template void DFS(Graph G,const T v)/从顶点从顶点v出发对图出发对图G进行深度优先遍历的主过程进行深度优先遍历的主过程 int i,loc,n=G.NumberOfVertices();/顶点个数顶点个数 bool*visited=new booln;/创建辅助数组创建辅助数组 for(i=0;i n;i+)visited i=false;/辅助数组