图 图的基本概念.pptx

《图 图的基本概念.pptx》由会员分享，可在线阅读，更多相关《图 图的基本概念.pptx（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、8.1图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：合组成的一种数据结构，它可以形式化地表示为：图（图（V V，E E）其中其中V=x|xV=x|x 某个数据对象集某个数据对象集，它是顶点的有穷非空集合；，它是顶点的有穷非空集合；E=E=（x x，y y）|x|x，y y VV或或E=xE=|xy|x，y y V V且且P P（x x，y y），它是顶点之间关系的有穷集合，它是顶点之间关系的有穷集合，也叫做边集合，也叫做边集合，P P（x x

2、，y y）表示从）表示从x x到到y y的一条单向通路。的一条单向通路。第1页/共135页图的应用举例图的应用举例例例1 1 交通图（公路、铁路）交通图（公路、铁路）顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；交通图中的有单行道双行道，分别用有向边、无向边表示；V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线例

3、例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系第2页/共135页 通通常常，也也将将图图GG的的顶顶点点集集和和边边集集分分别别记记为为V V（GG）和和E E（GG）。E E（GG）可可以以是是空空集，若集，若E E（GG）为空，则图）为空，则图GG只有顶点而没有边。只有顶点而没有边。若图若图GG中的每条边都是有方向的，则称中的每条边都是有方向的，则称GG为为有向图有向图。在有向图中，一条有向边。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对是由两个顶点组成

4、的有序对，有序对通常用尖括号表示。例如，有序对v 表表示一条由示一条由v vi i到到v vj j的有向边。有向边又称为的有向边。有向边又称为弧弧，弧的始点称为，弧的始点称为弧尾弧尾，弧的终点称为，弧的终点称为弧弧头头。若图。若图GG中的每条边都是没有方向的，则称中的每条边都是没有方向的，则称GG为为无向图无向图。无向图中的边均是顶点。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。的无序对，无序对通常用圆括号表示。第3页/共135页图图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（a a）表示

5、的是有向图）表示的是有向图GG1 1，该图的顶点集和边集分别为：，该图的顶点集和边集分别为：V V（GG1 1）=v=v1 1，v v2 2，v v3 3，v v4 4 E E（GG1 1）=v=，v，v，v例例有序对有序对v ：用以为用以为v vi i起点、以起点、以v vj j为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；边或弧；第4页/共135页例：图例：图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（b b）表示的是无向图）表示的是无向图GG2 2，该图的顶点集和边集分别

