图的基本概念.ppt

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

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），它是顶点之间关系的有穷集，它是顶点之间关系的有穷集合，也叫做边集合，合，也叫做边

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

3、例例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 通通常常，也也将将图图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为为无向图无向图。无向图中的。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。边均是顶点的无序对，无序对通常用圆括号表示。图图1-11-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图1.11.1（a a）表表示示的的是是有有向向图图GG1 1，该该

5、图图的的顶顶点点集集和和边集分别为：边集分别为：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为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；边或弧；例：图例：图1-11-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图1.11.1（b b）表表示示的的是是无无向向图图GG2 2，该该图图的的顶顶点点集集和和边集分别为：边集分别为：V V（GG2 2）=v=v1 1

6、，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的线段的线段表示，称为无向边；表示，称为无向边；在以后的讨论中，我们约定：在以后的讨论中，我们约定：（1 1）一一条条边边中中涉涉及及的的两两个个顶顶点点必必须须不不相相同同，即即：若若（v vi i，v vj j）或或v 是是

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

8、）/2/2的无向图称为的无向图称为无向无向完全图完全图；对于一个具有；对于一个具有n n个顶点的有向图，其边数个顶点的有向图，其边数e e小于等于小于等于n n（n-1n-1），边数恰好等于），边数恰好等于n n（n-1n-1）的有向）的有向图称为图称为有向完全图有向完全图。也就是说完全图具有最多的边。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。数，任意一对顶点间均有边相连。二、完全图例：图例：图1-21-2v1v2v3v4v1v2v3v4（a a）无向完全图）无向完全图GG3 3（b b）有向完全图）有向完全图GG4 4 图图1.21.2所示的所示的GG3 3与与GG4 4分别是

9、具有分别是具有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互为互为邻接点邻接点。若若v 是一条有向边，则称是一条有向边，则称v vi i邻接到邻接到v vj j，v vj j邻邻接于接于v vi i，并称有向边，并称有向边v 关联于关联于v vi i与与v vj j，或称有向，或称有向边边v 与顶点与顶点v vi i和和v vj j相关联。相关

10、联。三、度、入度、出度在图中，一个顶点的在图中，一个顶点的度度就是与该顶点相关联的就是与该顶点相关联的边的数目，顶点边的数目，顶点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为始为始点的边的数目称为点的边的数目称为v v的的出度出度，记为，记为ODOD（v v），有向），有向图中顶点的度数等于顶点的入度

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

12、 j的的子图子图。v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示例子图示例（a a）无向图）无向图GG3 3的部分子图的部分子图（b b）有向图）有向图GG4 4的部分子图的部分子图 五、路径 无无向向图图GG中中若若存存在在着着一一个个顶顶点点序序列列v v、v v1 1、v v2 2、v vmm、u u，且且（v v，v v1 1）、（v v1 1，v v2 2）、（v vmm，u u）均均属属于于E E（GG），则则称称该该顶顶点点序序列列为为顶顶点点v v到到顶顶点点u u的的一一条条路路径径，相相应应地地，顶顶点点序序列列u u、v vmm、v

13、 vm-1m-1、v v1 1、v v是顶点是顶点u u到顶点到顶点v v的一条路径。的一条路径。如如果果GG是是有有向向图图，路路径径也也是是有有向向的的，它它由由E E（GG）中中的的有有向向边边v、v、vu组组成。成。路径长度路径长度是该路径上边或弧的数目。是该路径上边或弧的数目。如果一条路径上除了起点如果一条路径上除了起点v v和终点和终点u u相同外，其余相同外，其余顶点均不相同，则称此路径为一条顶点均不相同，则称此路径为一条简单路径简单路径。起点和。起点和终点相同（终点相同（v=uv=u）的简单路径称为）的简单路径称为简单回路简单回路或或简单环简单环。六、连通图与强连通图在无向图在

