图图的基本概念.pptx

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

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

2、它是顶点之间关系的有穷集合，也叫做边集合，它是顶点之间关系的有穷集合，也叫做边集合，P P（x x，y y）表示从）表示从x x到到y y的一条单向的一条单向(dnxin)(dnxin)通路。通路。第1页/共135页第二页，共135页。图的应用图的应用(yngyng)(yngyng)举例举例例例1 1 交通图（公路、铁路）交通图（公路、铁路）顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；交通图中的有单行道双行道，分别用有向边、无向边表示；V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3例例

3、2 2 电路图电路图 顶点：元件顶点：元件(yunjin)(yunjin)边：连接元件边：连接元件(yunjin)(yunjin)之间的线路之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点(ddin)(ddin)边：地点边：地点(ddin)(ddin)间的连线间的连线例例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系第2页/共135页第三页，共135页。通常，也将图通常，也将图GG的顶点集和边集分别记为的顶点集和边集分别记为V V（GG）和）和E E（GG）。）。E E（GG）可以是

4、空集）可以是空集(knj)(knj)，若，若E E（GG）为空，则图）为空，则图GG只有顶点而没有边。只有顶点而没有边。若图若图GG中的每条边都是有方向的，则称中的每条边都是有方向的，则称GG为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示(biosh)(biosh)。例如，有序对。例如，有序对vivj表示表示(biosh)(biosh)一条由一条由vivi到到vjvj的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终点称为弧头。若图的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终

5、点称为弧头。若图GG中的每条边都是没有方向的，则称中的每条边都是没有方向的，则称GG为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示(biosh)(biosh)。第3页/共135页第四页，共135页。图图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（a a）表示）表示(biosh)(biosh)的是有向图的是有向图G1G1，该图的顶点集和边集分别为：，该图的顶点集和边集分别为：V V（G1G1）=v1=v1，v2v2，v3v3

6、，v4v4E E（G1G1）=v1=v2，v1v3，v2v4，v3v2例例有序对有序对 ：用以为用以为vivi起点起点(qdin)(qdin)、以、以vjvj为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；边或弧；第4页/共135页第五页，共135页。例：图例：图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（b b）表示的是无向图）表示的是无向图G2G2，该图的顶点，该图的顶点(dngdin)(dngdin)集和边集分别为：集和边集分别为：V V（G2G2）=v1=v1，v2v2，

7、v3v3，v4v4，v5v5E E（G2G2）=（vlvl，v2v2），（），（v1v1，v3v3），（），（v1v1，v4v4），（），（v2v2，v3v3），（），（v2v2，v5v5），（），（v4v4，v5v5）无序对无序对(vi,vj)(vi,vj)：用连接用连接(linji)(linji)顶点顶点vivi、vjvj的线段的线段表示，称为无向边；表示，称为无向边；第5页/共135页第六页，共135页。在以后的讨论中，我们在以后的讨论中，我们(wmen)(wmen)约定：约定：（1 1）一条边中涉及的两个顶点必须不相同，即：若（）一条边中涉及的两个顶点必须不相同，即：若（vivi，vj

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

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

10、页第八页，共135页。例：图例：图8-28-2v1v2v3v4v1v2v3v4（a a）无向完全图）无向完全图GG3 3（b b）有向完全图）有向完全图GG4 4 图图8.28.2所示的所示的G3G3与与G4G4分别是具有分别是具有4 4个顶点的无向完全个顶点的无向完全(wnqun)(wnqun)图和有向完全图和有向完全(wnqun)(wnqun)图。图图。图G3G3共有共有4 4个顶点个顶点6 6条边；图条边；图G4G4共有共有4 4个顶点个顶点1212条边。条边。若（若（vivi，vjvj）是一条无向边，则称顶点）是一条无向边，则称顶点(dngdin)vi(dngdin)vi和和vjvj互

11、为邻接点互为邻接点。第8页/共135页第九页，共135页。若若vivj是一条有向边，则称是一条有向边，则称vivi邻接到邻接到vjvj，vjvj邻接于邻接于vivi，并称有向边，并称有向边vivj关联关联(gunlin)(gunlin)于于vivi与与vjvj，或称有向边，或称有向边vivj与顶点与顶点vivi和和vjvj相关联相关联(gunlin)(gunlin)。三、度、入度、出度三、度、入度、出度在图中，一个顶点的度就是在图中，一个顶点的度就是(jish)(jish)与该顶点相关联的边的数目，顶点与该顶点相关联的边的数目，顶点v v的度记为的度记为DD（v v）。例如在图）。例如在图8.