6、为：，该图的顶点集和边集分别为：V V（GG2 2）=v=v1 1，v v2 2，v v3 3，v v4 4，v v5 5 E E（GG2 2）=（v vl l，v v2 2），（v v1 1，v v3 3），（v v1 1，v v4 4），（v v2 2，v v3 3），（v v2 2，v v5 5），（v v4 4，v v5 5）无序对无序对(v(vi i,v,vj j)：用连接顶点用连接顶点v vi i、v vj j的线段的线段表示，称为无向边；表示，称为无向边；第5页/共135页在以后的讨论中，我们约定：在以后的讨论中，我们约定：（1 1）一一条条边边中中涉涉及及的的两两个个顶顶点点必

7、必须须不不相相同同，即即：若若（v vi i，v vj j）或或v 是是E E（GG）中的一条边，则要求）中的一条边，则要求v vi ivvj j；（2 2）一对顶点间不能有相同方向的两条有向边；）一对顶点间不能有相同方向的两条有向边；（3 3）一对顶点间不能有两条无向边，即只讨论简单的图。）一对顶点间不能有两条无向边，即只讨论简单的图。第6页/共135页若用若用n n表示图中顶点的数目，用表示图中顶点的数目，用e e表示图中边的数目，按照上述规定，容易得表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有到下述结论：对于一个具有n n个顶点的无向图，其边数个顶点的无向图，其边数e

8、e小于等于小于等于n n（n-1n-1）/2/2，边数恰好等于边数恰好等于n n（n-1n-1）/2/2的无向图称为的无向图称为无向完全图无向完全图；对于一个具有；对于一个具有n n个顶点的有个顶点的有向图，其边数向图，其边数e e小于等于小于等于n n（n-1n-1），边数恰好等于），边数恰好等于n n（n-1n-1）的有向图称为）的有向图称为有向完有向完全图全图。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。二、完全图第7页/共135页例：图例：图8-28-2v1v2v3v4v1v2v3v4（a a）无向完全图）无向完全图G

9、G3 3（b b）有向完全图）有向完全图GG4 4 图图8.28.2所示的所示的GG3 3与与GG4 4分别是具有分别是具有4 4个顶点的无向完全图和有向完全图。图个顶点的无向完全图和有向完全图。图GG3 3共共有有4 4个顶点个顶点6 6条边；图条边；图GG4 4共有共有4 4个顶点个顶点1212条边。条边。若（若（v vi i，v vj j）是一条无向边，则称顶点）是一条无向边，则称顶点v vi i和和v vj j互为邻接点互为邻接点。第8页/共135页若若v 是一条有向边，则称是一条有向边，则称v vi i邻接到邻接到v vj j，v vj j邻接于邻接于v vi i，并称有向边，并称有

10、向边v 关联于关联于v vi i与与v vj j，或称有向边，或称有向边v 与顶点与顶点v vi i和和v vj j相关联。相关联。三、度、入度、出度在图中，一个顶点的在图中，一个顶点的度度就是与该顶点相关联的边的数目，顶点就是与该顶点相关联的边的数目，顶点v v的度记为的度记为D D（v v）。例如在图）。例如在图8.28.2（a a）所示的无向图）所示的无向图GG3 3中，各顶点的度均为中，各顶点的度均为3 3。若若GG为有向图，则把以顶点为有向图，则把以顶点v v为终点的边的数目称为顶点为终点的边的数目称为顶点v v的的入度入度，记为，记为IDID（v v）；把以顶点）；把以顶点v v为

11、始点的边的数目称为为始点的边的数目称为v v的的出度出度，记为，记为ODOD（v v），有向图中），有向图中顶点的度数等于顶点的入度与出度之和，即顶点的度数等于顶点的入度与出度之和，即D D（v v）=ID=ID（v v）+OD+OD（v v）。）。第9页/共135页无无论论有有向向图图还还是是无无向向图图，图图中中的的每每条条边边均均关关联联于于两两个个顶顶点点，因因此此，顶顶点点数数n n、边边数数e e和度数之间有如下关系：和度数之间有如下关系：e=e=.（式（式8-18-1）四、子图给定两个图给定两个图GGi i和和GGj j，其中，其中GGi i=（V Vi i，E Ei i），），

12、GGj j=（V Vj j，E Ej j），若满足），若满足V Vi i V Vj j，E Ei i E Ej j，则称，则称GGi i是是GGj j的的子图子图。第10页/共135页v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示例子图示例（a a）无向图）无向图GG3 3的部分子图的部分子图（b b）有向图）有向图GG4 4的部分子图的部分子图 第11页/共135页五、路径 无无向向图图GG中中若若存存在在着着一一个个顶顶点点序序列列v v、v v1 1、v v2 2、v vmm、u u，且且（v v，v v1 1）、（v v1 1，v v2 2）、（

13、v vmm，u u）均均属属于于E E（GG），则则称称该该顶顶点点序序列列为为顶顶点点v v到到顶顶点点u u的的一一条条路路径径，相相应应地地，顶顶点点序序列列u u、v vmm、v vm-1m-1、v v1 1、v v是是顶顶点点u u到到顶顶点点v v的的一一条条路路径。径。如如果果GG是是有有向向图图，路路径径也也是是有有向向的的，它它由由E E（GG）中中的的有有向向边边v、v、vu组成。组成。路径长度路径长度是该路径上边或弧的数目。是该路径上边或弧的数目。第12页/共135页如果一条路径上除了起点如果一条路径上除了起点v v和终点和终点u u相同外，其余顶点均不相同，则称此路径相

14、同外，其余顶点均不相同，则称此路径为一条为一条简单路径简单路径。起点和终点相同（。起点和终点相同（v=uv=u）的简单路径称为）的简单路径称为简单回路简单回路或或简单环简单环。六、连通图与强连通图在无向图在无向图GG中，若从顶点中，若从顶点v vi i到顶点到顶点v vj j有路径，则称有路径，则称v vi i与与v vj j是连通的。若是连通的。若V V（GG）中任意两个不同的顶点）中任意两个不同的顶点v vi i和和v vj j都连通（即有路径），则称都连通（即有路径），则称GG为为连通图连通图。例。例如，图如，图8.18.1（b b）所示的无向图）所示的无向图GG2 2、图、图8.28.

15、2（a a）所示的无向图）所示的无向图GG3 3是都是连通图。是都是连通图。无向图无向图GG的极大连通子图称为的极大连通子图称为GG的的连通分量连通分量。根据连通分量的定义，可知。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。第13页/共135页例：非连通图及其连通分量示例例：非连通图及其连通分量示例（a a）非连通图）非连通图GG5 5（b b）GG5 5的两个连通分量的两个连通分量H H1 1和和H H2 2在有向图在有向图GG中，若对于中，若对于V V（GG）中任意两个不同的顶点）中任意两个

16、不同的顶点v vi i和和v vj j，都存在从，都存在从v vi i到到v vj j以以及从及从v vj j到到v vi i的路径，则称的路径，则称GG是是强连通图。强连通图。V1V2V4V5V3V1V2V4V5V3第14页/共135页有向图的极大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。根据强连通图的定义，可的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图例如，图8.28.2（b b）所示的有向图）所示的有向图GG4 4是一个具有是一个具有

17、4 4个顶点的强连通图，图个顶点的强连通图，图8.58.5（a a）所示的有向图）所示的有向图GG6 6不是强连通图（不是强连通图（v v2 2、v v3 3、v v4 4没有到达没有到达v v1 1的路径），它的路径），它的两个强连通分量的两个强连通分量H H3 3与与H H4 4如图如图8.58.5（b b）所示。）所示。v v1 1v v2 2v v3 3v v4 4v v1 1v v2 2v v3 3v v4 4（a a）非强连通图）非强连通图GG6 6（b b）GG6 6的两个强连通分量的两个强连通分量H H3 3和和H H4 4 第15页/共135页七、网络有时在图的每条边上附上相

18、关的数值，这种与图的边相关的数值叫有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权权。权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。条边都赋上一个权，则称这种带权图为网络。V0V1V3V234567825V0V2V1455064（a a）无向网络）无向网络GG7 7（b b）有向网络）有向网络GG8 8第16页/共135页作业：作业：8.18.1对于无向图对于无向图8.298.29，试给出，试给出（1 1）图中每个顶点的度；）图中每个顶点的度；（2 2）该图的邻

19、接矩阵；）该图的邻接矩阵；（4 4）该图的连通分量。）该图的连通分量。v0v3v4v2v1v5v6图图8.298.29无向图无向图第17页/共135页8.2 8.2 给定有向图给定有向图8.308.30，试给出，试给出（1 1）顶点）顶点D D的入度与出度；的入度与出度；（2 2）该图的出边表与入边表；）该图的出边表与入边表；（3 3）该图的强连通分量。）该图的强连通分量。ABCDE图图8.308.30有向图有向图第18页/共135页8.2图的基本运算 图图是是一一种种复复杂杂数数据据结结构构，由由图图的的定定义义及及图图的的一一组组基基本本操操作作构构成成了了图图的的抽抽象象数数据据类类型。

20、型。ADTGraphADTGraph数据对象数据对象V V：V V是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R R：R=vR=|vw|v，w w V V且且P P（v v，w w），），P P（v v，w w）定义了边（或弧）（）定义了边（或弧）（v v，w w）的信息）的信息 第19页/共135页图的基本操作如下：图的基本操作如下：（1 1）creatgraphcreatgraph（&g&g）创建一个图的存储结构。创建一个图的存储结构。（2 2）insertvertexinsertvertex（&g&g，v v）在图在图g g中增

21、加一个顶点中增加一个顶点v v。（3 3）deletevertexdeletevertex（&g&g，v v）在图在图g g中删除顶点中删除顶点v v及所有和顶点及所有和顶点v v相关联的边或弧。相关联的边或弧。（4 4）insertedgeinsertedge（&g&g，v v，u u）在图在图g g中增加一条从顶点中增加一条从顶点v v到顶点到顶点u u的边或弧。的边或弧。（5 5）deleteedgedeleteedge（&g&g，v v，u u）在图在图g g中删除一条从顶点中删除一条从顶点v v到顶点到顶点u u的边或弧。的边或弧。第20页/共135页（6 6）travetrave（

22、g g）遍历图遍历图g g。（7 7）locatevertexlocatevertex（g g，v v）求顶点求顶点v v在图在图g g中的位序。中的位序。（8 8）fiirstvertexfiirstvertex（g g，v v）求图求图g g中顶点中顶点v v的第一个邻接点。的第一个邻接点。（9 9）degreedegree（g g，v v）求图求图g g中顶点中顶点v v的度数。的度数。（1010）nextvertexnextvertex（g g，v v，w w）求求图图g g中中与与顶顶点点v v相相邻邻接接的的顶顶点点w w的的下下一一个个邻邻接接点点。即求图即求图g g中顶点中顶点

23、v v的某个邻接点，它的存储顺序排在邻接点的某个邻接点，它的存储顺序排在邻接点w w的存储位置之后。的存储位置之后。ADTGraphADTGraph第21页/共135页8.3图的基本存储结构 图的存储结构至少要保存两类信息：图的存储结构至少要保存两类信息：1)1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系约定约定:G=G=是图是图,V=v,V=v0 0,v,v1 1,v,v2 2,v,vn-1n-1,设顶点的设顶点的角标为它的编号角标为它的编号 如何表示顶点间的关系？如何表示顶点间的关系？V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第22