14、无向图GG中，若从顶点中，若从顶点v vi i到顶点到顶点v vj j有路径，则有路径，则称称v vi i与与v vj j是连通的。若是连通的。若V V（GG）中任意两个不同的顶）中任意两个不同的顶点点v vi i和和v vj j都连通（即有路径），则称都连通（即有路径），则称GG为为连通图连通图。例。例如，图如，图1.11.1（b b）所示的无向图）所示的无向图GG2 2、图、图7.27.2（a a）所示）所示的无向图的无向图GG3 3是都是连通图。是都是连通图。无向图无向图GG的极大连通子图称为的极大连通子图称为GG的的连通分量连通分量。根据连通分量的定义，可知任何连通图的连通分量根据连通

15、分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。是其自身，非连通的无向图有多个连通分量。例：非连通图及其连通分量示例例：非连通图及其连通分量示例（a a）非连通图）非连通图GG5 5（b b）GG5 5的两个连通分量的两个连通分量H H1 1和和H H2 2在有向图在有向图GG中，若对于中，若对于V V（GG）中任意两个不同的）中任意两个不同的顶点顶点v vi i和和v vj j，都存在从，都存在从v vi i到到v vj j以及从以及从v vj j到到v vi i的路径，则称的路径，则称GG是是强连通图。强连通图。V1V2V4V5V3V1V2V4V5V3有向图的极

16、大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分分量是其自身，而非强连通的有向图有多个强连分量。例如，图量。例如，图1.21.2（b b）所示的有向图）所示的有向图GG4 4是一个具有是一个具有4 4个顶点的强连通图，图个顶点的强连通图，图8.58.5（a a）所示的有向图）所示的有向图GG6 6不是强连通图（不是强连通图（v v2 2、v v3 3、v v4 4没有到达没有到达v v1 1的路径），的路径），它的两个强连通分量它的两个强

17、连通分量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 七、网络有时在图的每条边上附上相关的数值，这种与有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫图的边相关的数值叫权权。权可以表示两个顶点之间的距离、耗费等具有权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则某种意义的数。若将图的每条边都赋上一个权，则称

18、这种带权图为网络。称这种带权图为网络。V0V1V3V234567825V0V2V1455064（a a）无向网络）无向网络GG7 7（b b）有向网络）有向网络GG8 8图的基本运算 图图是是一一种种复复杂杂数数据据结结构构，由由图图的的定定义义及及图图的的一一组组基基本操作构成了图的抽象数据类型。本操作构成了图的抽象数据类型。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）定定义义

19、了边（或弧）（了边（或弧）（v v，w w）的信息）的信息 图的基本操作如下：图的基本操作如下：（1 1）creatgraphcreatgraph（&g&g）创建一个图的存储结构。创建一个图的存储结构。（2 2）insertvertexinsertvertex（&g&g，v v）在在图图g g中中增增加加一一个个顶顶点点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

20、g中中增增加加一一条条从从顶点顶点v v到顶点到顶点u u的边或弧。的边或弧。（5 5）deleteedgedeleteedge（&g&g，v v，u u）在在图图g g中中删删除除一一条条从从顶点顶点v v到顶点到顶点u u的边或弧。的边或弧。（6 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）degreede

21、gree（g g，v v）求图求图g g中顶点中顶点v v的度数。的度数。（1010）nextvertexnextvertex（g g，v v，w w）求求图图g g中中与与顶顶点点v v相相邻邻接接的的顶顶点点w w的的下下一一个个邻邻接接点点。即即求求图图g g中中顶顶点点v v的的某某个个邻邻接接点点，它它的的存存储储顺顺序序排排在在邻邻接接点点w w的的存存储储位位置之后。置之后。ADTGraphADTGraph图的基本存储结构 图的存储结构至少要保存两类信息：图的存储结构至少要保存两类信息：1)1)顶点的数据顶点的数据 2)2)顶点间的关系顶点间的关系约定约定:G=G=是图是图,V=

22、v,V=v0 0,v,v1 1,v,v2 2,v,vn-1n-1,设顶点的设顶点的角标为它的编号角标为它的编号 如何表示顶点间的关系？如何表示顶点间的关系？V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3邻接矩阵及其实现给定图给定图G=G=（V V，E E），其中），其中V V（GG）=v=v0 0，v vi i，v vn-1n-1，GG的邻接矩阵（的邻接矩阵（AdacencyMatrixAdacencyMatrix）是）是具有如下性质的具有如下性质的n n阶方阵：阶方阵：无向图的邻接矩阵是对称的，有向图的邻接矩无向图的邻接矩阵是对称的，有向图的邻接矩阵