12、28.2（a a）所示的无向图）所示的无向图G3G3中，各顶点的度均为中，各顶点的度均为3 3。若若GG为有向图，则把以顶点为有向图，则把以顶点v v为终点的边的数目称为顶点为终点的边的数目称为顶点v v的入度，记为的入度，记为IDID（v v）；把以顶点）；把以顶点v v为始点的边的数目称为为始点的边的数目称为v v的出度，记为的出度，记为ODOD（v v），有向图中顶点的度数等于顶点的入度与出度之和，即），有向图中顶点的度数等于顶点的入度与出度之和，即DD（v v）=ID=ID（v v）+OD+OD（v v）。）。第9页/共135页第十页，共135页。无论有向图还是无向图，图中的每条边均关

13、联于两个顶点，因此，顶点数无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n n、边数、边数e e和度数之间有如下和度数之间有如下(rxi)(rxi)关系：关系：e=e=.（式（式8-18-1）四、子图四、子图给定给定(idn)(idn)两个图两个图GiGi和和GjGj，其中，其中Gi=Gi=（ViVi，EiEi），），Gj=Gj=（VjVj，EjEj），若满足），若满足ViViVjVj，EiEiEjEj，则称，则称GiGi是是GjGj的子图。的子图。第10页/共135页第十一页，共135页。v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示

14、例子图示例(shl)(shl)（a a）无向）无向(wxin)(wxin)图图G3G3的部分子的部分子图图（b b）有向图）有向图G4G4的部分的部分(bfen)(bfen)子子图图 第11页/共135页第十二页，共135页。五、路径五、路径(ljng)(ljng)无向图无向图GG中若存在着一个顶点序列中若存在着一个顶点序列(xli)v(xli)v、v1v1、v2v2、vmvm、u u，且（，且（v v，v1v1）、（）、（v1v1，v2v2）、）、（、（vmvm，u u）均属于）均属于E E（GG），则称该顶点序列），则称该顶点序列(xli)(xli)为顶点为顶点v v到顶点到顶点u u的一

15、条路径，相应地，顶点序列的一条路径，相应地，顶点序列(xli)u(xli)u、vmvm、vm-1vm-1、v1v1、v v是顶点是顶点u u到顶点到顶点v v的一条路径。的一条路径。如果如果GG是有向图，路径也是有向的，它由是有向图，路径也是有向的，它由E E（GG）中的有向边）中的有向边vv1、v1v2、vmu组成。路径长度是该路径上边或弧的数目。组成。路径长度是该路径上边或弧的数目。第12页/共135页第十三页，共135页。如果一条路径上除了起点如果一条路径上除了起点v v和终点和终点(zhngdin)u(zhngdin)u 相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相

16、同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点(zhngdin)(zhngdin)相同（相同（v=uv=u）的简单路径称为简单回路或简单环。）的简单路径称为简单回路或简单环。六、连通六、连通(lintng)(lintng)图与强连通图与强连通(lintng)(lintng)图图在无向图在无向图GG中，若从顶点中，若从顶点vivi到顶点到顶点vjvj有路径，则称有路径，则称vivi与与vjvj是连通的。若是连通的。若V V（GG）中任意两个不同）中任意两个不同(btn)(btn)的顶点的顶点vivi和和vjvj都连通（即有路径），则称都连通（即有路径），则称GG为连通图。例如，图为

17、连通图。例如，图8.18.1（b b）所示的无向图）所示的无向图G2G2、图、图8.28.2（a a）所示的无向图）所示的无向图G3G3是都是连通图。是都是连通图。无向图无向图GG的极大连通子图称为的极大连通子图称为GG的的连通分量连通分量。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。第13页/共135页第十四页，共135页。例：非连通例：非连通(lintng)(lintng)图及其连通图及其连通(lintng)(lintng)分量示例分量示例（a a）非连通图）非连通图