24、页/共135页8.3.1邻接矩阵及其实现给定图给定图G=G=（V V，E E），其中），其中V V（GG）=v=v0 0，v vi i，v vn-1n-1，GG的邻接矩阵的邻接矩阵（AdacencyMatrixAdacencyMatrix）是具有如下性质的）是具有如下性质的n n阶方阵：阶方阵：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。一、非网络的邻接矩阵一、非网络的邻接矩阵第23页/共135页v0v1v3v2v3v1v0v2图的邻接矩阵示例图的邻接矩阵示例01110111101010101101110110101010

25、01000100101010101100110001000100A1=A1=A2=A2=图图8.7 8.7 无向图无向图G G9 9及有向图及有向图G G1010的邻接矩阵表示的邻接矩阵表示 第24页/共135页用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点各个顶点的度数。对于无向图，顶点v vi i的度数是邻接矩阵中第的度数是邻接矩阵中第i i行或第行或第i i列值为列值为1 1的元素个数，即：的元素个数，即：D D（v vi i）=（8-28-2）对于有向图，邻接矩阵中第对于有

26、向图，邻接矩阵中第i i行值为行值为1 1的元素个数为顶点的元素个数为顶点v vi i的出度，第的出度，第i i列值列值为为1 1的元素的个数为顶点的元素的个数为顶点v vi i的入度，即：的入度，即：ODOD（v vi i）=;ID=;ID（v vi i）=（8-38-3）第25页/共135页二、网络的邻接矩阵二、网络的邻接矩阵当当G=G=（V V，E E）是一个网络时，）是一个网络时，GG的邻接矩阵是具有如下性质的的邻接矩阵是具有如下性质的n n阶方阵：阶方阵：WWij ij 当（当（v vi i，v vj j）或）或v E E（GG）00当（当（v vi i，v vj j）或）或vEE（