23、可能是不对称的。阵可能是不对称的。一、非网络的邻接矩阵一、非网络的邻接矩阵v0v1v3v2v3v1v0v2图的邻接矩阵示例图的邻接矩阵示例0111011110101010110111011010101001000100101010101100110001000100A1=A1=A2=A2=图图2.7 2.7 无向图无向图G G9 9及有向图及有向图G G1010的邻接矩阵表示的邻接矩阵表示 用邻接矩阵表示图，很容易判定任意两个顶点用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点无向图，顶点v vi i的

24、度数是邻接矩阵中第的度数是邻接矩阵中第i i行或第行或第i i列值列值为为1 1的元素个数，即：的元素个数，即：D D（v vi i）=（2-22-2）对于有向图，邻接矩阵中第对于有向图，邻接矩阵中第i i行值为行值为1 1的元素个的元素个数为顶点数为顶点v vi i的出度，第的出度，第i i列值为列值为1 1的元素的个数为顶的元素的个数为顶点点v vi i的入度，即：的入度，即：ODOD（v vi i）=;ID=;ID（v vi i）=（2-32-3）二、网络的邻接矩阵二、网络的邻接矩阵当当G=G=（V V，E E）是一个网络时，）是一个网络时，GG的邻接矩阵是具的邻接矩阵是具有如下性质的有

25、如下性质的n n阶方阵：阶方阵：WWij ij 当（当（v vi i，v vj j）或）或v E E（GG）00当（当（v vi i，v vj j）或）或vEE（GG）且）且i=ji=j当（当（v vi i，v vj j）或）或vEE（GG）且）且ijijAiAi，j=j=其中其中WWij ij表示边上的权值；表示边上的权值；表示一个计算机允表示一个计算机允许的、大于所有边上权值的数。许的、大于所有边上权值的数。V0V1V3V234567825V0V2V1455064网络的邻接矩阵示例网络的邻接矩阵示例056347805634785605603402534025782507825000550

26、0045045640640A A3 3=A A4 4=（a a）GG7 7的邻接矩阵的邻接矩阵（b b）GG8 8的邻接矩阵的邻接矩阵图图2.82.8网络邻接矩阵示例网络邻接矩阵示例邻接矩阵存储结构邻接矩阵存储结构#defineFINITY5000/*#defineFINITY5000/*此处用此处用50005000代表无穷大代表无穷大*/*/#definem20/*#definem20/*最大顶点数最大顶点数*/*/typedefcharvertextype;/*typedefcharvertextype;/*顶点值类型顶点值类型*/*/typedefintedgetype;/*typede

27、fintedgetype;/*权值类型权值类型*/*/typedefstructtypedefstructvertextypevexsm;/*vertextypevexsm;/*顶点信息域顶点信息域*/*/edgetypeedgesmm;/*edgetypeedgesmm;/*邻接矩阵邻接矩阵*/*/intn,e;/*intn,e;/*图中顶点总数与边数图中顶点总数与边数*/*/mgraph;/*mgraph;/*邻接矩阵表示的图类型邻接矩阵表示的图类型*/*/文件名文件名:mgraph.h:mgraph.h/*/*/*/*图的邻接矩阵创建算法图的邻接矩阵创建算法*/*/*/*文件名：文件名：

28、c_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)scanf

29、(%d%d,&g-n,&g-e);/*;/*输入图的顶点数与边数输入图的顶点数与边数*/*/getchar();/*getchar();/*取消输入的换行符取消输入的换行符*/*/printf(pleaseinputvexs:n);printf(pleaseinputvexs:n);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=

