数据结构第07章图.ppt

《数据结构第07章图.ppt》由会员分享，可在线阅读，更多相关《数据结构第07章图.ppt（251页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本章介绍另一种非线性数据结构 图 图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继；第七章第七章 图图 7.1 图的概念图的概念 7.2 图的存储结构图的存储结构 7.3 图的遍历图的遍历 7.4 生成树生成树 7.5 最短路径最短路径 7.6 拓扑排序拓扑排序第七第七 章章 图图学习要点学习要点1熟悉图的各种存储结构及其构造算法，了解熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密实际问题的求解效率与采用何种存储结构和算法有密切联系；切联系；2熟练掌握图的两种遍历：深度优先遍历和广熟练掌握图的两种遍历：深度优先遍历和广度优先

2、遍历的算法。在学习中应注意图的遍历算法与度优先遍历的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略搜索策略3理解各种图的算法；理解各种图的算法；7.1 7.1 图的概念图的概念 一一 图的概念图的概念 二二 图的应用图的应用 三三 图的基本术语图的基本术语第七第七 章章 图图7.1 7.1 图的基本概念图的基本概念一一 图的概念图的概念 图的定义图的定义 图图G G由两个集合构成，记作由两个集合构成，记作G=G=其中

3、其中V V是顶点的非空有是顶点的非空有限集合，限集合，E E是边的有限集合，其中边是顶点的是边的有限集合，其中边是顶点的无序对无序对或或有序对有序对集集合。合。G1G1=V V=v=v0 0,v,v1 1,v,v2 2,v,v3 3,v,v4 4 E E=(v=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v,v4 4)G1G1图示图示无序对无序对(v(vi i,v,vj j)：用连接顶点用连接顶点v vi i、v vj j的线段的线段表示，称为无向边；

4、表示，称为无向边；例例 V0V0 V4V4 V3V3 V1V1 V2V2G2 G2 图示图示有序对有序对v ：用以用以v vi i起点、以起点、以v vj j为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；称边或弧；称vivi为弧尾，为弧尾，vjvj为弧头为弧头无向图无向图：在图在图G G中，若所有边是无向边，则称中，若所有边是无向边，则称G G为无向图；为无向图；有向图有向图：在图：在图G G中，若所有边是有向边，则称中，若所有边是有向边，则称G G为有向图；为有向图；混和图混和图：在图：在图G G中，既有无向边也有有向边，则称中，既有无向边也有有向边，则称G G为混合图

5、；为混合图；7.1 7.1 图的基本概念图的基本概念 V0V0 V1V1 V2V2 V3V3G2G2=V V=v=v0 0 v v1 1,v,v2 2,v,v3 3 E E=v=,v,二二图的应用举例图的应用举例三三例例1 1 交通图（公路、铁路）交通图（公路、铁路）顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示交通图中的有单行道双行道，分别用有向边、无向边表示；例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地

6、点间的连线例例4 4 各种流程图各种流程图 如如产品的生产流程图产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系7.1 7.1 图的基本概念图的基本概念 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V31 1 邻接点及关联边邻接点及关联边 邻接点：边的两个顶点邻接点：边的两个顶点,v,v、u u互为邻接点互为邻接点 关联边：若边关联边：若边e=(v,u),则称顶点则称顶点v、u 关联边关联边e2 2 顶点的度、入度、出度顶点的度、入度、出度 在无向图中：在无向图中：顶点顶点V的度的度=与与V相关联的边的数目相关

7、联的边的数目 在有向图中：在有向图中：顶点顶点V的出度的出度=以以V为起点有向边数为起点有向边数 顶点顶点V的入度的入度=以以V为终点有向边数为终点有向边数 顶点顶点V的度的度=V的出度的出度+V的入度的入度 设图设图G G的顶点数为的顶点数为n，边数为，边数为e 图的所有顶点的度数和图的所有顶点的度数和=2*e （每条边对图的所有顶点的度数和（每条边对图的所有顶点的度数和“贡献贡献”2度）度）e e三三图的基本术语图的基本术语7.1 7.1 图的基本概念图的基本概念 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V33 3完全图、权、网完全图、权、网 有

8、向完全图有向完全图具有具有n(n-1)条弧的条弧的n个顶点的有向图称为个顶点的有向图称为 无向完全图无向完全图有有n(n-1)/2 条边的条边的n个顶点的个顶点的无向图称为无向图称为 权权与图的边或弧相关的数叫与图的边或弧相关的数叫 网网带权的图叫带权的图叫例213213有向完全图无向完全图例14523753186427.1 7.1 图的基本概念图的基本概念 4 4 路径、回路路径、回路 路径路径路径是顶点的序列路径是顶点的序列V=Vi0,Vi1,Vin，满足满足(Vij-1,Vij)E 或 E,(1jn)路径长度路径长度沿路径边的数目或沿路径各边权值之和沿路径边的数目或沿路径各边权值之和 回

9、路回路第一个顶点和最后一个顶点相同的路径叫第一个顶点和最后一个顶点相同的路径叫 在在图图G1G1中，中，V V0 0,V,V1 1,V,V2 2,V,V3 3 是是V V0 0到到V V3 3的路径；的路径；V V0 0,V,V1 1,V,V2 2,V,V3 3,V,V0 0是回路；是回路；在在图图G2G2中，中，V V0 0,V,V2 2,V,V3 3 是是V V0 0到到V V3 3的路径；的路径；V V0 0,V,V2 2,V,V3 3,V,V0 0是回路；是回路；无向图无向图G1G1有向图有向图G2例例7.1 7.1 图的基本概念图的基本概念 V V0 0 V V4 4 V V3 3

10、V V1 1 V V2 2 V V0 0 V V1 1 V V2 2 V V3 3 5 5 简单路径和简单回路简单路径和简单回路 在一条路径中在一条路径中,序列中顶点不重复出现的路径称为序列中顶点不重复出现的路径称为简单路径；简单路径；由简单路径组成的回路称为简单回路；由简单路径组成的回路称为简单回路；在在图图G1G1中，中，V0,V1,V2,V3 V0,V1,V2,V3 是简单路径；是简单路径；在在图图G2G2中，中，V0,V2,V3,V0 V0,V2,V3,V0是简单回路；是简单回路；无向图无向图G1G1有向图有向图G2例例7.1 7.1 图的基本概念图的基本概念 V0V0 V4V4 V3

11、V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V36 6 连通图（强连通图）连通图（强连通图）在无（有）向图在无（有）向图G=中，若对任何两个顶点中，若对任何两个顶点 v、u 都存在从都存在从v 到到 u 的路径，则称的路径，则称G是连通图（强连通图）是连通图（强连通图）7.1 7.1 图的基本概念图的基本概念 非非连连通通图图 连连通通图图 强强连连通通图图 非非强强连连通通图图 V0V0 V1V1 V2V2 V3V3 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V1 V5V5 V4V47子图子图设

12、有两个图设有两个图G=（V，E）、）、G1=（V1，E1），若），若V1 V，E1 E，则称，则称G1是是G的子图；的子图；例例(b)、(c)是是(a)的子图的子图(a)(a)(b)(b)(c)(c)7.1 7.1 图的基本概念图的基本概念 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V28连通分量（强连通分量连通分量（强连通分量）无向图无向图G的极大连通子图称为的极大连通子图称为G的连通分量的连通分量极大连通子图意思是：该子图是极大连通子图意思是：该子图是G连通子图，将连通子图，将G的任何不的

13、任何不在该子图中的顶点加入，子图不再连通；在该子图中的顶点加入，子图不再连通；连通分量连通分量非非连连通通图图7.1 7.1 图的基本概念图的基本概念 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4有向图有向图D的极大强连通子图称为的极大强连通子图称为D的强连通分量的强连通分量极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是D强连通子图，将强连通子图，将D的任何的任何不在该子图中的顶点加入，子图不再是强连通的；不在该子图中的顶点加入，子图不再是强连通的；强连通分量强连通分量 V0V0 V1V1 V2V2 V3V3 V0V0 V2V2 V3V3 V1V19生成树生成树包含

14、无向图包含无向图G所有顶点的的极小连通子图称为所有顶点的的极小连通子图称为G的生成树的生成树极小连通子图意思是：该子图是极小连通子图意思是：该子图是G的连通子图，在该子图的连通子图，在该子图中删除任何一条边，子图不再连通，中删除任何一条边，子图不再连通，若若T是是G的生成树当且仅当的生成树当且仅当T满足如下条件满足如下条件T是是G的连通子图的连通子图T包含包含G的所有顶点的所有顶点T中无回路中无回路连通图连通图 G1 G1G1G1的生成树的生成树7.1 7.1 图的基本概念图的基本概念 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0

15、 V4V4 V3V3 V1V1 V2V2T1T1是是G1G1的生成树的生成树例245136G1图G1中：V(G1)=1,2,3,4,5,6 E(G1)=,例157324G26图G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)例213213有向完全图无向完全图例245136G1顶点2入度：出度：顶点4入度：出度：例157324G26顶点5的度：顶点2的度：341310例157324G26例245136G1路径：1，2，3，5，6，3路径长度：简单路径：1，2，3，5，6，3，1 3，5，6，3路径：1，