27、GG）且）且i=ji=j当（当（v vi i，v vj j）或）或vEE（GG）且）且ijijAiAi，j=j=其中其中WWij ij表示边上的权值；表示边上的权值；表示一个计算机允许的、大于所有边上权值的表示一个计算机允许的、大于所有边上权值的数。数。第26页/共135页V0V1V3V234567825V0V2V1455064网络的邻接矩阵示例网络的邻接矩阵示例056347805634785605603402534025782507825000550 0045045640640A A3 3=A A4 4=（a a）GG7 7的邻接矩阵的邻接矩阵（b b）GG8 8的邻接矩阵的邻接矩阵图图8.

28、88.8网络邻接矩阵示例网络邻接矩阵示例第27页/共135页邻接矩阵存储结构邻接矩阵存储结构#defineFINITY5000/*#defineFINITY5000/*此处用此处用50005000代表无穷大代表无穷大*/#definem20/*#definem20/*最大顶点数最大顶点数*/typedefcharvertextype;/*typedefcharvertextype;/*顶点值类型顶点值类型*/typedefintedgetype;/*typedefintedgetype;/*权值类型权值类型*/typedefstructtypedefstructvertextypevexsm;

29、/*vertextypevexsm;/*顶点信息域顶点信息域*/edgetypeedgesmm;/*edgetypeedgesmm;/*邻接矩阵邻接矩阵*/intn,e;/*intn,e;/*图中顶点总数与边数图中顶点总数与边数*/mgraph;/*mgraph;/*邻接矩阵表示的图类型邻接矩阵表示的图类型*/文件名文件名:mgraph.h:mgraph.h第28页/共135页/*/*/*/*图的邻接矩阵创建算法图的邻接矩阵创建算法*/*/*文件名：文件名：c_ljjz.cc_ljjz.c函数名：函数名：creatmgraph1()*/creatmgraph1()*/*/*/#include#