30、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,&wscanf(%d%d%d,&i,&j,&w););g-edgesij=w;g-edgesij=w;/*/*若是建立无向网，只需在此加入语句若是建立无向网，只需在此加入语句g-

31、edgesji=w;g-edgesji=w;即可即可*/*/说明说明:当建立有向网时，边信息以三元组（当建立有向网时，边信息以三元组（i i，j j，w w）的形的形式输入，式输入，i i、j j分别表示两顶点的序号，分别表示两顶点的序号，w w表示边上的权。表示边上的权。对于每一条输入的边信息（对于每一条输入的边信息（i i，j j，w w），），只需将只需将g-g-edgesijedgesij赋值为赋值为w w。算法中用到的算法中用到的creatmgraph2()creatmgraph2()是用于建立无向网络是用于建立无向网络的函数，它与的函数，它与creatmgraph1()creatm

32、graph1()的区别在于对每一条输的区别在于对每一条输入的边信息（入的边信息（i i，j j，w w），），需同时将需同时将g-edgesijg-edgesij和和g-g-edgesjiedgesji赋值为赋值为w w。当建立非网络的存储结构时，所有的边信息只需按当建立非网络的存储结构时，所有的边信息只需按二元组（二元组（i i，j j）的形式输入。的形式输入。邻接表 用邻接矩阵表示法存储图，占用的存储单元个用邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。数只与图中顶点的个数有关，而与边的数目无关。一个含有一个含有n n个顶点的图，个顶点的图，如果其边数比

33、如果其边数比n n2 2少得多，少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储那么它的邻接矩阵就会有很多空元素，浪费了存储空间。空间。n n无向图的邻接表无向图的邻接表对于图对于图GG中的每个顶点中的每个顶点v vi i，该方法把所有邻接于该方法把所有邻接于v vi i的顶点的顶点v vj j链成一个带头结点的单链表，这个单链表就链成一个带头结点的单链表，这个单链表就称为顶点称为顶点v vi i的邻接表。单链表中的每个结点至少包含的邻接表。单链表中的每个结点至少包含两个域，一个为两个域，一个为邻接点域邻接点域（adjvexadjvex），），它指示与顶点它指示与顶点v vi i邻接的顶点

34、在图中的位序，另一个为邻接的顶点在图中的位序，另一个为链域链域（nextnext），），它指示与顶点它指示与顶点v vi i邻接的下一个结点。邻接的下一个结点。adjvex nextadjvex nextvertex firstdegevertex firstdege为了便于随机访问任一顶点的邻接表，可将所为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接有头结点顺序存储在一个向量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。放在一起来描述图的存储结构。v0v1v3v2无向

35、图无向图GG9 91 2 3 0 2 0 1 3 0 2 V0V1V2V3GG9 9的邻接表的邻接表表头结点表头结点结构结构边结点结边结点结构构对于无向图，对于无向图，v vi i的邻接表中每个表结点都对应于的邻接表中每个表结点都对应于与与v vi i相关联的一条边；对于有向图来说，如果每一顶相关联的一条边；对于有向图来说，如果每一顶点点v vi i的邻接表中每个表结点都存储以的邻接表中每个表结点都存储以v vi i的为始点射出的为始点射出的一条边，则称这种表为有向图的的一条边，则称这种表为有向图的出边表出边表（有向图的（有向图的邻接表），反之，若每一顶点邻接表），反之，若每一顶点v vi i

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