18、G5G5（b b）G5G5的两个的两个(lin)(lin)连通分量连通分量H1H1和和H2H2在有向图在有向图GG中，若对于中，若对于V V（GG）中任意两个不同的顶点）中任意两个不同的顶点vivi和和vjvj，都存在，都存在(cnzi)(cnzi)从从vivi到到vjvj以及从以及从vjvj到到vivi的路径，则称的路径，则称GG是强连通图。是强连通图。V1V2V4V5V3V1V2V4V5V3第14页/共135页第十五页，共135页。有向图的极大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量

19、。例如，图的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分量。例如，图8.28.2（b b）所示的有向图）所示的有向图G4G4是一个具有是一个具有4 4个顶点的强连通图，图个顶点的强连通图，图8.58.5（a a）所示的有向图）所示的有向图G6G6不是强连通图（不是强连通图（v2v2、v3v3、v4v4没有到达没有到达v1v1的路径的路径(ljng)(ljng)），它的两个强连通分量），它的两个强连通分量H3H3与与H4H4如图如图8.58.5（b b）所示。）所示。v v1 1v v2 2v v3 3v v4 4v v1 1v v2 2v

20、 v3 3v v4 4（a a）非强连通图）非强连通图GG6 6（b b）GG6 6的两个强连通分量的两个强连通分量H H3 3和和H H4 4 第15页/共135页第十六页，共135页。七、网络七、网络(wnglu)(wnglu)有时有时(yush)(yush)在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。权可以表示两个顶点之间的距离、耗费等具有权可以表示两个顶点之间的距离、耗费等具有(jyu)(jyu)某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。某种意义的数。若将图的每条边都赋上一个权，则称这种带权图

21、为网络。V0V1V3V234567825V0V2V1455064（a a）无向网络）无向网络GG7 7（b b）有向网络）有向网络GG8 8第16页/共135页第十七页，共135页。作业作业(zuy)(zuy)：8.18.1对于无向图对于无向图8.298.29，试给出，试给出（1 1）图中每个顶点的度；）图中每个顶点的度；（2 2）该图的邻接矩阵；）该图的邻接矩阵；（4 4）该图的连通）该图的连通(lintng)(lintng)分量。分量。v0v3v4v2v1v5v6图图8.298.29无向无向(wxin)(wxin)图图第17页/共135页第十八页，共135页。8.2 8.2 给定有向图给定

22、有向图8.308.30，试给出，试给出（1 1）顶点）顶点(dngdin)D(dngdin)D的入度与出度；的入度与出度；（2 2）该图的出边表与入边表；）该图的出边表与入边表；（3 3）该图的强连通分量。）该图的强连通分量。ABCDE图图8.308.30有向图有向图第18页/共135页第十九页，共135页。8.28.2图的基本图的基本(jbn)(jbn)运算运算图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。图是一种复杂数据结构，由图的定义及图的一组基本操作构成了图的抽象数据类型。ADTGraphADTGraph数据对象数据对象V V：V V是具有相同特性的数据元素

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

24、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中增加中增加(zngji)(zngji)一条从顶点一条从顶点v v到顶点到顶点u u的边或弧。的边或弧。（5 5）deleteedgedeleteedge（&g&g，v v，u u）在图在图g g中删除一条从顶点中删除一条从顶点v v到顶点到顶点u u的边或弧。的边或弧。第20页/共135页第二十一页，共135页。（6

25、 6）travetrave（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的度数的度数(dshu)(dshu)。（1010）nextvertexnextvertex（g g，v v，ww）求图求图g g中与顶点中与顶点v v相邻接的顶点相邻接的顶点ww的下一个邻接点

26、。即求图的下一个邻接点。即求图g g中顶点中顶点v v的某个邻接点，它的存储顺序排在邻接点的某个邻接点，它的存储顺序排在邻接点ww的存储位置之后。的存储位置之后。ADTGraphADTGraph第21页/共135页第二十二页，共135页。8.38.3图的基本图的基本(jbn)(jbn)存储结构存储结构 图的存储结构至少要保存图的存储结构至少要保存(bocn)(bocn)两类信息：两类信息：1)1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系约定约定(yudng):(yudng):G=G=是图是图,V=v0,v1,v2,vn-1,V=v0,v1,v2,vn-1,设顶点的设顶点的 角标为