30、include#includemgraph.h#includemgraph.hvoidcreatmgraph1(mgraph*g)voidcreatmgraph1(mgraph*g)inti,j,k,w;/*inti,j,k,w;/*建立有向网络的邻接矩阵存储结构建立有向网络的邻接矩阵存储结构*/printf(pleaseinputnande:n);printf(pleaseinputnande:n);scanf(%d%d,&g-n,&g-e)scanf(%d%d,&g-n,&g-e);/*;/*输入图的顶点数与边数输入图的顶点数与边数*/getchar();/*getchar();/*取消输

31、入的换行符取消输入的换行符*/printf(pleaseinputvexs:n);printf(pleaseinputvexs:n);第29页/共135页for(i=0;in;i+)/*for(i=0;in;i+)/*输入图中的顶点值输入图中的顶点值*/g-vexsi=getchar();g-vexsi=getchar();for(i=0;in;i+)/*for(i=0;in;i+)/*初始化邻接矩阵初始化邻接矩阵*/for(j=0;jn;j+)for(j=0;jn;j+)if(i=j)g-edgesij=0;if(i=j)g-edgesij=0;elseg-edgesij=FINITY;el

32、seg-edgesij=FINITY;printf(pleaseinputedges:n);printf(pleaseinputedges:n);for(k=0;ke;k+)/*for(k=0;ke;k+)/*输入网络中的边输入网络中的边*/scanf(%d%d%d,&i,&j,&wscanf(%d%d%d,&i,&j,&w););g-edgesij=w;g-edgesij=w;/*/*若是建立无向网，只需在此加入语句若是建立无向网，只需在此加入语句g-edgesji=w;g-edgesji=w;即可即可*/第30页/共135页说明说明:当建立有向网时，边信息以三元组（当建立有向网时，边信息以

33、三元组（i i，j j，w w）的形式输入，）的形式输入，i i、j j分别表示两顶点分别表示两顶点的序号，的序号，w w表示边上的权。对于每一条输入的边信息（表示边上的权。对于每一条输入的边信息（i i，j j，w w），只需将），只需将g-g-edgesijedgesij赋值为赋值为w w。算法算法8.58.5中用到的中用到的creatmgraph2()creatmgraph2()是用于建立无向网络的函数，它与是用于建立无向网络的函数，它与creatmgraph1creatmgraph1()()的区别在于对每一条输入的边信息（的区别在于对每一条输入的边信息（i i，j j，w w），需同时

34、将），需同时将g-edgesijg-edgesij和和g-g-edgesjiedgesji赋值为赋值为w w。当建立非网络的存储结构时，所有的边信息只需按二元组（当建立非网络的存储结构时，所有的边信息只需按二元组（i i，j j）的形式输入。）的形式输入。第31页/共135页8.3.2邻接表及其实现 用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有而与边的数目无关。一个含有n n个顶点的图，如果其边数比个顶点的图，如果其边数比n n2 2少得多，那么它少得多，那么它的邻接矩阵就会有很多

35、空元素，浪费了存储空间。的邻接矩阵就会有很多空元素，浪费了存储空间。n n无向图的邻接表无向图的邻接表对于图对于图GG中的每个顶点中的每个顶点v vi i，该方法把所有邻接于，该方法把所有邻接于v vi i的顶点的顶点v vj j链成一个带头结点的单链成一个带头结点的单链表，这个单链表就称为顶点链表，这个单链表就称为顶点v vi i的邻接表。单链表中的每个结点至少包含两个域，一的邻接表。单链表中的每个结点至少包含两个域，一个为个为邻接点域邻接点域（adjvexadjvex），它指示与顶点），它指示与顶点v vi i邻接的顶点在图中的位序，另一个为邻接的顶点在图中的位序，另一个为链域链域（nex