16、2，5，7，6，5，2，3路径长度：7简单路径：回路：简单回路：51，2，3，5，6回路：简单回路：1，2，5，7，61，2，3，11，2，5，7，6，5，2，1连通图例245136强连通图356例非连通图连通分量例245136356例245136图与子图7.2 图的存储结构图的存储结构多重链表多重链表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3邻接矩阵邻接矩阵表示顶点间相联关系的矩阵表示顶点间相联关系的矩阵v定义：设定义：设G=(V,E)是有是有n1个顶点的图，个顶点的图，G的邻接矩阵的邻接矩阵A是是具有以下性质的具有以下性质的n阶方阵阶方阵例G12413

17、例15324G2数组表示法数组表示法 如何表示顶点间的关系如何表示顶点间的关系？v特点：特点：l无向图的邻接矩阵对称，可压缩存储；有无向图的邻接矩阵对称，可压缩存储；有n n个顶点个顶点的无向图需存储空间为的无向图需存储空间为n(n+1)/2n(n+1)/2l有向图邻接矩阵不一定对称；有有向图邻接矩阵不一定对称；有n n个顶点的有向图个顶点的有向图需存储空间为需存储空间为nnl无向图中顶点无向图中顶点ViVi的度的度TD(Vi)TD(Vi)是邻接矩阵是邻接矩阵A A中第中第i i行行(或第或第i i列列)元素之和元素之和l有向图中，有向图中，u顶点顶点ViVi的出度是的出度是A A中第中第i

