《《数据结构(C语言版)》 第08章.ppt》由会员分享，可在线阅读，更多相关《《数据结构(C语言版)》 第08章.ppt（135页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第章图图的基本概念图的基本概念 图的基本运算图的基本运算 生成树与最小生成树生成树与最小生成树 拓扑排序拓扑排序 图的基本存储结构图的基本存储结构 最短路径最短路径关键路径关键路径 图的遍历图的遍历8.1图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：它可以形式化地表示为：图（图（V V，E E）其中其中V=x|xV=x|x 某个数据对象集某个数据对象集，它是顶点的有，它是顶点的有穷非空集合；穷非空集合；E=E=（x x，
2、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，y y）表示从）表示从x x到到y y的一条的一条单向通路。单向通路。图的应用举例图的应用举例例例1 1 交通图（公路、铁路）交通图（公路、铁路）顶点：地点顶点：地点 边：连接地点的公路边：连接地点的公路 交通图中的有单行道双行道，分别用有向边、无向边表示；交通图中的有单行道双行道，分别用有向边、无向边表示；V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3
3、例例2 2 电路图电路图 顶点：元件顶点：元件 边：连接元件之间的线路边：连接元件之间的线路例例3 3 通讯线路图通讯线路图 顶点：地点顶点：地点 边：地点间的连线边：地点间的连线例例4 4 各种流程图各种流程图 如产品的生产流程图如产品的生产流程图 顶点：工序顶点：工序 边：各道工序之间的顺序关系边：各道工序之间的顺序关系 通通常常，也也将将图图GG的的顶顶点点集集和和边边集集分分别别记记为为V V（GG）和和E E（GG）。E E（GG）可可以以是是空空集集，若若E E（GG）为为空空，则图则图GG只有顶点而没有边。只有顶点而没有边。若图若图GG中的每条边都是有方向的，则称中的每条边都是有
4、方向的，则称GG为为有向有向图图。在有向图中，一条有向边是由两个顶点组成的有。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对序对，有序对通常用尖括号表示。例如，有序对v 表示一条由表示一条由v vi i到到v vj j的有向边。有向边又称为的有向边。有向边又称为弧弧，弧，弧的始点称为的始点称为弧尾弧尾，弧的终点称为，弧的终点称为弧头弧头。若图。若图GG中的每中的每条边都是没有方向的，则称条边都是没有方向的，则称GG为为无向图无向图。无向图中的。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。边均是顶点的无序对，无序对通常用圆括号表示。图图8-18-1
5、v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）无向图）无向图G G2 2 图图8.18.1（a a）表表示示的的是是有有向向图图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为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；边或弧；例：图例：图8-18-1v1v2v3v4v1v2v4v5v3（a a）有向图）有向图G G1 1（b b）
6、无向图）无向图G G2 2 图图8.18.1（b b）表表示示的的是是无无向向图图GG2 2，该该图图的的顶顶点点集集和和边集分别为：边集分别为：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的线段的线段表示，称为无向边；表示，称为无向边；
7、在以后的讨论中，我们约定：在以后的讨论中，我们约定：（1 1）一一条条边边中中涉涉及及的的两两个个顶顶点点必必须须不不相相同同，即即：若若（v vi i，v vj j）或或v 是是E E（GG）中中的的一一条条边边，则则要要求求v vi ivvj j；（2 2）一对顶点间不能有相同方向的两条有向边；）一对顶点间不能有相同方向的两条有向边；（3 3）一一对对顶顶点点间间不不能能有有两两条条无无向向边边，即即只只讨讨论论简简单的图。单的图。若用若用n n表示图中顶点的数目，用表示图中顶点的数目，用e e表示图中边的表示图中边的数目，按照上述规定，容易得到下述结论：对于一数目，按照上述规定，容易得到
8、下述结论：对于一个具有个具有n n个顶点的无向图，其边数个顶点的无向图，其边数e e小于等于小于等于n n（n-n-1 1）/2/2，边数恰好等于，边数恰好等于n n（n-1n-1）/2/2的无向图称为的无向图称为无向无向完全图完全图；对于一个具有；对于一个具有n n个顶点的有向图，其边数个顶点的有向图，其边数e e小于等于小于等于n n（n-1n-1），边数恰好等于），边数恰好等于n n（n-1n-1）的有向）的有向图称为图称为有向完全图有向完全图。也就是说完全图具有最多的边。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。数，任意一对顶点间均有边相连。二、完全图例：图例：图8-28
9、-2v1v2v3v4v1v2v3v4（a a）无向完全图）无向完全图GG3 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互为互为邻接点邻接点。若若v 是一条有向边，则称是一条有向边，则称v vi i邻接到邻接到v vj j，v
10、vj j邻邻接于接于v vi i，并称有向边，并称有向边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的的入度入度，记为，
11、记为IDID（v v）；把以顶点）；把以顶点v v为始为始点的边的数目称为点的边的数目称为v v的的出度出度，记为，记为ODOD（v v），有向），有向图中顶点的度数等于顶点的入度与出度之和，即图中顶点的度数等于顶点的入度与出度之和，即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=（
12、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 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 v
13、mm，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组成。组成。路径长度路径长度是该路径上边或弧的数目。是该路径上边或弧的数目。如果一条路径上除了起点如果一条路径上除了起点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.2（a a）所示）所示的无
15、向图的无向图GG3 3是都是连通图。是都是连通图。无向图无向图GG的极大连通子图称为的极大连通子图称为GG的的连通分量连通分量。根据连通分量的定义，可知任何连通图的连通分量根据连通分量的定义，可知任何连通图的连通分量是其自身，非连通的无向图有多个连通分量。是其自身，非连通的无向图有多个连通分量。例：非连通图及其连通分量示例例：非连通图及其连通分量示例（a a）非连通图）非连通图GG5 5（b b）GG5 5的两个连通分量的两个连通分量H H1 1和和H H2 2在有向图在有向图GG中，若对于中，若对于V V（GG）中任意两个不同的）中任意两个不同的顶点顶点v vi i和和v vj j，都存在从
16、，都存在从v vi i到到v vj j以及从以及从v vj j到到v vi i的路径，则称的路径，则称GG是是强连通图。强连通图。V1V2V4V5V3V1V2V4V5V3有向图的极大强连通子图称为有向图的极大强连通子图称为GG的强连通分量。的强连通分量。根据强连通图的定义，可知强连通图的唯一强连通根据强连通图的定义，可知强连通图的唯一强连通分量是其自身，而非强连通的有向图有多个强连分分量是其自身，而非强连通的有向图有多个强连分量。例如，图量。例如，图8.28.2（b b）所示的有向图）所示的有向图GG4 4是一个具有是一个具有4 4个顶点的强连通图，图个顶点的强连通图，图8.58.5（a a）
17、所示的有向图）所示的有向图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 七、网络有时在图的每条边上附上相关的数值，这种与有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫图的边相关的数
18、值叫权权。权可以表示两个顶点之间的距离、耗费等具有权可以表示两个顶点之间的距离、耗费等具有某种意义的数。若将图的每条边都赋上一个权，则某种意义的数。若将图的每条边都赋上一个权，则称这种带权图为网络。称这种带权图为网络。V0V1V3V234567825V0V2V1455064（a a）无向网络）无向网络GG7 7（b b）有向网络）有向网络GG8 8作业：作业：8.18.1对于无向图对于无向图8.298.29，试给出，试给出（1 1）图中每个顶点的度；）图中每个顶点的度；（2 2）该图的邻接矩阵；）该图的邻接矩阵；（4 4）该图的连通分量。）该图的连通分量。v0v3v4v2v1v5v6图图8.2
19、98.29无向图无向图8.2 8.2 给定有向图给定有向图8.308.30，试给出，试给出（1 1）顶点）顶点D D的入度与出度；的入度与出度；（2 2）该图的出边表与入边表；）该图的出边表与入边表；（3 3）该图的强连通分量。）该图的强连通分量。ABCDE图图8.308.30有向图有向图8.2图的基本运算 图图是是一一种种复复杂杂数数据据结结构构，由由图图的的定定义义及及图图的的一一组组基基本操作构成了图的抽象数据类型。本操作构成了图的抽象数据类型。ADTGraphADTGraph数数据据对对象象V V：V V是是具具有有相相同同特特性性的的数数据据元元素素的的集集合合，称称为顶点集。为顶点
20、集。数据关系数据关系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）的信息）的信息 图的基本操作如下：图的基本操作如下：（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
21、 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的边或弧。的边或弧。（6 6）travetrave（g g）遍历图遍历图g g。（7 7）locatevertexlocatevertex（g g，v v）求求顶顶点点v v在在图图g g中中的的位位序。序。（8 8）fiirstvertexfii
22、rstvertex（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中中顶顶点点v v的的某某个个邻邻接接点点，它它的的存存储储顺顺序序排排在在邻邻接接点点w w的的存存储储位位置之后。置之后。ADTGraphADTGraph8.3图的基本存储结构 图的存储结构至少要保存两类
23、信息：图的存储结构至少要保存两类信息：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 V3V38.3.1邻接矩阵及其实现给定图给定图G=G=（V V，E E），其中），其中V V（GG）=v=v0 0，v vi i，v vn-1n-1，GG的邻接矩阵（的邻接矩阵（AdacencyMatrixAdacencyMatri
24、x）是）是具有如下性质的具有如下性质的n n阶方阵：阶方阵：无向图的邻接矩阵是对称的，有向图的邻接矩无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。阵可能是不对称的。一、非网络的邻接矩阵一、非网络的邻接矩阵v0v1v3v2v3v1v0v2图的邻接矩阵示例图的邻接矩阵示例0111011110101010110111011010101001000100101010101100110001000100A1=A1=A2=A2=图图8.7 8.7 无向图无向图G G9 9及有向图及有向图G G1010的邻接矩阵表示的邻接矩阵表示 用邻接矩阵表示图，很容易判定任意两个顶点用邻接矩阵表示图，很容易
25、判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。对于之间是否有边相连，并求得各个顶点的度数。对于无向图，顶点无向图，顶点v vi i的度数是邻接矩阵中第的度数是邻接矩阵中第i i行或第行或第i i列值列值为为1 1的元素个数，即：的元素个数，即：D D（v vi i）=（8-28-2）对于有向图，邻接矩阵中第对于有向图，邻接矩阵中第i i行值为行值为1 1的元素个的元素个数为顶点数为顶点v vi i的出度，第的出度，第i i列值为列值为1 1的元素的个数为顶的元素的个数为顶点点v vi i的入度，即：的入度，即：ODOD（v vi i）=;ID=;ID（v vi i）=（8-8-3 3
26、）二、网络的邻接矩阵二、网络的邻接矩阵当当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（GG）且）且i=ji=j当（当（v vi i，v vj j）或）或vEE（GG）且）且ijijAiAi，j=j=其中其中WWij ij表示边上的权值；表示边上的权值；表示一个计算机允表示一个计算机允许的、大于所有边上权值的数。许的、大于所有边上权值的数。V0V1V3V234567825V0V2
27、V1455064网络的邻接矩阵示例网络的邻接矩阵示例056347805634785605603402534025782507825000550 0045045640640A A3 3=A A4 4=（a a）GG7 7的邻接矩阵的邻接矩阵（b b）GG8 8的邻接矩阵的邻接矩阵图图8.88.8网络邻接矩阵示例网络邻接矩阵示例邻接矩阵存储结构邻接矩阵存储结构#defineFINITY5000/*#defineFINITY5000/*此处用此处用50005000代表无穷大代表无穷大*/*/#definem20/*#definem20/*最大顶点数最大顶点数*/*/typedefcharvertex
28、type;/*typedefcharvertextype;/*顶点值类型顶点值类型*/*/typedefintedgetype;/*typedefintedgetype;/*权值类型权值类型*/*/typedefstructtypedefstructvertextypevexsm;/*vertextypevexsm;/*顶点信息域顶点信息域*/*/edgetypeedgesmm;/*edgetypeedgesmm;/*邻接矩阵邻接矩阵*/*/intn,e;/*intn,e;/*图中顶点总数与边数图中顶点总数与边数*/*/mgraph;/*mgraph;/*邻接矩阵表示的图类型邻接矩阵表示的图类
29、型*/*/文件名文件名:mgraph.h:mgraph.h/*/*/*/*/*图图的的邻邻接接矩矩阵阵创创建建算算法法 */*/*/*文件名：文件名：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;/*建立有向网络的邻接矩阵存储结构建立有向网络的邻接矩阵存储结构*/*/pri
30、ntf(pleaseinputnande:n);printf(pleaseinputnande:n);scanf(%d%d,&g-n,&g-e)scanf(%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=get
31、char();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;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
32、%d,&i,&j,&w););g-edgesij=w;g-edgesij=w;/*/*若是建立无向网，只需在此加入语句若是建立无向网，只需在此加入语句g-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。算法算法8.58.5中用到
33、的中用到的creatmgraph2()creatmgraph2()是用于建立无向网是用于建立无向网络的函数，它与络的函数，它与creatmgraph1()creatmgraph1()的区别在于对每一条的区别在于对每一条输入的边信息（输入的边信息（i i，j j，w w），），需同时将需同时将g-edgesijg-edgesij和和g-edgesjig-edgesji赋值为赋值为w w。当建立非网络的存储结构时，所有的边信息只需按当建立非网络的存储结构时，所有的边信息只需按二元组（二元组（i i，j j）的形式输入。的形式输入。8.3.2邻接表及其实现 用邻接矩阵表示法存储图，占用的存储单元个用
34、邻接矩阵表示法存储图，占用的存储单元个数只与图中顶点的个数有关，而与边的数目无关。数只与图中顶点的个数有关，而与边的数目无关。一个含有一个含有n n个顶点的图，如果其边数比个顶点的图，如果其边数比n n2 2少得多，少得多，那么它的邻接矩阵就会有很多空元素，浪费了存储那么它的邻接矩阵就会有很多空元素，浪费了存储空间。空间。n n无向图的邻接表无向图的邻接表对于图对于图GG中的每个顶点中的每个顶点v vi i，该方法把所有邻接于该方法把所有邻接于v vi i的顶点的顶点v vj j链成一个带头结点的单链表，这个单链表就链成一个带头结点的单链表，这个单链表就称为顶点称为顶点v vi i的邻接表。单
35、链表中的每个结点至少包含的邻接表。单链表中的每个结点至少包含两个域，一个为两个域，一个为邻接点域邻接点域（adjvexadjvex），），它指示与顶点它指示与顶点v vi i邻接的顶点在图中的位序，另一个为邻接的顶点在图中的位序，另一个为链域链域（nextnext），），它指示与顶点它指示与顶点v vi i邻接的下一个结点。邻接的下一个结点。adjvex nextadjvex nextvertex firstdegevertex firstdege为了便于随机访问任一顶点的邻接表，可将所为了便于随机访问任一顶点的邻接表，可将所有头结点顺序存储在一个向量中就构成了图的邻接有头结点顺序存储在一个向
36、量中就构成了图的邻接表存储。最后将图的顶点数及边数等信息与邻接表表存储。最后将图的顶点数及边数等信息与邻接表放在一起来描述图的存储结构。放在一起来描述图的存储结构。v0v1v3v2图图8.78.7无向图无向图GG9 91 2 3 0 2 0 1 3 0 2 V0V1V2V3图图8.9G8.9G9 9的邻接表的邻接表表头结点表头结点结构结构边结点结边结点结构构对于无向图，对于无向图，v vi i的邻接表中每个表结点都对应于的邻接表中每个表结点都对应于与与v vi i相关联的一条边；对于有向图来说，如果每一顶相关联的一条边；对于有向图来说，如果每一顶点点v vi i的邻接表中每个表结点都存储以的邻
37、接表中每个表结点都存储以v vi i的为始点射出的为始点射出的一条边，则称这种表为有向图的的一条边，则称这种表为有向图的出边表出边表（有向图的（有向图的邻接表），反之，若每一顶点邻接表），反之，若每一顶点v vi i的邻接表中每个表结的邻接表中每个表结点都对应于以点都对应于以v vi i为终点的边（即射入为终点的边（即射入v vi i的边），则称的边），则称这种表为有向图的这种表为有向图的入边表入边表（又称逆邻接表）。（又称逆邻接表）。v0v1v2v31 0 2 0 1 1 GG1010的出边表的出边表v0v1v2v3 1 2 0 2 1 3 GG1010的入边表的入边表v3v1v0v2图图8
38、.7(b)8.7(b)有向图有向图GG1010在无向图的邻接表中，顶点在无向图的邻接表中，顶点v vi i的度为第的度为第i i个链表中个链表中结点的个数；而在有向图的出边表中，第结点的个数；而在有向图的出边表中，第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
39、 0 2 0 1 1 GG1010的出边表的出边表V V0 0的出度为的出度为1 1，入度为，入度为2 2邻接表的存储结构邻接表的存储结构/*/*/*/*/*邻接表存储结构邻接表存储结构文件名：文件名：adjgraph.h*/adjgraph.h*/*/*/*/#definem20/*#definem20/*预定义图的最大顶点数预定义图的最大顶点数*/*/typedefchardatatype;/*typedefchardatatype;/*顶点信息数据类型顶点信息数据类型*/*/typedefstructnode/*typedefstructnode/*边表结点边表结点*/*/intadjv
40、ex;/*intadjvex;/*邻接点邻接点*/*/structnode*next;structnode*next;edgenode;edgenode;adjvex nextadjvex next边结点结边结点结构构typedefstructvnode/*typedefstructvnode/*头结点类型头结点类型*/*/datatypevertex;/*datatypevertex;/*顶点信息顶点信息*/*/edgenode*firstedge;/*edgenode*firstedge;/*邻接链表头指针邻接链表头指针*/*/vertexnode;vertexnode;typedefst
41、ruct/*typedefstruct/*邻接表类型邻接表类型*/*/vertexnodeadjlistm;/*vertexnodeadjlistm;/*存放头结点的顺序表存放头结点的顺序表*/*/intn,e;/*intn,e;/*图的顶点数与边数图的顶点数与边数*/*/adjgraph;adjgraph;vertex firstdegevertex firstdege头结点结头结点结构构/*/*/*/*/*无无向向图图的的邻邻接接表表创创建建算算法法 */*/*/*文件名文件名c_ljb.cc_ljb.c函数名：函数名：createadjgraph()*/createadjgraph()*
42、/*/*/*/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();getchar();printf(Pleaseinput%dvertex:,g-n);printf(Pleaseinput
43、%dvertex:,g-n);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:,g-e);printf(Pleaseinput%dedges:,g-e);for(k=0;ke;k+)/*for(k=0;ke;k+)/*循环循环e e
44、次建立边表次建立边表*/*/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-adjlisti.firstedge;s-next=g-adjlisti.firstedge;g-adjlisti.firstedge=s;g-adjlisti.firstedge=s;/*
45、将将新新结结点点*s*s插插入入顶顶点点v vi i的边表头部的边表头部*/*/s=(edgenode*)malloc(sizeof(edgenode);s=(edgenode*)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的边表头部的边表头部
46、*/*/算法算法8.28.2建立无向图的邻接表算法建立无向图的邻接表算法说明：一个图的邻接矩阵表示是唯一的，但其邻接表说明：一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，这是因为在邻接表结构中，各边表结点表示不唯一，这是因为在邻接表结构中，各边表结点的链接次序取决于建立邻接表的算法以及边的输入次的链接次序取决于建立邻接表的算法以及边的输入次序。序。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
47、.c时如果输入的信息为：时如果输入的信息为：则将建立如下的邻接表存储结构。则将建立如下的邻接表存储结构。A 3-2-1A 3-2-1B 2-0B 2-0C 3-1-0C 3-1-0D 2-0D 2-08.3.3邻接多重表n n在邻接多重表中，每一条边只有一个边结点。为有关在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。边的处理提供了方便。边结点的结构边结点的结构 mark vexi linki vexj linkj 其中，其中，mark mark 是记录是否处理过的标记；是记录是否处理过的标记；vexivexi和和vexjvexj是依附于该边的两顶点位置。是依附于该边的两顶点
48、位置。lnikilniki域是链接指针，域是链接指针，指向下一条依附于顶点指向下一条依附于顶点vexivexi的边；的边；linkjlinkj也是链接指针，也是链接指针，指向下一条依附于顶点指向下一条依附于顶点vexjvexj的边。需要时还可设置一的边。需要时还可设置一个存放与该边相关的权值的域个存放与该边相关的权值的域 cost cost。顶点结点的结构顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，一个顶点结点有两个数据成员：其中，vertex vertex 存放存放与该顶点相关的信息，与该顶点相关的信息，f
49、irstedgefirstedge 是指示第一条依是指示第一条依附于该顶点的边的指针。附于该顶点的边的指针。在邻接多重表中在邻接多重表中,所有依附于同一个顶点的所有依附于同一个顶点的边都链接在同一个单链表中。边都链接在同一个单链表中。从顶点从顶点 i i 出发出发,可以循链找到所有依附于该顶可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。vertex FirstedgeV0V1V3V234567825V0V1V2V356013402780325230123无向网络的邻接多重表示例无向网络的邻接多重表示例其中边表结点增加了一个存储权值的数据域其中
50、边表结点增加了一个存储权值的数据域。8.4图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组用一个辅助数组visitnvisitn作为对顶点的标记，当顶点作为对顶点的标记，当顶点vi vi未被访问，未被访问，visitivisiti值为值为0 0；当；当v