36、tnext），它指示与顶点），它指示与顶点v vi i邻接的下一个结点。邻接的下一个结点。第32页/共135页adjvex nextadjvex nextvertex firstdegevertex firstdege为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。一起来描述图的存储结构。v0v1v3v2图图8.78.7无向图无向图GG9 91 2 3 0

37、2 0 1 3 0 2 V0V1V2V3图图8.9G8.9G9 9的邻接表的邻接表表头结点结构表头结点结构边结点结构边结点结构第33页/共135页对于无向图，对于无向图，v vi i的邻接表中每个表结点都对应于与的邻接表中每个表结点都对应于与v vi i相关联的一条边；对于有相关联的一条边；对于有向图来说，如果每一顶点向图来说，如果每一顶点v vi i的邻接表中每个表结点都存储以的邻接表中每个表结点都存储以v vi i的为始点射出的一条的为始点射出的一条边，则称这种表为有向图的边，则称这种表为有向图的出边表出边表（有向图的邻接表），反之，若每一顶点（有向图的邻接表），反之，若每一顶点v vi

38、i的邻的邻接表中每个表结点都对应于以接表中每个表结点都对应于以v vi i为终点的边（即射入为终点的边（即射入v vi i的边），则称这种表为有向的边），则称这种表为有向图的图的入边表入边表（又称逆邻接表）。（又称逆邻接表）。v0v1v2v31 0 2 0 1 1 GG1010的出边表的出边表v0v1v2v3 1 2 0 2 1 3 GG1010的入边表的入边表v3v1v0v2图图8.7(b)8.7(b)有向图有向图GG1010第34页/共135页在无向图的邻接表中，顶点在无向图的邻接表中，顶点v vi i的度为第的度为第i i个链表中结点的个数；而在有向图的出个链表中结点的个数；而在有向图的

39、出边表中，第边表中，第i i个链表中的结点个数是顶点个链表中的结点个数是顶点v vi i的出度；为了求入度，必须对整个邻接表的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为扫描一遍，所有链表中其邻接点域的值为i i的结点的个数是顶点的结点的个数是顶点v vi i的入度。的入度。1 2 3 0 2 0 1 3 0 2 V0V1V2V3V V0 0的度为的度为3 3v0v1v2v31 0 2 0 1 1 GG1010的出边表的出边表V V0 0的出度为的出度为1 1，入度，入度为为2 2第35页/共135页邻接表的存储结构邻接表的存储结构/*/*/*/*邻接表存储结构邻接表

40、存储结构文件名：文件名：adjgraph.h*/adjgraph.h*/*/*/#definem20/*#definem20/*预定义图的最大顶点数预定义图的最大顶点数*/typedefchardatatype;/*typedefchardatatype;/*顶点信息数据类型顶点信息数据类型*/typedefstructnode/*typedefstructnode/*边表结点边表结点*/intadjvex;/*intadjvex;/*邻接点邻接点*/structnode*next;structnode*next;edgenode;edgenode;adjvex nextadjvex next

41、边结点结构边结点结构第36页/共135页typedefstructvnode/*typedefstructvnode/*头结点类型头结点类型*/datatypevertex;/*datatypevertex;/*顶点信息顶点信息*/edgenode*firstedge;/*edgenode*firstedge;/*邻接链表头指针邻接链表头指针*/vertexnode;vertexnode;typedefstruct/*typedefstruct/*邻接表类型邻接表类型*/vertexnodeadjlistm;/*vertexnodeadjlistm;/*存放头结点的顺序表存放头结点的顺序表*/

42、intn,e;/*intn,e;/*图的顶点数与边数图的顶点数与边数*/adjgraph;adjgraph;vertex firstdegevertex firstdege头结点结构头结点结构第37页/共135页/*/*/*/*无向图的邻接表创建算法无向图的邻接表创建算法*/*/*文件名文件名c_ljb.cc_ljb.c函数名：函数名：createadjgraph()*/createadjgraph()*/*/*/voidcreateadjgraph(adjgraph*g)voidcreateadjgraph(adjgraph*g)inti,j,k;inti,j,k;edgenode*s;ed