27、它的编号角标为它的编号 如何表示顶点间的关系？如何表示顶点间的关系？V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第22页/共135页第二十三页，共135页。8.3.18.3.1邻接矩阵及其实现邻接矩阵及其实现(shxin)(shxin)给定图给定图G=G=（V V，E E），其中），其中V V（GG）=v0=v0，vivi，vn-1vn-1，GG的邻接矩阵（的邻接矩阵（AdacencyMatrixAdacencyMatrix）是具有如下性质）是具有如下性质(xngzh)(xngzh)的的n n阶方阵：阶方阵：无向无向(w xin(w xin)图的邻接

28、矩阵是对称的，有向图的邻接矩阵可能是不对称的。图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。一、非网络的邻接矩阵一、非网络的邻接矩阵第23页/共135页第二十四页，共135页。v0v1v3v2v3v1v0v2图的邻接矩阵示例图的邻接矩阵示例(shl)(shl)0111011110101010110111011010101001000100101010101100110001000100A1=A1=A2=A2=图图8.7 8.7 无向图无向图G G9 9及有向图及有向图G G1010的邻接矩阵表示的邻接矩阵表示 第24页/共135页第二十五页，共135页。用邻接矩阵表示图，很容易判定任意

29、两个顶点之间是否有边相连，并求得各个顶点的度数用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数(dshu)(dshu)。对于无向图，顶点。对于无向图，顶点vivi的度数的度数(dshu)(dshu)是邻接矩阵中第是邻接矩阵中第i i行或第行或第i i列值为列值为1 1的元素个数，即：的元素个数，即：DD（v vii）=（8-28-2）对于有向图，邻接矩阵中第对于有向图，邻接矩阵中第i i行值为行值为1 1的元素的元素(yuns)(yuns)个数为顶点个数为顶点vivi的出度，第的出度，第i i列值为列值为1 1的元素的元素(yuns)(yuns)的个数为顶点的个数

30、为顶点vivi的入度，即：的入度，即：ODOD（v vii）=;ID=;ID（v vii）=（8-38-3）第25页/共135页第二十六页，共135页。二、网络二、网络(wnglu)(wnglu)的邻接矩阵的邻接矩阵当当G=G=（V V，E E）是一个网络时，）是一个网络时，GG的邻接矩阵是具有如下性质的邻接矩阵是具有如下性质(xngzh)(xngzh)的的n n阶方阵：阶方阵：WWijij 当（当（v vii，v vjj）或）或v E E（GG）00当（当（v vii，v vjj）或）或vEE（GG）且）且i=ji=j当（当（v vii，v vjj）或）或vEE（GG）且）且ijijAiAi

31、，j=j=其中其中(qzhng)Wij(qzhng)Wij表示边上的权值；表示边上的权值；表示一个计算机允许的、大于所有边上权值的数。表示一个计算机允许的、大于所有边上权值的数。第26页/共135页第二十七页，共135页。V0V1V3V234567825V0V2V1455064网络网络(wnglu)(wnglu)的邻接矩阵示例的邻接矩阵示例056347805634785605603402534025782507825000550 0045045640640A A33=A A44=（a a）GG7 7的邻接矩阵的邻接矩阵（b b）GG8 8的邻接矩阵的邻接矩阵图图8.88.8网络邻接矩阵示例网络

32、邻接矩阵示例第27页/共135页第二十八页，共135页。邻接矩阵存储邻接矩阵存储(cnch)(cnch)结构结构#define#defineFINITYFINITY50005000 /*/*此此处处用用50005000代代表表(dibio)(dibio)无无穷穷大大*/*/#definem20/*#definem20/*最大顶点数最大顶点数*/*/typedefcharvertextype;/*typedefcharvertextype;/*顶点值类型顶点值类型*/*/typedefintedgetype;/*typedefintedgetype;/*权值类型权值类型*/*/typedefst

33、ructtypedefstructvertextypevexsm;/*vertextypevexsm;/*顶点信息域顶点信息域*/*/edgetypeedgesmm;/*edgetypeedgesmm;/*邻接矩阵邻接矩阵*/*/intn,e;/*intn,e;/*图中顶点总数与边数图中顶点总数与边数*/*/mgraph;/*mgraph;/*邻接矩阵表示的图类型邻接矩阵表示的图类型*/*/文件名文件名:mgraph.h:mgraph.h第28页/共135页第二十九页，共135页。/*/*/*/*图的邻接矩阵创建算法图的邻接矩阵创建算法(sunf)*/(sunf)*/*/*文件名：文件名：c_

34、ljjz.cc_ljjz.c函数名：函数名：creatmgraph1()*/creatmgraph1()*/*/*/#include#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);/*scan

35、f(%d%d,&g-n,&g-e);/*输入图的顶点数与边数输入图的顶点数与边数*/*/getchar();/*getchar();/*取消输入的换行符取消输入的换行符*/*/printf(pleaseinputvexs:n);printf(pleaseinputvexs:n);第29页/共135页第三十页，共135页。for(i=0;in;i+)/*for(i=0;in;i+)/*输入图中的顶点输入图中的顶点(dngdin)(dngdin)值值*/*/g-vexsi=getchar();g-vexsi=getchar();for(i=0;in;i+)/*for(i=0;in;i+)/*初始化

36、邻接矩阵初始化邻接矩阵*/*/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;elseg-edgesij=FINITY;printf(pleaseinputedges:n);printf(pleaseinputedges:n);for(k=0;ke;k+)/*for(k=0;ke;k+)/*输入网络中的边输入网络中的边*/*/scanf(%d%d%d,&i,&j,&w);scanf(%d%d%d,&i,&j,&w);g-edgesij=w;g-edgesij=w;/*/

37、*若是建立无向网，只需在此加入语句若是建立无向网，只需在此加入语句g-edgesji=w;g-edgesji=w;即可即可*/*/第30页/共135页第三十一页，共135页。说明说明:当建立有向网时，边信息当建立有向网时，边信息(xnx)(xnx)以三元组（以三元组（i i，j j，ww）的形式输入，）的形式输入，i i、j j分别表示两顶点的序号，分别表示两顶点的序号，ww表示边上的权。对于每一条输入的边信息表示边上的权。对于每一条输入的边信息(xnx)(xnx)（i i，j j，ww），只需将），只需将g-edgesijg-edgesij赋值为赋值为ww。算法算法8.58.5中用到的中用到

38、的creatmgraph2()creatmgraph2()是用于建立无向网络的函数，它与是用于建立无向网络的函数，它与creatmgraph1()creatmgraph1()的区别在于对每一条输入的边信息的区别在于对每一条输入的边信息(xnx)(xnx)（i i，j j，ww），需同时将），需同时将g-edgesijg-edgesij和和g-edgesjig-edgesji赋值为赋值为ww。当建立非网络的存储结构时，所有的边信息当建立非网络的存储结构时，所有的边信息(xnx)(xnx)只需按二元组（只需按二元组（i i，j j）的形式输入。）的形式输入。第31页/共135页第三十二页，共135

39、页。8.3.28.3.2邻接邻接(lnji)(lnji)表及其实现表及其实现 用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。一个含有n n个顶点的图，如果个顶点的图，如果(rgu(rgu)其边数比其边数比n2n2少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间。少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储空间。nn无向图的邻接表无向图的邻接表nn 对于图对于图GG中的每个顶点中的每个顶点vivi，该方法把所有邻接于，该方法把所有邻接于vivi的顶点的

40、顶点vjvj链成一个带头链成一个带头(di tu)(di tu)结点的单链表，这个单链表就称为顶点结点的单链表，这个单链表就称为顶点vivi的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（的邻接表。单链表中的每个结点至少包含两个域，一个为邻接点域（adjvexadjvex），它指示与顶点），它指示与顶点vivi邻接的顶点在图中的位序，另一个为链域（邻接的顶点在图中的位序，另一个为链域（nextnext），它指示与顶点），它指示与顶点vivi邻接的下一个结点。邻接的下一个结点。第32页/共135页第三十三页，共135页。adjvex nextadjvex nextvertex fir

41、stdegevertex firstdege为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息(xnx)(xnx)与邻接表放在一起来描述图的存储结构。与邻接表放在一起来描述图的存储结构。v0v1v3v2图图8.78.7无向图无向图GG991 2 3 0 2 0 1 3 0 2 V0V1V2V3图图8.9G8.9G99的邻接表的邻接表表头表头(biotu)(biotu)结点结构结点结构边结点边结点(jidin

42、)(jidin)结构结构第33页/共135页第三十四页，共135页。对于无向图，对于无向图，vivi的邻接表中每个表结点都对应于与的邻接表中每个表结点都对应于与vivi相关联的一条边；对于有向图来说，如果每一顶点相关联的一条边；对于有向图来说，如果每一顶点vivi的邻接表中每个表结点都存储以的邻接表中每个表结点都存储以vivi的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之的为始点射出的一条边，则称这种表为有向图的出边表（有向图的邻接表），反之(fnzh)(fnzh)，若每一顶点，若每一顶点vivi的邻接表中每个表结点都对应于以的邻接表中每个表结点都对应于以vivi为终

43、点的边（即射入为终点的边（即射入vivi的边），则称这种表为有向图的入边表（又称逆邻接表）。的边），则称这种表为有向图的入边表（又称逆邻接表）。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页第三十五页，共135页。在无向图的邻接表中，顶点在无向图的邻接表中，顶点vivi的度为第的度为第i i个链表中结点个链表中结点(jidin)(jidin)的个数；而在有向图的出边表中，第的个数；而在有向图的出边表中，第i i个链表

44、中的结点个链表中的结点(jidin)(jidin)个数是顶点个数是顶点vivi的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为的出度；为了求入度，必须对整个邻接表扫描一遍，所有链表中其邻接点域的值为i i的结点的结点(jidin)(jidin)的个数是顶点的个数是顶点vivi的入度。的入度。1 2 3 0 2 0 1 3 0 2 V0V1V2V3V V00的度为的度为3 3v0v1v2v31 0 2 0 1 1 GG1010的出边表的出边表V V00的出度为的出度为1 1，入度为，入度为2 2第35页/共135页第三十六页，共135页。邻接表的存储邻接表的存储(cnch

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

46、next;structnode*next;edgenode;edgenode;adjvex nextadjvex next边结点边结点(jidin)(jidin)结构结构第36页/共135页第三十七页，共135页。typedefstructvnode/*typedefstructvnode/*头结点类型头结点类型*/*/datatypevertex;/*datatypevertex;/*顶点信息顶点信息*/*/edgenode*firstedge;/*edgenode*firstedge;/*邻接链表头指针邻接链表头指针(zhzhn)*/(zhzhn)*/vertexnode;vertexno

47、de;typedefstruct/*typedefstruct/*邻接表类型邻接表类型*/*/vertexnodeadjlistm;/*vertexnodeadjlistm;/*存放头结点的顺序表存放头结点的顺序表*/*/intn,e;/*intn,e;/*图的顶点数与边数图的顶点数与边数*/*/adjgraph;adjgraph;vertex firstdegevertex firstdege头结点头结点(jidin)(jidin)结构结构第37页/共135页第三十八页，共135页。/*/*/*/*无向图的邻接无向图的邻接(lnji)(lnji)表创建算法表创建算法*/*/*/*文件名文件名

48、c_ljb.cc_ljb.c函数名：函数名：createadjgraph()*/createadjgraph()*/*/*/voidcreateadjgraph(adjgraph*g)voidcreateadjgraph(adjgraph*g)inti,j,k;inti,j,k;edgenode*s;edgenode*s;printf(Pleaseinputnande:n);printf(Pleaseinputnande:n);scanf(%d%d,&g-n,&g-e);/*scanf(%d%d,&g-n,&g-e);/*输入顶点数与边数输入顶点数与边数*/*/getchar();getcha

49、r();printf(Pleaseinput%dvertex:,g-n);printf(Pleaseinput%dvertex:,g-n);第38页/共135页第三十九页，共135页。for(i=0;in;i+)for(i=0;in;i+)scanf(“%c”,&g-adjlisti.vertex);/*scanf(“%c”,&g-adjlisti.vertex);/*读入顶点信息读入顶点信息*/*/g-adjlisti.firstedge=NULL;/*g-adjlisti.firstedge=NULL;/*边表置为空表边表置为空表*/*/printf(Pleaseinput%dedges:

50、,g-e);printf(Pleaseinput%dedges:,g-e);for(k=0;ke;k+)/*for(k=0;ke;k+)/*循环循环(xnhun)e(xnhun)e次建立边表次建立边表*/*/scanf(%d%d,&i,&j);/*scanf(%d%d,&i,&j);/*输入无序对（输入无序对（i,j i,j）*/*/s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)malloc(sizeof(edgenode);s-adjvex=j;/*s-adjvex=j;/*邻接点序号为邻接点序号为j*/j*/s-next=g-adjli