《第7章 图及其应用PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第7章 图及其应用PPT讲稿.ppt（193页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第7章 图及其应用第1页，共193页，编辑于2022年，星期二 图图(Graph)：是一种网状数据结构。是顶点集是一种网状数据结构。是顶点集V和连接这些顶点的弧集和连接这些顶点的弧集(边集边集)R所组成的结构记为所组成的结构记为:G=(V,R）有向图：有向图：若若图中的边是顶点的有序对图中的边是顶点的有序对,则称此图则称此图为有向图。为有向图。有向边又称为弧有向边又称为弧,通常用尖括弧表示一条通常用尖括弧表示一条有向边有向边,vi,vj表示从顶点表示从顶点vi到到vj的一段弧的一段弧,vi称为称为边的始点边的始点(或弧尾或弧尾),vj称为边的终点称为边的终点(或弧头或弧头),vi,vj和和 v
2、j,vi代表两条不同的弧。代表两条不同的弧。132第2页，共193页，编辑于2022年，星期二无无向向图图：若若图图中中的的边边是是顶顶点点的的无无序序对对,则则称称此此图图为无向图。为无向图。通通常常用用圆圆括括号号表表示示无无向向边边,(vi,vj)表表示示顶顶点点vi和和vj间间相相连连的的边边。在在无无向向图图中中(vi,vj)和和(vj,vi)表表示示同同一一条条边边.2341第3页，共193页，编辑于2022年，星期二完全图、稠密图、稀疏图完全图、稠密图、稀疏图完全图、稠密图、稀疏图完全图、稠密图、稀疏图 具具有有n个个顶顶点点，n(n-1)/2条条边边的的图图，称称为为完完完完全
3、全全全无无无无向向向向图图图图，具具有有n个个顶顶点点，n(n-1)条条弧弧的的有有向向图图,称称为为完完完完全全全全有有有有向向向向图图图图。完完全全无无向向图图和完全有向图都称为和完全有向图都称为完全图完全图完全图完全图。对于一般无向图，顶点数为对于一般无向图，顶点数为n，边数为，边数为e，则，则 0e n(n-1)/2。对对于于一一般般有有向向图图，顶顶点点数数为为n，弧弧数数为为e，则则 0en(n-1)。当当一一个个图图接接近近完完全全图图时时，则则称称它它为为稠稠稠稠密密密密图图图图，相相反反地地，当当一一个图中含有较少的边或弧时，则称它为个图中含有较少的边或弧时，则称它为稀疏图稀
4、疏图稀疏图稀疏图。第4页，共193页，编辑于2022年，星期二子图：子图：对于图对于图G=(V,R),G=(V,R),若有若有V V,R R,则称图则称图G是是G的一个子图。的一个子图。下图给出了下图给出了G与其子图与其子图G。2435167图G435167图G 第5页，共193页，编辑于2022年，星期二邻接点邻接点邻接点邻接点 对对于于无无无无向向向向图图图图 G=(V,R)，如如如如果果果果边边边边(v(v，v)v)R R，则则则则称称称称顶顶顶顶点点点点v,v,vv互互互互为为为为邻邻邻邻接接接接点点点点，即即v,v相相邻邻接接。边边（v,v）依依附附于于顶顶点点v和和v，或或者者说边
5、（说边（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页，编辑于2022年，星期二权与网权与网 在在实实际际应应用用中中，图图的的边边或或弧弧上上往往往往与与具具有有
6、一一定定意意义义的的数数有有关关，即即每每一一条条边边都都有有与与它它相相关关的的数数，称称为为权权，我们将我们将这种带权的图这种带权的图叫做叫做加权图加权图或或网网，如图所示。，如图所示。第7页，共193页，编辑于2022年，星期二路径和回路路径和回路路径：路径：路径：路径：所谓顶点所谓顶点vp 到顶点到顶点vq之间的路径之间的路径,是指是指顶点序列顶点序列顶点序列顶点序列vp,vi1,vi2,vim,vq,其中（其中（vp,vi1）,（vi1,vi2）,（vim,vq）分别为图中的边。分别为图中的边。路径长度：路径长度：路径长度：路径长度：路径上边的数目路径上边的数目路径上边的数目路径上边
7、的数目称为路径长度。称为路径长度。简单路径：简单路径：简单路径：简单路径：序列中序列中顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径称为简单路径。称为简单路径。回路回路回路回路或或或或环：环：环：环：如果如果路径的起点和终点相同路径的起点和终点相同路径的起点和终点相同路径的起点和终点相同(即即vp=vq),则称此则称此路径为回路或环。路径为回路或环。第8页，共193页，编辑于2022年，星期二 如图所示的无向图中如图所示的无向图中,顶点顶点顶点顶点v1v1到顶点到顶点到顶点到顶点v5v5的路径有两条的路径有两条的路径有两条的路径有两条,分别为分别为v1,v2,
8、v3,v4与与v1,v5,v4,路径长度分别为路径长度分别为路径长度分别为路径长度分别为3 3和和和和2 2。v1到到v5的两条路径都为的两条路径都为简单简单简单简单路径路径路径路径。简单回路：简单回路：简单回路：简单回路：除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外,其它顶点不其它顶点不其它顶点不其它顶点不重复出现的回路重复出现的回路重复出现的回路重复出现的回路为为简单回路简单回路或者或者简单环简单环。第9页，共193页，编辑于2022年，星期二 连通图和强连通图连通图和强连通图连通图和强连通图连通图和强连通图 在在无向图无
9、向图无向图无向图中，若从顶点中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和顶和顶点点j是是连通的连通的。若任意两个顶点都是连通的，则称此无向图。若任意两个顶点都是连通的，则称此无向图为为连通图连通图，否则称为，否则称为非连通图非连通图。连通图和非连通图示例见图连通图和非连通图示例见图:第10页，共193页，编辑于2022年，星期二 对对于于有有有有向向向向图图图图来来说说,若若图图中中任任任任意意意意一一一一对对对对顶顶顶顶点点点点v vi i和和和和v vj j(ij)(ij)均均均均有有有有从从从从v vi i到到到到 v vj j及及及及从从从从 v vj j到到到到
10、v vi i的的的的有有有有向向向向路路路路径径径径,则则称称该该有有有有向向向向图图图图是是是是强强强强连连连连通通通通的的的的。强连通图和非强连通图示例见图强连通图和非强连通图示例见图:第11页，共193页，编辑于2022年，星期二连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量 无无无无向向向向图图图图中中，极极大大的的连连通通子子图图为为该该图图的的连连通通分分量量。显显然然，任任何何连连通通图图的的连连通通分分量量只只有有一一个个，即即它它本本身身，而而非非连连通通图图有有多多个个连通分量。连通分量。24351672435167第12页，共193页，编
11、辑于2022年，星期二 有有向向图图中中的的极极大大强强连连通通子子图图称称为为该该有有向向图图的的强强连连通通分分量量。显显然然，任任何何强强连连通通图图的的强强连连通通分分量量只只有有一一个个，即即它本身，而非强连通图有多个强连通分量。它本身，而非强连通图有多个强连通分量。下图不是强连通的下图不是强连通的,但它有两个强连通分量但它有两个强连通分量:132321第13页，共193页，编辑于2022年，星期二顶点的度顶点的度2341如：顶点如：顶点1的度为的度为3顶点的顶点的度度度度 是指是指依附于某顶点依附于某顶点依附于某顶点依附于某顶点v vi i的边数的边数的边数的边数,通常记通常记 为
12、为D(v)第14页，共193页，编辑于2022年，星期二顶点的度顶点的度132如：顶点如：顶点2的入度为的入度为2 出度为出度为1有向图有向图有向图有向图中中,要区别顶点的入度和出度的概念。要区别顶点的入度和出度的概念。顶点顶点v的的入度入度入度入度 是指是指以以以以v v为终点的弧的数目为终点的弧的数目为终点的弧的数目为终点的弧的数目记为记为ID(v)顶点顶点v的的出度出度出度出度 是指是指以以以以v v为始点的弧的数目为始点的弧的数目为始点的弧的数目为始点的弧的数目记为记为OD(v)显然：显然：D(v)=ID(v)+OD(v)第15页，共193页，编辑于2022年，星期二 7.2.1 邻接
13、矩阵存储法 7.2.2 邻接表表示法7.2 图的存储第16页，共193页，编辑于2022年，星期二图的抽象数据类型图的抽象数据类型class Graph/对象对象:由一个顶点的非空集合和一个边集合构成由一个顶点的非空集合和一个边集合构成/每条边由一对顶点来表示。每条边由一对顶点来表示。public:Graph();/建立一个空的图建立一个空的图 void InsertVertex(const T vertex);/插入一个顶点插入一个顶点vertex,该顶点暂时没有入边该顶点暂时没有入边 void InsertEdge(int v1,int v2,int weight);/在图中插入一条边在图
14、中插入一条边(v1,v2,w)void RemoveVertex(int v);/在图中删除顶点在图中删除顶点v和所有关联到它的边和所有关联到它的边 第17页，共193页，编辑于2022年，星期二 void RemoveEdge(int v1,int v2);/在图中删去边在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点若图中没有顶点,则返回则返回true,否则返回否则返回false T GetWeight(int v1,int v2);/函数返回边函数返回边(v1,v2)的权值的权值 int GetFirstNeighbor(int v);/给出顶点给出顶点 v 第一
15、个邻接顶点的位置第一个邻接顶点的位置 int GetNextNeighbor(int v,int w);/给出顶点给出顶点 v 的某邻接顶点的某邻接顶点 w 的下一个邻接顶的下一个邻接顶点点;第18页，共193页，编辑于2022年，星期二图的存储表示图的存储表示图的模板基类图的模板基类 在模板类定义中的数据类型参数表在模板类定义中的数据类型参数表 中，中，T是顶点数据的类型，是顶点数据的类型，E是边上所附数据的是边上所附数据的类型。类型。这个模板基类是按照最复杂的情况（即带权无向图）来定义的，这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要使用非带权图，可将数据类型参数表如果需
16、要使用非带权图，可将数据类型参数表 改为改为。如果使用的是有向图，也可以对程序做相应的改动。如果使用的是有向图，也可以对程序做相应的改动。第19页，共193页，编辑于2022年，星期二图的模板基类图的模板基类 const int maxWeight=0 x7fffffff;/无穷大的值(=)const int DefaultVertices=30;/最大顶点数(=n)template class Graph /图的类定义protected:int maxVertices;/图中最大顶点数 int numEdges;/当前边数 int numVertices;/当前顶点数 int GetVert
17、exPos(T vertex);/给出顶点vertex在图中位置public:第20页，共193页，编辑于2022年，星期二 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 GetWeight(i
18、nt v1,int v2);/取边上权值 virtual int GetFirstNeighbor(int v);/取顶点 v 的第一个邻接顶点第21页，共193页，编辑于2022年，星期二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(
19、int v);/删去顶点 v 和所有与相关联边 virtual bool RemoveEdge(int v1,int v2);/在图中删去边(v1,v2);第22页，共193页，编辑于2022年，星期二邻接矩阵：邻接矩阵：用一个二维数组（矩阵）来表示图中顶点之间的相邻关系。设图设图G=(V,R)有有n(n1)个顶点个顶点,则则G的邻接矩阵是按如下定的邻接矩阵是按如下定义的义的n阶方阵阶方阵:1 若若(vi,vj)或或R(G)aij=0 反之反之第23页，共193页，编辑于2022年，星期二例例:图图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页，编辑于2022年，星期二从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：（1）矩阵是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很很容容易易判判断
21、断顶顶点点i 和和顶顶点点j之之间间是是否否有有边边相相连连(看看矩矩阵阵中中i行行j列值是否为列值是否为1)。第25页，共193页，编辑于2022年，星期二从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论:（1）矩阵不一定是对称的矩阵不一定是对称的;（2）第第i 行中行中1的个数为顶点的个数为顶点i 的出度的出度;（3）第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4）矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目;（5）很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是
22、否有弧相连.第26页，共193页，编辑于2022年，星期二 网的邻接矩阵表示：网的邻接矩阵表示：若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具有个顶点的网，则它的邻接矩阵是具有如下性质的如下性质的nn矩阵矩阵A：若若或或(vi,vj)VR(G)反之反之 第27页，共193页，编辑于2022年，星期二 5 7 4 8 5 234158475例：例：例：例：一个有向网一个有向网N及其邻接矩阵的示例。及其邻接矩阵的示例。第28页，共193页，编辑于2022年，星期二 n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O O(n(n2 2)。对
23、稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：容易实现图的操作，如：求某顶点的度、判断顶点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。之间是否有边（弧）、找顶点的邻接点等等。第29页，共193页，编辑于2022年，星期二邻接矩阵表示法的邻接矩阵表示法的C+语言类型描述如下：语言类型描述如下：template class Graphmtx:public Graph private:T*VerticesList;/顶点表顶点表 E*Edge
24、;/邻接矩阵邻接矩阵int GetVertexPos(T vertex)/给出顶点给出顶点vertex在图中的位置在图中的位置 for(int i=0;i=0&i=numVertices?VerticesListi:NULL;E GetWeight(int v1,int v2)/取边取边(v1,v2)上权值上权值 return v1!=-1&v2!=-1?Edgev1v2:0;第31页，共193页，编辑于2022年，星期二 int GetFirstNeighbor(int v);/取顶点取顶点 v 的第一个邻接顶点的第一个邻接顶点 int GetNextNeighbor(int v,int w
25、);/取取 v 的邻接顶点的邻接顶点 w 的下一邻接顶点的下一邻接顶点 bool InsertVertex(const T vertex);/插入顶点插入顶点vertex 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页，编辑于2022年，星期二template Graphmtx
26、:Graphmtx(int sz)/构造函数构造函数 maxVertices=sz;numVertices=0;numEdges=0;int i,j;VerticesList=new TmaxVertices;/创建顶点表 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页，编辑于2022年，星期二te
27、mplate int Graphmtx:GetFirstNeighbor(int v)/给出顶点位置为给出顶点位置为v的第一个邻接顶点的位置的第一个邻接顶点的位置,/如果找不到如果找不到,则函数返回则函数返回-1 if(v=-1)return-1；for(int col=0;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return-1;获取第一个邻接点获取第一个邻接点第34页，共193页，编辑于2022年，星期二template int Graphmtx:getNextNeighbor(int v,int w)/
28、给出顶点给出顶点 v 的某邻接顶点的某邻接顶点 w 的下一个邻接顶点的下一个邻接顶点 if(v=-1|w=-1)return -1；for(int col=w+1;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return -1;获取下一个邻接点获取下一个邻接点第35页，共193页，编辑于2022年，星期二 邻接表邻接表（Adjacency List）表示法是图的一种链式存储）表示法是图的一种链式存储结构。它包括两个部分结构。它包括两个部分,一部分是一部分是链表链表链表链表,另一部分是另一部分是向量向量向量向量。在
29、在链表部分中共有链表部分中共有链表部分中共有链表部分中共有n n个链表个链表个链表个链表(n为顶点数为顶点数),用来存放边的信用来存放边的信息。息。将将每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中。2341第36页，共193页，编辑于2022年，星期二 这这样样，一一个个n个个顶顶点点的的图图的的邻邻接接表表表表示示由由表表头头结结点点表表与与边链表边链表两部分构成：两部分构成：(1)表头结点表：表头结点表：由所有表头结点以顺序结构（向由所有表头结点以顺序结构（向量）的形式存储量
30、）的形式存储.。表头结点的结构如图所示，由两部分构成：表头结点的结构如图所示，由两部分构成：数据域数据域（vexdata）用于存储顶点的名用于存储顶点的名(值值)；指针域（指针域（firstarc）用于指向链表中第一个顶点（即与顶点用于指向链表中第一个顶点（即与顶点vi邻接的第一个邻接的第一个邻接点）。邻接点）。vexdatavexdatafirstarcfirstarc第37页，共193页，编辑于2022年，星期二(2)边链表：边链表：由邻接点链式存储的单链表。由邻接点链式存储的单链表。单链表中每个结点由三个域组成单链表中每个结点由三个域组成:邻接点域邻接点域(adjvex)指示与顶点指示与
31、顶点vi 邻接的点在图中的位置；邻接的点在图中的位置；数据域数据域(info)存存储和边储和边(或弧或弧)相关的信息相关的信息,如权值等；如权值等；链域链域(next)指向指向顶点顶点vi 的下一个邻接点的下一个邻接点。adjvexadjvexinfoinfonextarcnextarc第38页，共193页，编辑于2022年，星期二例：例：2341第39页，共193页，编辑于2022年，星期二5423415第40页，共193页，编辑于2022年，星期二从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：（1）第
32、）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e(e为边数为边数)。第41页，共193页，编辑于2022年，星期二从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论:（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e。
33、从有向图的邻接表可知，不能求出顶点的入度。若要从有向图的邻接表可知，不能求出顶点的入度。若要求第求第i个顶点的个顶点的入度入度入度入度，必须，必须遍历整个邻接表遍历整个邻接表遍历整个邻接表遍历整个邻接表，在所有边链，在所有边链表中查找表中查找邻接点域的值为邻接点域的值为邻接点域的值为邻接点域的值为i i的结点并计数的结点并计数的结点并计数的结点并计数求和。由此可见，求和。由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，对于用邻接表方式存储的有向图，求顶点的入度并不方便，它需要通过扫描整个邻接表才能得到结果。它需要通过扫描整个邻接表才能得到结果。第42页，共193页，编辑于2022
34、年，星期二 解解决决的的方方法法：逆逆邻邻接接表表法法，对对每每一一顶顶点点vi再再建建立立一一个个逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个所所有有以以顶顶点点vi为为弧弧头头的弧的表，如图所示：的弧的表，如图所示：2341第43页，共193页，编辑于2022年，星期二邻接表的邻接表的邻接表的邻接表的缺点：缺点：缺点：缺点：邻接表的邻接表的邻接表的邻接表的优点：优点：优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。单链表，没有邻
35、接矩阵方便。第44页，共193页，编辑于2022年，星期二用邻接表表示的图的类定义用邻接表表示的图的类定义 template struct Edge /边链表结点的定义边链表结点的定义 int adjvex;/边的另一顶点位置边的另一顶点位置 E info;/边上的权值边上的权值 Edge*nextarc;/指向下一个边链表结点的指指向下一个边链表结点的指针针 Edge()/构造函数构造函数 Edge(int num,E cost=0)/构造函数构造函数 :adjvex(num),info(cost),nextarc(NULL)bool operator!=(Edge&R)const retu
36、rn dest!=R.dest;/判边等否判边等否;第45页，共193页，编辑于2022年，星期二template struct Vertex /顶点的定义顶点的定义 T vexdata;/顶点的名字顶点的名字Edge*firstarc;/边链表的头指针边链表的头指针;template class Graphlnk:public Graph /图的类定义图的类定义private:Vertex*NodeTable;/顶点表顶点表(各边链表的头结点各边链表的头结点)第46页，共193页，编辑于2022年，星期二int GetVertexPos(const T vertx)/给出顶点给出顶点vert
37、ex在图中的位置在图中的位置 for(int i=0;i=0&i NumVertices)?NodeTablei.vexdata:0;bool InsertVertex(const T&vertex);bool 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页，编辑于2022年，星期二template Graphlnk:Gra
38、phlnk(int sz)/构造函数：建立一个空的邻接表构造函数：建立一个空的邻接表 maxVertices=sz;NodeTable=new VertexmaxVertices;/创建顶点表数组创建顶点表数组 assert(NodeTable);numVertices=0;numEdges=0;for(int i=0;i maxVertices;i+)NodeTablei.firstarc=NULL;第49页，共193页，编辑于2022年，星期二template Graphlnk:Graphlnk()/析构函数：删除一个邻接表析构函数：删除一个邻接表 for(int i=0;i numVer
39、tices;i+)Edge*p=NodeTablei.firstarc;while(p!=NULL)NodeTablei.firstarc=p-next;delete p;p=NodeTablei.firstarc;delete NodeTable;/删除顶点表数组删除顶点表数组;边链表边链表(单链单链表表)的析构的析构第50页，共193页，编辑于2022年，星期二获取第一个邻接点获取第一个邻接点template int Graphlnk:GetFirstNeighbor(int v)/给出顶点位置为给出顶点位置为 v 的第一个邻接顶点的位置的第一个邻接顶点的位置,/如果找不到如果找不到,则函
40、数返回则函数返回-1 if(v=-1)return -1;/顶点顶点v不存在不存在 Edge*p=NodeTablev.firstarc;/对应边链表对应边链表第一个边结点第一个边结点if(p!=NULL)return p-adjvex;/存在存在,返回第返回第一个邻接顶点一个邻接顶点 return -1;/第一个邻接顶点不存在第一个邻接顶点不存在;第51页，共193页，编辑于2022年，星期二获取下一个邻接点获取下一个邻接点template int Graphlnk:GetNextNeighbor(int v,int w)/给出顶点给出顶点v的邻接顶点的邻接顶点w的下一个邻接顶点的位置的下一
41、个邻接顶点的位置,/若没有下一个邻接顶点若没有下一个邻接顶点,则函数返回则函数返回-1 if(v!=-1)/顶点顶点v存在存在 Edge*p=NodeTablev.firstarc;while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p!=NULL&p-nextarc!=NULL)return p-nextarc-adjvex;/返回下一个邻接顶点返回下一个邻接顶点 return-1;/下一邻接顶点不存在下一邻接顶点不存在;第52页，共193页，编辑于2022年，星期二讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩
42、阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.1.1.联系：联系：联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，链表邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。中结点个数等于一行中非零元素的个数。2.2.2.2.区别：区别：区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度而邻接表的空间复
43、杂度为为O(n+e)。第53页，共193页，编辑于2022年，星期二分析分析分析分析:在图的链接存储在图的链接存储(邻接表、逆邻接表邻接表、逆邻接表)中，表头向量中，表头向量需要占用需要占用n个存储单元，所有边结点需要占用个存储单元，所有边结点需要占用2e或或e存储存储单元，所以最多需要（单元，所以最多需要（n+2e）个存储单元，稀疏图采用）个存储单元，稀疏图采用这种存储方式可节省存储空间。这种存储方式可节省存储空间。第54页，共193页，编辑于2022年，星期二图图的的遍遍历历：沿沿着着某某条条搜搜索索路路径径对对图图中中所所有有顶顶点点各作一次访问。各作一次访问。图图的的遍遍历历比比起起树
44、树的的遍遍历历要要复复杂杂得得多多。图图中中顶顶点点关关系系是是多多对对多多的的关关系系，图图可可能能是是非非连连通通图图，图图中中还还可可能能有有回回路路存存在在，因因此此在在访访问问了了某某个个顶顶点点后后，可可能能沿沿着着某某条路径搜索后又回到该顶点上。条路径搜索后又回到该顶点上。为为了了保保证证图图中中的的各各顶顶点点在在遍遍历历过过程程中中访访问问且且仅仅访访问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志。图的遍历图的遍历第55页，共193页，编辑于2022年，星期二 为为此此 我我们们设设置置一一个个访访问问标标志志数数组组visitedn，用用于于标标示
45、示图图中中每每个个顶顶点点是是否否被被访访问问过过，它它的的初初始始值值为为0(“假假”)，表表示示顶顶点点均均未未被被访访问问；一一旦旦访访问问过过顶顶点点vi，则则置置访访问问标标志志数数组组中中的的visitedi为为1(“真真”)，以以表表示示该该顶顶点点已访问。已访问。根据搜索路径的不同，图的遍历又分：根据搜索路径的不同，图的遍历又分：深度优先搜索遍历深度优先搜索遍历 广度优先搜索遍历广度优先搜索遍历第56页，共193页，编辑于2022年，星期二 7.3.1 深度优先搜索遍历 7.3.2 广度优先搜索遍历 7.3 图的遍历第57页，共193页，编辑于2022年，星期二 深深度度优优先
46、先搜搜索索（Depth-First Search）是是指指按按照照深深度度方方向向搜搜索索，它它类类似似于于树树的的先先根根遍遍历历，是是树树的的先先根根遍遍历历的推广。的推广。特点：特点：尽可能先对纵深方向进行搜索。尽可能先对纵深方向进行搜索。算法描述：算法描述：从某个顶点从某个顶点v0出发，进行出发，进行dfs的算法描述如下：的算法描述如下：(1)访问访问v0。(2)依次从依次从v0的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历第58页，共193页，编辑于2022年，星期二BAGDCFHEI 下图给出了一个深度优先搜索的过程图示，其中下图给出了一个深度优先搜索的过程图示，
47、其中实箭头实箭头实箭头实箭头代表访问方向，虚箭头代表回溯方向代表访问方向，虚箭头代表回溯方向代表访问方向，虚箭头代表回溯方向代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表，箭头旁边的数字代表搜索顺序，搜索顺序，A A为起始顶点为起始顶点为起始顶点为起始顶点。BAGDCFHEI遍历过程遍历过程深度优先生成树深度优先生成树第59页，共193页，编辑于2022年，星期二 若若若若图图图图是是是是连连连连通通通通的的的的或或或或强强强强连连连连通通通通的的的的，则则从从图图中中某某一一个个顶顶点点出出发发可以访问到图中所有顶点，否则只能访问到一部分顶点。可以访问到图中所有顶点，否则只能访问到一部
48、分顶点。另外，从刚才写出的遍历结果可以看出，从某一另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是个顶点出发的遍历结果是不唯一的。但是,若我们给定若我们给定图的存储结构图的存储结构,则从某一顶点出发的遍历结果应是唯一则从某一顶点出发的遍历结果应是唯一的。的。分析与总结：分析与总结：分析与总结：分析与总结：第60页，共193页，编辑于2022年，星期二分析连通图的深度遍历算法的实现分析连通图的深度遍历算法的实现:(1)为为防防止止重重复复访访问问顶顶点点，需需为为每每个个顶顶点点设设置置一一个个访访问问标标志志 visitedi，其其值值为为 0 时时，表表示示顶顶
49、点点 i 未未被被访访问问过；值为过；值为 1 时，表示顶点时，表示顶点 i 已被访问过。已被访问过。(2)算算法法中中需需依依次次找找v0的的各各邻邻接接点点，可可根根据据不不同同的的存存储结构具体实现。储结构具体实现。第61页，共193页，编辑于2022年，星期二访问 v0置访问标志visitedv0=1w=GetFirstNeighbor(v0)w=0 w 已被访问过dfs(w)w=GetNextNeighbor(v0,w)NNYY结束结束第62页，共193页，编辑于2022年，星期二图的深度优先搜索算法图的深度优先搜索算法template void DFS(Graph G,const
50、T v)/从顶点从顶点v出发对图出发对图G进行深度优先遍历的主过程进行深度优先遍历的主过程 int i,loc,n=G.NumberOfVertices();/顶点个数顶点个数 bool*visited=new booln;/创建辅助数组创建辅助数组 for(i=0;i n;i+)visited i=false;/辅助数组辅助数组visited初始化初始化loc=G.GetVertexPos(v);DFS(G,loc,visited);/从顶点从顶点0开始深度优先搜索开始深度优先搜索 delete visited;/释放释放visited;第63页，共193页，编辑于2022年，星期二temp