43、genode*s;printf(Pleaseinputnande:n);printf(Pleaseinputnande:n);scanf(%d%d,&g-n,&g-e);scanf(%d%d,&g-n,&g-e);/*/*输入顶点数与边数输入顶点数与边数*/getchar();getchar();printf(Pleaseinput%dvertex:,g-n);printf(Pleaseinput%dvertex:,g-n);第38页/共135页for(i=0;in;i+)for(i=0;in;i+)scanf(“%c”,&g-adjlisti.vertex);/*scanf(“%c”,&g-

44、adjlisti.vertex);/*读入顶点信息读入顶点信息*/g-adjlisti.firstedge=NULL;/*g-adjlisti.firstedge=NULL;/*边表置为空表边表置为空表*/printf(Pleaseinput%dedges:,g-e);printf(Pleaseinput%dedges:,g-e);for(k=0;ke;k+)/*for(k=0;ke;k+)/*循环循环e e次建立边表次建立边表*/scanf(%d%d,&i,&j);/*scanf(%d%d,&i,&j);/*输入无序对（输入无序对（i,j i,j）*/s=(edgenode*)malloc(

45、sizeof(edgenode);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=j;/*s-adjvex=j;/*邻接点序号为邻接点序号为j*/j*/s-next=g-adjlisti.firstedge;s-next=g-adjlisti.firstedge;g-adjlisti.firstedge=s;g-adjlisti.firstedge=s;/*将将新新结结点点*s s插插入入顶顶点点v vi i的边表头部的边表头部*/第39页/共135页s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)

46、malloc(sizeof(edgenode);s-adjvex=i;/*s-adjvex=i;/*邻接点序号为邻接点序号为i*/i*/s-next=g-adjlistj.firstedge;s-next=g-adjlistj.firstedge;g-adjlistj.firstedge=s;g-adjlistj.firstedge=s;/*/*将新结点将新结点*s s插入顶点插入顶点v vj j的边表头部的边表头部*/算法算法8.28.2建立无向图的邻接表算法建立无向图的邻接表算法说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻说明：一个图的邻接矩阵表示是唯一的，但其邻

47、接表表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。第40页/共135页4 54 5ABCDABCD0 1 0 2 0 3 1 2 2 30 1 0 2 0 3 1 2 2 3ABDC例例:若若需需建建立立下下图图所所示示的的无无向向图图邻邻接接表表存存储储结结构构,则则在在执执行行程程序序c_ljb.cc_ljb.c时时如如果果输输入的信息为：入的信息为：则将建立如下的邻接表存储结构。则将建立如下的邻接表存储结构。A 3-2-1A 3-2-1B 2-0B 2-0C 3-1-

48、0C 3-1-0D 2-0D 2-0第41页/共135页8.3.3邻接多重表n n在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。边结点的结构边结点的结构 mark vexi linki vexj linkj 其中，其中，mark mark 是记录是否处理过的标记；是记录是否处理过的标记；vexivexi和和vexjvexj是依附于该边的两顶点位是依附于该边的两顶点位置。置。lnikilniki域是链接指针，指向下一条依附于顶点域是链接指针，指向下一条依附于顶点vexivexi的边；的边；linkjlinkj也

49、是链接指针，也是链接指针，指向下一条依附于顶点指向下一条依附于顶点vexjvexj的边。需要时还可设置一个存放与该边相关的权值的域的边。需要时还可设置一个存放与该边相关的权值的域 costcost。第42页/共135页 顶点结点的结构顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，其中，vertex vertex 存放与该顶点相关的信息，存放与该顶点相关的信息，firstedge firstedge 是指示第一条依附于该顶是指示第一条依附于该顶点的边的指针。点的边的指针。在邻接多重表中

50、在邻接多重表中,所有依附于同一个顶点的边都链接在同一个单链表中。所有依附于同一个顶点的边都链接在同一个单链表中。从顶点从顶点 i i 出发出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。接顶点。vertex Firstedge第43页/共135页V0V1V3V234567825V0V1V2V356013402780325230123无向网络的邻接多重表示例无向网络的邻接多重表示例其中边表结点增加了一个存储权值的数据域其中边表结点增加了一个存储权值的数据域。第44页/共135页8.4图的遍历图的遍历：从图的某顶点出发，访问