37、个数是顶点的结点个数是顶点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 2G9G9的邻接表的邻接表邻接表的存储结构邻接表的存储结构/*/*/*/*邻接表存储结构邻接表存储结构文件名：文件名：adjgraph.h*

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

39、efstructvnode/*typedefstructvnode/*头结点类型头结点类型*/*/datatypevertex;/*datatypevertex;/*顶点信息顶点信息*/*/edgenode*firstedge;/*edgenode*firstedge;/*邻接链表头指针邻接链表头指针*/*/vertexnode;vertexnode;typedefstruct/*typedefstruct/*邻接表类型邻接表类型*/*/vertexnodeadjlistm;/*vertexnodeadjlistm;/*存放头结点的顺序表存放头结点的顺序表*/*/intn,e;/*intn,e

40、;/*图的顶点数与边数图的顶点数与边数*/*/adjgraph;adjgraph;vertex firstdegevertex firstdege头结点结头结点结构构/*/*/*/*无向图的邻接表创建算法无向图的邻接表创建算法*/*/*/*文件名文件名c_ljb.cc_ljb.c函数名：函数名：createadjgraph()*/createadjgraph()*/*/*/voidcreateadjgraph(adjgraph*g)voidcreateadjgraph(adjgraph*g)inti,j,k;inti,j,k;edgenode*s;edgenode*s;printf(Pleas

41、einputnande: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);for(i=0;in;i+)for(i=0;in;i+)scanf(“%c”,&g-adjlisti.vertex);/*scanf(“%c”,&g-adjlisti.vertex);/*读入顶点信息读入顶点

42、信息*/*/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(sizeof(edgenode);s=(e

43、dgenode*)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的边表头部的边表头部*/*/s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)malloc(sizeof(edgenode);s-adj

44、vex=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的边表头部的边表头部*/*/建立无向图的邻接表算法建立无向图的邻接表算法说明：一个图的邻接矩阵表示是唯一的，但其邻接表说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点表示不唯一，这是因为在邻接表结构中，各边表结点的

45、链接次序取决于建立邻接表的算法以及边的输入次的链接次序取决于建立邻接表的算法以及边的输入次序。序。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-0C 3-1-0D 2-0D 2-0图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，图的

46、遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组用一个辅助数组visitnvisitn作为对顶点的标记，当顶点作为对顶点的标记，当顶点vi vi未未被访问，被访问，visitivisiti值为值为0 0；当；当v vi i已被访问，则已被访问，则visitivisiti值为值为1 1。有两种遍历方法有两种遍历方

47、法（它们对无向图，有向图都适用）它们对无向图，有向图都适用）深度优先遍历深度优先遍历广度优先遍历广度优先遍历深度优先遍历从图中某顶点从图中某顶点v v出发：出发：1 1）访问顶点）访问顶点v v；2 2）依次从）依次从v v的未被访问的邻接点出发，继续对图进行深的未被访问的邻接点出发，继续对图进行深度优先遍历；度优先遍历；对对于于给给定定的的图图G=G=（V V，E E），首首先先将将V V中中每每一一个个顶顶点点都都标标记记为为未未被被访访问问，然然后后，选选取取一一个个源源点点v v V V，将将v v标标记记为为已已被被访访问问，再再递递归归地地用用深深度度优优先先搜搜索索方方法法，依依

48、次次搜搜索索v v的的所所有有邻邻接接点点w w。若若w w未未曾曾访访问问过过，则则以以w w为为新新的的出出发发点点继继续续进进行行深深度度优优先先遍遍历历，如如果果从从v v出出发发有有路路的的顶顶点点都都已已被被访访问问过过，则则从从v v的的搜搜索索过过程程结结束束。此此时时，如如果果图图中中还还有有未未被被访访问问过过的的顶顶点点（该该图图有有多多个个连连通通分分量量或或强强连连通通分分量量），则则再再任任选选一一个个未未被被访访问问过过的的顶顶点点，并并从从这这个个顶顶点点开开始始做做新新的的搜搜索索。上上述述过过程程一一直进行到直进行到V V中所有顶点都已被访问过为止。中所有顶

49、点都已被访问过为止。V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4例例序列序列1 1：V0,V1,V3,V7,V4,V2,V5,V6深度优先遍历过程：深度优先遍历过程：由于没有规定由于没有规定访问邻接点的顺序，访问邻接点的顺序，深度优先序列不是唯一的深度优先序列不是唯一的序列序列2 2：V0,V1,V4,V7,V3,V2,V5,V6c0c1c3c2c4c5c0c1c3c2c4c5DFSDFS序列：序列：c c0 0 cc1 1 cc3 3 cc4 4 cc5 5 cc2 2但是，当采

50、用邻接表存储结构并且存储结构已确但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。定的情况下，遍历的结果将是确定的。采用邻接表存储结构的深度优先遍历算法实现：采用邻接表存储结构的深度优先遍历算法实现：/*/*/*/*图的深度优先遍历算法图的深度优先遍历算法*/*/*/*文件名：文件名：dfs.cdfs.c函数名：函数名：dfs()dfs()、dfstraverse()*/dfstraverse()*/*/*/intvisitedm;intvisitedm;voiddfs(adjgraphg,inti)voiddfs(adjgraphg,inti)/*/*以以v vi