18、i行元素之和行元素之和u顶点顶点ViVi的入度是的入度是A A中第中第i i列元素之和列元素之和例G12413例15324G2如何判断邻接否、如何判断邻接否、增删边？增删边？l 检测图中的总边数。扫描整个数组检测图中的总边数。扫描整个数组A A，统计出数，统计出数组中非组中非0 0元素的个数。无向图的总边数为非元素的个数。无向图的总边数为非0 0元素元素个数的一半，而有向图的总弧数为非个数的一半，而有向图的总弧数为非0 0元素个数；元素个数；l网的邻接矩阵可定义为：网的邻接矩阵可定义为：Aij=Aij=w wijij 若若(v(vi i,v,vj j)或或v E(G)E(G)若若(v(vi i

19、,v,vj j)或或v E(G)E(G)其中其中 w wijij表示表示(v(vi i,v,vj j)边上的权值；边上的权值；表示结点表示结点v vi i和和v vj j之间没有边相连。之间没有边相连。若若G G是一个带权值的图，即为网络，则其邻接是一个带权值的图，即为网络，则其邻接矩阵可定义为：矩阵可定义为：例1452375318642带权有向图的邻接矩阵带权有向图的邻接矩阵带权无向图的邻接矩阵带权无向图的邻接矩阵v邻接矩阵表示法中图的存储表示邻接矩阵表示法中图的存储表示#definen6/*图的顶点数图的顶点数*/#definee8/*图的边数图的边数*/typedefcharvextyp

20、e;/*顶点的数据类型顶点的数据类型*/typedeffloatadjtype;/*权值类型权值类型*/typedefstructvextypevexsn;adjtypearcsnn;graph;21435BADCE215340=807080705040503040203020arcs6203050407080邻接矩阵表示法中无向网络的建立算法邻接矩阵表示法中无向网络的建立算法CREATEGRAPH(graph*ga)inti,j,k;floatw;for(i=0;ivexsigetchar();/*读入顶点信息，建立顶点表读入顶点信息，建立顶点表*/for(i=0;in;i+)for(j=0

21、;jarcsij0;/*邻接矩阵初始化邻接矩阵初始化*/for(k=0;karcsijw;ga-arcsjiw;例1452375318642容易实现图的操作，如：求某顶点的容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。顶点的邻接点等等。n个顶点需要个顶点需要n*n个单元存储边个单元存储边(弧弧);空间效率为空间效率为O(n2)。对稀疏图而言尤对稀疏图而言尤其浪费空间。其浪费空间。邻接矩阵法优点：邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵法缺点：注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#de

22、fineINFINITYINT_MAX/最大值最大值#defineMAX_VERTEX_NUM20/假设的最大顶点数假设的最大顶点数typedefenumDG,DN,AG,ANGraphKind;/有向有向/无向图，有向无向图，有向/无向网无向网typedefstructArcCell/弧（边）弧（边）结点的定义结点的定义VRTypeadj;/顶点间关系，无权图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型InfoType*info;/该弧相关信息的指针该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;ty

23、pedefstruct/图的定义图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点表，用一维向量即可顶点表，用一维向量即可AdjMatrixarcs;/邻接矩阵邻接矩阵intVernum,arcnum;/顶点总数，弧（边）总数顶点总数，弧（边）总数GraphKindkind;/图的种类标志图的种类标志Mgraph;图的邻接矩阵存储表示（参见教材图的邻接矩阵存储表示（参见教材P161P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2)StatusCreateUDN(Mgraph&G)/无向网的构造，用邻接矩阵表示无向网的构造，用邻

24、接矩阵表示scanf(&G.vexnum,&G.arcnum,&IncInfo);/输入总顶点数，总弧数和信息输入总顶点数，总弧数和信息for(i=0;iG.vexnum,;+i)scanf(&G.vexsi);/输入顶点值，存入一维向量中输入顶点值，存入一维向量中for(i=0;iG.vexnum;+i)/对邻接矩阵对邻接矩阵n*nn*n个单元初始化，个单元初始化，adj=,info=NULLfor(j=0;jG.vexnum;+j)G.arcsij=INFINITY,NULL;for(k=0;kG.arcnum;+k)/给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值(循环次数弧数循环次数

25、弧数scanf(&v1,&v2,&w);/输入弧的两顶点以及对应权值输入弧的两顶点以及对应权值i=LocateVex(G,v1);j=LocateVex(G,v2);/找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n(n次次?G.arcsij.adj=w;/输入对应权值输入对应权值If(IncInfo)Input(*G.arcsij.info);/如果弧有信息则填入如果弧有信息则填入G.arcsij=G.arcsji；/无向网是对称矩阵无向网是对称矩阵returnOK;/CreateUDN CreateUDN 例：例：用邻接矩阵生成无向网的算法用邻接矩阵生成无向网的算法（参见教材（参见教材

26、P162P162）对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率=O(n=O(n2 2+n+e*n)+n+e*n)v 邻接表邻接表 (Adjacency List)(Adjacency List)在邻接表中，对图中每个顶点建立一个单在邻接表中，对图中每个顶点建立一个单链表，第链表，第i i个单链表中的结点表示依附于顶点个单链表中的结点表示依附于顶点v vi i的边。每个结点由三个域组成：的边。每个结点由三个域组成：adjvexadjvex nextarcnextarc infoinfo邻接点域邻接点域指示与顶点指示与顶点v vi i邻接邻接的点在图中的位置的点在图

27、中的位置链域链域指示下一条边指示下一条边或弧的结点或弧的结点数据域数据域存储与边或弧存储与边或弧相关的信息，相关的信息，如权值，如权值，无权无权图一般不用图一般不用每个单链表附设一个头结点。每个单链表附设一个头结点。在表头结点中，除了在表头结点中，除了在表头结点中，除了在表头结点中，除了设有链域指向链表中第一个结点之外，还设有存储设有链域指向链表中第一个结点之外，还设有存储设有链域指向链表中第一个结点之外，还设有存储设有链域指向链表中第一个结点之外，还设有存储顶点顶点顶点顶点v v v vi i i i的名或其它有关信息的数据域。的名或其它有关信息的数据域。的名或其它有关信息的数据域。的名或其

28、它有关信息的数据域。datadata firstarcfirstarc数据域数据域链域链域 表头结点可以链相接，通常以顺序结构的表头结点可以链相接，通常以顺序结构的形式存储，以便随机访问任一顶点的链表。形式存储，以便随机访问任一顶点的链表。存放与该顶点存放与该顶点相关的信息相关的信息指示第一条依附于指示第一条依附于该顶点的边的指针该顶点的边的指针图的邻接表存储表示图的邻接表存储表示#defineMAX_VERTEX_NUM20typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针

29、指向下一条弧的指针InfoType*info;/该弧相关信息的指针该弧相关信息的指针ArcNode;typedefstructVNodeVertexTypedata;/顶点信息顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数intkind;/图的种类标志图的种类标志ALGraph;n n无向图的邻接表无向图的邻接表 在无向图的邻接表中，顶点在无向图的邻接表中，顶点

30、v vi i的度恰为第的度恰为第i i个个链表中的结点数。链表中的结点数。datadatafirstarcfirstarcadjvexadjvexnextarcnextarcn n有向图的邻接表有向图的邻接表(出边表出边表)datadatafirstarcfirstarcadjvexadjvexnextarcnextarc有向图中对每个结点建立以有向图中对每个结点建立以ViVi为为尾尾的弧的单链表的弧的单链表顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为以同一顶点为起点起点的弧：用线性链表存储的弧：用线性链表存储n n有向图的逆邻接表有向图的逆邻接表(入边表入

31、边表)datadatafirstarcfirstarcadjvexadjvexnextarcnextarc有向图中对每个结点建立以有向图中对每个结点建立以ViVi为为头头的弧的单链表的弧的单链表顶点：用一维数组存储（按编号顺序）顶点：用一维数组存储（按编号顺序）以同一顶点为以同一顶点为终点终点的弧：用线性链表存储的弧：用线性链表存储n在有向图中，第在有向图中，第i个链表中的结点个数只是个链表中的结点个数只是顶点顶点vi的出度，为求入度，必须遍历整个邻接的出度，为求入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为表。在所有链表中其邻接点域的值为i的结点的结点的个数是顶点的个数是顶点vi的入

32、度。的入度。n在有向图的邻接表中，第在有向图的邻接表中，第i个边链表链接个边链表链接的边都是的边都是顶点顶点i发出的边发出的边。也叫做。也叫做出边表出边表。n在有向图的逆邻接表中，第在有向图的逆邻接表中，第i个边链表链个边链表链接的边都是接的边都是进入顶点进入顶点i的边的边。也叫做。也叫做入边表入边表。例aecbdG2 2 4 2 1adjvex next1234acdbdatafirstarc5e 4 3 5 1 5 3 2 3该结点表示边该结点表示边（Vi VjVi Vj）,其中的其中的2 2是是VjVj在一维数组中的位置在一维数组中的位置例G1bdac1234acdbvexdata fi

33、rstarc 3 4 1 2adjvex next邻接表邻接表v特点l无向图中顶点无向图中顶点Vi的度为第的度为第i个单链表中的结点数个单链表中的结点数l有向图有向图中中u顶点顶点Vi的的出度出度为第为第i个单链表中的结点个数个单链表中的结点个数u顶点顶点Vi的的入度入度为整个为整个单链表中邻接点域值是单链表中邻接点域值是i的结点个数的结点个数l判定两顶点判定两顶点v,u是否邻接：要看是否邻接：要看v对应线性链表中有无对应的对应线性链表中有无对应的结点结点ul在在G中增减边：要在两个单链表插入、删除结点；中增减边：要在两个单链表插入、删除结点；l若无向图中有若无向图中有n n个顶点、个顶点、e

34、 e条边，则它的邻接表需条边，则它的邻接表需n n个头结点和个头结点和2e2e个表结点。可见，个表结点。可见，G占用存储空间与占用存储空间与G的顶点数、边数均有关；的顶点数、边数均有关；适用于边稀疏的图。适用于边稀疏的图。例aecbdG21234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3带权图的邻接表带权图的邻接表多一个多一个info域域相反，相反，已知某网的邻接（出边）表，可以画出该网络。已知某网的邻接（出边）表，可以画出该网络。8064125当邻接表当邻接表的存储结的存储结构形成后，构形成后，图便唯一图便唯一确定！确定

35、！邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵两结点对应的单链表，没有邻接矩阵方便。方便。讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的

36、无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3.3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（enen2 2)三、三、十字链表十字链表（自学）（自学）（适用于有向图）适用于有向图）四、四、邻接多重表邻接多重表（自学

37、）（自学）（适用于无向图）（适用于无向图）有向图有向图的十字链表表示法的十字链表表示法弧结点：typedef struct arcnode int tailvex,headvex;/弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧 struct arcnode *tlink;/指向弧尾相同的下一条弧AD;tailvex headvex hlink tlink顶点结点：typedef struct dnode int data;/存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点 struct ar

38、cnode *firstout;/指向以该顶点为弧尾的第一个弧结点DD;DD gM;/g0不用data firstin firstout例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1无向图无向图的邻接多重表表示法的邻接多重表表示法顶点结点：typedef struct dnode int data;/存与顶点有关的信息 struct node *firstedge;/指向第一条依附于该顶点的边DD;DD gaM;/ga0不用data firstedge边结点：typedef struct node int mark;/标志域 int ivex,jvex;/

39、该边依附的两个顶点在表头数组中位置 struct node *ilink,*jlink;/分别指向依附于ivex和jvex的下一条边JD;mark ivex ilink jvex jlink例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2 7.3 7.3 图的图的遍历遍历 从图中某个顶点出发游历图，访遍图中其余从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次。这顶点，并且使图中的每个顶点仅被访问一次。这一过程就称为一过程就称为图的遍历图的遍历。图的遍历比树的遍历要复杂得多。因为图的图的遍历比树的遍历要复杂得多。因为图的任一顶点都可能和

40、其余的顶点相邻接；因此在访任一顶点都可能和其余的顶点相邻接；因此在访问了某个顶点后，可能沿着某条路径搜索后，又问了某个顶点后，可能沿着某条路径搜索后，又回到该顶点上。回到该顶点上。为了避免同一顶点被访问多次，在遍历图的为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。过程中，必须记下每个已访问过的顶点。为了避免重复访问，可设置一个标志顶点为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组是否被访问过的辅助数组visited0.n-1，它，它的初始状态为的初始状态为0，在图的遍历过程中，一旦某，在图的遍历过程中，一旦某一个顶点一个顶点i 被访问，就立即让被访问，就

41、立即让visitedi为为1，防止它被多次访问。，防止它被多次访问。通常有两条遍历图的路径：通常有两条遍历图的路径：深度优先搜索深度优先搜索 、广度优先搜索、广度优先搜索q 深深 度度 优优 先先 搜搜 索索 DFS(Depth_FirstSearch)算法思想：算法思想：假设初始状态是图中所有顶点未曾被访问，假设初始状态是图中所有顶点未曾被访问，则可从图中某个顶点则可从图中某个顶点V0出发，访问此顶点，出发，访问此顶点，然后然后依次从依次从V0的各个未被访问的邻接点出发深的各个未被访问的邻接点出发深度优先搜索遍历图度优先搜索遍历图，直至图中所有和，直至图中所有和V0有路径有路径相通的顶点都被

42、访问到，若此时图中尚有顶点相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。都被访问到为止。图的深度优先搜索类似于树的前序遍历图的深度优先搜索类似于树的前序遍历V V1 1V V8 8V V2 2V V3 3V V6 6V V7 7V V4 4V V5 5无向图无向图G G1 1v 深度优先搜索的示例深度优先搜索的示例V V1 1V V2 2V V3 3V V4 4V V5 5V V7 7V V6 6V V8 80 01 12 2

43、3 34 45 56 67 7 1 12 20 04 40 01 17 71 17 72 25 53 34 42 26 63 3 6 65 5G G1 1的的邻接表邻接表由上得到顶点访问序列为：由上得到顶点访问序列为：v v1 1、v v2 2、v v4 4、v v8 8、v v5 5、v v3 3、v v6 6、v v7 7 显然这是一个递归的过程，为了在遍历过显然这是一个递归的过程，为了在遍历过程中便于区分顶点是否已被访问，需附设访问程中便于区分顶点是否已被访问，需附设访问数组数组visited0.n-1，数组元素的初始值为，数组元素的初始值为false；在遍历过程中，一旦某一个顶点；在遍

44、历过程中，一旦某一个顶点i 被被访问，则置访问，则置visitedi为为 true。例例例例2 2 2 2：v2v1v3v5v2v1v3v5DFSDFS结果结果结果结果v4v4 v6v6起点起点深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点v 后，由后，由v 出发，访问出发，访问它的任一邻接顶点它的任一邻接顶点w1；E再从再从w1出发，访问出发，访问与与w1邻接邻接但还但还未被访问未被访问过的过的顶点顶点w2；E然后再从然后再从w2出发，进行类似的访问，出发，进行类似的访问，E如此进行下去，直至到达所有的邻接顶点都被访如此

45、进行下去，直至到达所有的邻接顶点都被访问过的顶点问过的顶点u 为止。为止。简单归纳：简单归纳：访问起始点访问起始点v;若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重个邻接点重新遍历。新遍历。E接着，接着，退回一步，退到前一次刚访问过的顶点，退回一步，退到前一次刚访问过的顶点，看是否看是否还有其它没有被访问的邻接顶点。还有其它没有被访问的邻接顶点。E如果有，如果有，则访问此顶点，之后再从此顶点出发，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；进行与前述类似的访问；E如果

46、没有如果没有，就，就再退回一步再退回一步进行搜索。重复上述过进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。程，直到连通图中所有顶点都被访问过为止。BooleanvisitedMAX;BooleanvisitedMAX;/访问标访问标志数组志数组StatusStatus(*VisitFunc)(intv);(*VisitFunc)(intv);/函函数变量数变量/以上两个变量都是全局变量以上两个变量都是全局变量voidvoidDFSTraverse(GraphG,Status(*Visit)(intDFSTraverse(GraphG,Status(*Visit)(intv)v)/

47、对图对图G G作深度优先遍历。作深度优先遍历。VisitFunc=Visit;VisitFunc=Visit;for(v=0;vG.vexnum;+v)for(v=0;vG.vexnum;+v)visitedv=FALSE;visitedv=FALSE;/访问标志数组初始化访问标志数组初始化forfor(v=0;vG.vexnum;+v)(v=0;vG.vexnum;+v)if(!visitedv)if(!visitedv)DFS(G,v);DFS(G,v);/对尚未访问的对尚未访问的顶点调用顶点调用DFSDFS v 图的深度优先搜索算法图的深度优先搜索算法voidDFS(GraphG,int

48、v)voidDFS(GraphG,intv)/从第从第v v个顶点出发递归地深度优先遍历图个顶点出发递归地深度优先遍历图G G。visitedv=visitedv=TRUE;TRUE;/访问标记置为访问标记置为truetrueVisitFunc(v);VisitFunc(v);/访问第访问第v v个顶点个顶点forfor(w=FirstAdjVex(G,v);(w=FirstAdjVex(G,v);w!=0;w!=0;w=NextAdjVex(G,v,w)w=NextAdjVex(G,v,w)if(!visitedw)if(!visitedw)DFS(G,w);/DFS(G,w);/对对v v

49、的尚未访的尚未访问的邻接顶点问的邻接顶点w w/递归调用递归调用DFSDFS v 算法时间复杂度分析算法时间复杂度分析 从上述算法可知，在遍历过程中，对图中从上述算法可知，在遍历过程中，对图中每个顶点至多调用一次每个顶点至多调用一次DFSDFS函数；因为一旦某个函数；因为一旦某个顶点被标志成已被访问，就不再从它出发进行顶点被标志成已被访问，就不再从它出发进行搜索。搜索。因此，因此，对图的遍历实际上是对图的遍历实际上是对每个顶点查对每个顶点查找其邻接点的过程，耗费的时间取决于所用的找其邻接点的过程，耗费的时间取决于所用的存储结构。存储结构。如果用如果用邻接表邻接表表示图，沿表示图，沿 First

50、out link 链可以找到某个顶点链可以找到某个顶点v 的所有邻接顶点的所有邻接顶点w。由于。由于总共有总共有2e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问而且对所有顶点递归访问1次，所以遍历图的时次，所以遍历图的时间复杂性为间复杂性为O(n+e)。如果用如果用邻接矩阵邻接矩阵表示图，则查找每一个顶表示图，则查找每一个顶点的所有的边，所需时间为点的所有的边，所需时间为O(n)，则遍历图中，则遍历图中所有的顶点所需的时间为所有的顶点所需的时间为O(n2)。q 广广 度度 优优 先先 搜搜 索索 BFS(Breadth_FirstSearch)图的