数据结构第7章图

1、第七章 图7.1 图的定义和术语图的定义和术语v图图(Graph)图图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的,记为记为G=(V,E)其中：其中：V(G)是是顶点顶点的非空有限集的非空有限集 E(G)是是边边的有限集合，边是顶点的无序对或有序对的有限集合，边是顶点的无序对或有序对v有向图有向图有向图有向图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的 其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，是有向边（也称弧）的有限集合，弧是顶点的有序弧是顶点的有序对对，记为，记为，v,w是顶点，是顶点，v为为弧尾弧尾，w为为

2、弧头弧头。易知，易知，v无向图无向图无向图无向图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的 其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集 E(G)是边的有限集合，是边的有限集合，边是顶点的无序对边是顶点的无序对，记为，记为（v,w）或（或（w,v)，并且（，并且（v,w)=(w,v)，顶点，顶点v和顶点和顶点W互为互为邻接点邻接点例例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),

3、(2,4),(2,5), (5,6), (5,7)有序对有序对 ：用以为用以为vivi起点、以起点、以vjvj为终点为终点的有向线段表示，称为有向的有向线段表示，称为有向边或弧；边或弧；无序对无序对(vi,vj)(vi,vj)：用连接顶点用连接顶点vivi、vjvj的线段的线段表示，称为无向边；表示，称为无向边；v有向完全图有向完全图在一个有向图中，如果任意两顶点之在一个有向图中，如果任意两顶点之间都有间都有方向互为相反的两条弧相连接方向互为相反的两条弧相连接。即。即n个顶点的个顶点的有向图最大边数是有向图最大边数是n(n-1)v无向完全图无向完全图在一个无向图中，如果任意两顶点都在一个无向图

4、中，如果任意两顶点都有一条有一条直接边直接边相连接相连接即即n个顶点的无向图最大边数个顶点的无向图最大边数是是n(n-1)/2v权权与图的边或弧相关的数叫与图的边或弧相关的数叫v网网带权的图叫带权的图叫1 12 25 54 43 3176324 58B BC CA A21435v子图子图如果图如果图G(V,E)和图和图G(V,E),满足：满足：lV VlE E 则称则称G为为G的子图的子图v顶点的度顶点的度l无向图中，顶点的度为与每个顶点相连的边数无向图中，顶点的度为与每个顶点相连的边数l有向图中，顶点的度分成入度与出度有向图中，顶点的度分成入度与出度u入度入度：以该顶点为头的弧的数目：以该顶

5、点为头的弧的数目u出度出度：以该顶点为尾的弧的数目：以该顶点为尾的弧的数目v路径路径路径是顶点的序列路径是顶点的序列V=Vi0,Vi1,Vin，满足，满足(Vij-1,Vij) E 或或 E,(1j n)v路径长度路径长度沿路径边的数目或沿路径各边权值之和沿路径边的数目或沿路径各边权值之和v回路回路第一个顶点和最后一个顶点相同的路径叫第一个顶点和最后一个顶点相同的路径叫v简单路径简单路径序列中顶点不重复出现的路径叫序列中顶点不重复出现的路径叫v简单回路简单回路除了第一个顶点和最后一个顶点外，其除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫余顶点不重复出现的回路叫例例213213有向

6、完全图有向完全图无向完全图无向完全图356例例245136图与子图图与子图例例245136G1顶点顶点2入度：入度：1 出度：出度：3顶点顶点4入度：入度：1 出度：出度：0例例157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：4度数之和度数之和 = 边数边数的二倍的二倍（因为每个边（因为每个边“贡献贡献”了两个了两个度数）度数）性质性质: : 入度之和入度之和 = = 出出度之和度之和= = 边数边数结点的度数结点的度数: : TD(v) = TD(v) = ID(v)+OD(v)ID(v)+OD(v)例例157324G26例例245136G1路径：路径：1，2，3，5，6，3

7、路径长度：路径长度：5简单路径：简单路径：1，2，3，5,6回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，3路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，1v连通连通在无向图中，如果从一个顶点在无向图中，如果从一个顶点v vi i到另一个顶点到另一个顶点v vj j（ijij）有路径）有路径, ,则称顶点则称顶点v vi i和和v vj j是连通的是连通的v连通图连通图若图中任意两个顶点都是连通的，则称此无向若图中任意两个顶点都是连通的，则称

8、此无向图为连通图（图为连通图（Connected GraphConnected Graph），否则称为非连通图。），否则称为非连通图。v连通分量连通分量无向图中，极大的连通子图为该图的无向图中，极大的连通子图为该图的v显然，任何连通图的连通分量只有一个，即它本身，而非显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。连通图有多个连通分量。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4强连通图强连通图对于有向图来说，若图中任意一对顶点对于有向图来说，若图中任意一对顶点v vi i 和和v vj j（ijij）均

9、有从一个顶点）均有从一个顶点v vi i到另一个顶点到另一个顶点v vj j的路径，也的路径，也有从有从v vj j到到v vi i的路径，则称该有向图是。的路径，则称该有向图是。v强连通分量强连通分量有向图的极大强连通子图称为有向图的极大强连通子图称为。 V0V0 V1V1 V2V2 V3V3 V0V0 V1V1 V2V2 V3V3 V1V1 V0V0 V2V2 V3V3v生成树生成树包含连通图包含连通图G G的全部的全部n n个顶点的一个极小连通子个顶点的一个极小连通子图。它必定包含且仅包含图。它必定包含且仅包含G G的的n-1n-1条边。条边。 极小连通子图意思是：该子图是极小连通子图意

10、思是：该子图是G G 的连通子图，在该子的连通子图，在该子图中删除任何一条边，子图不再连通。图中删除任何一条边，子图不再连通。v生成森林生成森林非连通图的生成树则组成一个非连通图的生成树则组成一个。若图中有。若图中有n n个顶点，个顶点，m m个连通分量，则生成森林中有个连通分量，则生成森林中有n-mn-m条边。条边。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2若无向图若无向图G含有含有n个顶点，它的边的条数个顶点，它的边的条数若若n-1条边，条边， 则则G一定有环路一定有环路若若=n-1

11、条边，则条边，则G不一定就是连通不一定就是连通 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2n图的基本操作 1、CreatGraph(&G,V,E) 按按V和和E的定义构造图的定义构造图G。2、DestroyGraph(&G) 销毁图销毁图G。3、LocateVex(G, u) 若若G中存在顶点中存在顶点u，返回其在图中位置，否则返回，返回其在图中位置，否则返回-1。4、GetVex(G, v)在图中找到顶点在图中找到顶点v，并返回顶点，并返回顶点v的相关信息，否则返回的相关信息，否则返回空

12、。空。5、FirstAdjVex(G,v) 返回图中顶点返回图中顶点v的第一个邻接顶点，若没有，返回空。的第一个邻接顶点，若没有，返回空。6、NextAdjVex(G，v，w) 返回返回v的相对于的相对于w的下一个邻接顶点，若的下一个邻接顶点，若w是是v的最后一的最后一个邻接点，则返回空。个邻接点，则返回空。7、 AddVex(&G, v) 在图在图G中增添新顶点中增添新顶点v。8、 DelVex(&G, v) 在图在图G中，删除顶点中，删除顶点v及所有和其相关的边或弧。及所有和其相关的边或弧。9、 AddArc(&G, v, w) 在图在图G中增添一条从顶点中增添一条从顶点v到顶点到顶点w的

13、边或弧。的边或弧。10、DelArc(&G, v, w) 在图中删除一条从顶点在图中删除一条从顶点v到顶点到顶点w的边或弧。的边或弧。11、DFS (G, v) 在图在图G中，从顶点中，从顶点v出发深度优先遍历图。出发深度优先遍历图。12、BFS (G,v) 在图在图G中，从顶点中，从顶点v出发广度优先遍历图。出发广度优先遍历图。图的基本操作 图是一种结构复杂的数据结构，表现在不仅各图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包系也错综复杂。从图的定义可知，一个图的信息

14、包括两部分，即括两部分，即图中顶点的信息以及描述顶点之间的图中顶点的信息以及描述顶点之间的关系（边或者弧）的信息关系（边或者弧）的信息。因此无论采用什么方法。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方建立图的存储结构，都要完整、准确地反映这两方面的信息。面的信息。图通常有图通常有邻接矩阵、邻接表、邻接多重表和十邻接矩阵、邻接表、邻接多重表和十字链表字链表等表示方法。等表示方法。7.2 图的存储结构图的存储结构定义：定义：在邻接矩阵表示中，除了用在邻接矩阵表示中，除了用一维数组一维数组存放顶点本存放顶点本身信息外，还用身信息外，还用一个矩阵一个矩阵表示各个顶点之间的邻接关系

15、。这表示各个顶点之间的邻接关系。这个矩阵称为个矩阵称为邻接矩阵邻接矩阵。 假设图假设图G G(V, E)(V, E)有有n n个确定的顶点，即个确定的顶点，即V Vvv0 0,v,v1 1, , v vn-1n-1 ，则表示，则表示G G中各顶点相邻关系为一个中各顶点相邻关系为一个n nn n的矩阵，矩阵的矩阵，矩阵的元素为的元素为 ：1 1若（若（i,ji,j）E(G)E(G)或或i,ji,jE(G)E(G)0 0其它情形其它情形 若若G G是带权图是带权图，则邻接矩阵定义为：，则邻接矩阵定义为：w wij ij 若（若（i,ji,j）E(G)E(G)或或i,ji,jE(G)E(G) 其它情

16、形其它情形 其中，其中，w wijij表示边上的权值表示边上的权值；Aij= Aij= 邻接矩阵邻接矩阵表示表示顶点间顶点间相联关系的矩阵相联关系的矩阵例例G12413例例15324G2001100010111010101010101000011000000001105735487214263816例例1452375318642有有向向图图无无向向图图无无向向网网v特点：特点：l无向图中，无向图中，u无向图的邻接矩阵无向图的邻接矩阵对称对称，可压缩存储；有，可压缩存储；有n个个顶点的无向图需存储空间为顶点的无向图需存储空间为n(n+1)/2u无向图中顶点无向图中顶点Vi的度的度TD(Vi)是邻

17、接矩阵是邻接矩阵A中第中第i行或第行或第i列列非非0元元(非非元元)之和之和u矩阵中矩阵中非非0元元(非非元元)的个数的的个数的一半一半为图中为图中边的边的数目数目l有向图中，有向图中，u有向图邻接矩阵有向图邻接矩阵不一定对称不一定对称；有；有n个顶点的有个顶点的有向图需存储空间为向图需存储空间为nu顶点顶点Vi的出度是的出度是A中第中第i行中行中非非0元元(非非元元)元素元素之和之和u顶点顶点Vi的入度是的入度是A中第中第i列中列中非非0元元(非非元元)元素元素之和之和u矩阵中矩阵中 非非0元元(非非元元)的个数为图中的个数为图中弧的数目弧的数目容易实现图的操作，如：求某顶点的度、判断容易实

18、现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。顶点之间是否有边（弧）、找顶点的邻接点等等。 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间复杂度空间复杂度为为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点优点：邻接矩阵法邻接矩阵法缺点缺点：在图的邻接矩阵表示中在图的邻接矩阵表示中: :有一个记录各个顶点信息的有一个记录各个顶点信息的顶点表顶点表，用一个一维数组，用一个一维数组来实现来实现还有一个表示各个顶点之间关系的还有一个表示各个顶点之间关系的邻接矩阵邻接矩阵

19、用一个用一个二维数组实现二维数组实现#define MAX_VERTEX_NUM 20 /最大顶点个数最大顶点个数typedef struct VertexType vexsMAX_VERTEX_NUM； /顶点向量顶点向量 int arcs MAX_VERTEX_NUM MAX_VERTEX_NUM ； /邻接矩阵邻接矩阵 int vexnum，arcnum； /图的当前顶点数和弧数图的当前顶点数和弧数 MGraph; 邻接矩阵结构定义表示法邻接矩阵建立：邻接矩阵建立：void CreatGraph(MGraph &G)int i,j,k;scanf(“%d%d”,&G.n,&G.e); /

20、cinG.nG.e;for (i=0;iG.n;i+)scanf(“%c”,&G.vexsi);for (i=0;iG.n;i+)for (j=0;jG.n;j+)G.edgesij=0;for (k=0;kG.e;k+)scanf(“%d%d”,&i,&j);G.edgesij=1;/*建立有向图建立有向图G的邻接矩阵存储的邻接矩阵存储*/*输入顶点数和边数输入顶点数和边数*/*输入顶点信息，建立顶点表输入顶点信息，建立顶点表*/*初始化邻接矩阵初始化邻接矩阵*/*输入输入e条边，建立邻接矩阵条边，建立邻接矩阵*/*无向图？！无向图？！*/关联矩阵关联矩阵表示表示顶点与边顶点与边的关联关系的

21、矩阵的关联关系的矩阵v定义：设定义：设G=(V,E)是有是有n 1个顶点，个顶点，e 0条边的图，条边的图，G的关联矩阵的关联矩阵A是具有以下性质的是具有以下性质的n e阶矩阵阶矩阵为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：ijijiijijiA, 1, 0, 1,边不相连顶点与，边相连顶点与，无向图：jijijiA01,11000110000110114321例例G124131234例例15324G2123456110000000110011100101001000011432156例例BDAC123456ABCD43215610101111000001110000011

22、1v特点特点l关联矩阵每列只有两个非零元素，是稀疏矩阵；关联矩阵每列只有两个非零元素，是稀疏矩阵；n n越大，零元素比率越大越大，零元素比率越大l无向图中顶点无向图中顶点ViVi的度的度TD(Vi)TD(Vi)是关联矩阵是关联矩阵A A中第中第i i行行元素之和元素之和l有向图中，有向图中，u顶点顶点ViVi的出度是的出度是A A中第中第i i行中行中“1”“1”的个数的个数u顶点顶点ViVi的入度是的入度是A A中第中第i i行中行中“-1”“-1”的个数的个数邻接表邻接表 邻接表（邻接表（Adjacency List）是图的一种）是图的一种顺序存储与链式存储结合顺序存储与链式存储结合的存储

23、方法。的存储方法。 它包括两部分：一部分是单链表，用来它包括两部分：一部分是单链表，用来存放边的信息；另一部分是数组，主要用来存放边的信息；另一部分是数组，主要用来存放顶点本身的数据信息。存放顶点本身的数据信息。对图中每个顶点对图中每个顶点Vi建立一个单链表，链表中的结点表示依附建立一个单链表，链表中的结点表示依附于顶点于顶点Vi的的边（有向图中指边（有向图中指以以Vi为尾的弧为尾的弧），这个单链表就称），这个单链表就称为为顶点顶点 vi 的邻接表。的邻接表。每个链表结点为两个域：每个链表结点为两个域： 其中：邻接点域其中：邻接点域adjvex记载与顶点记载与顶点Vi邻接的顶点信息；邻接的顶点

24、信息； 指针域指针域next指向下一个与顶点指向下一个与顶点Vi邻接的结点邻接的结点再为每个链表附设一再为每个链表附设一个头结点个头结点，并将所有点的邻接表表头放，并将所有点的邻接表表头放到一个数组中。到一个数组中。 头结点结构为：头结点结构为：其中：顶点域其中：顶点域vexdata存放顶点信息（姓名、编号等）；存放顶点信息（姓名、编号等）； 表头指针表头指针firstedge指向链表的第一个结点。指向链表的第一个结点。顶点域顶点域表头指针表头指针vexdatafirstedge邻接点域邻接点域指针域指针域adjvexnext在无向图中在无向图中顶点：顶点：通常按编号顺序将顶点数据存储在一维数

25、组中；通常按编号顺序将顶点数据存储在一维数组中；与同一顶点关联的边：与同一顶点关联的边：用线性链表存储用线性链表存储特点：设无向图中特点：设无向图中顶点数为顶点数为n，边数为边数为e， 则它的邻接表需要则它的邻接表需要n个头结点和个头结点和2e个表结点个表结点。 顶点顶点Vi的度的度 TD（Vi）= 链表链表i中的表结点数。中的表结点数。 V0V0V4V4V3V3V1V1V2V20 0 V0V01 1 V1V12 2 V2V23 3 V3V34 4 V4V42 21 13 34 42 22 21 11 10 00 03 34 4在有向图中，在有向图中，第第i个链表中的结点个数是顶点个链表中的结

26、点个数是顶点vi的出度。的出度。特点：设有向图中特点：设有向图中顶点数为顶点数为n，弧数为弧数为e， 则则 需需n个表头结点个表头结点和和e 个表结点个表结点。 V0V0 V1V1 V2V2 V3V30 0 V0V01 1 V1V1 2 2 V2V23 3 V3V31 12 23 30 0用链表存储同一顶点为用链表存储同一顶点为起点起点的弧的弧typedef struct AdjList vertices; int vexnum, arcnum; int kind; ALGraph;图的结构定义图的结构定义(邻接表邻接表)typedef struct tnode int vexdata; /存

27、放顶点存放顶点vivi信息信息 ArcNode *firstarc; /指向单链表的第一个结点指向单链表的第一个结点 VNode;VNode AdjListMAX_VERTEX_NUM；vexdata firstarc顶点的结点结构顶点的结点结构P163链表中的结点结构链表中的结点结构typedef struct ArcNode int adjvex; /邻接点域，存放与邻接点域，存放与ViVi邻接的点在表头数组中的邻接的点在表头数组中的位置位置 struct node *next; /链域，指向下一个与顶点链域，指向下一个与顶点ViVi邻接的结点邻接的结点 InfoType *info /该

28、弧相关信息的指针该弧相关信息的指针 ArcNode ;adjvex info next例例G1bdac例例aecbdG21234acdbvexdatafirstarc 3 2 4 1adjvexnext1234acdbvexdatafirstarc 4 2 1 2adjvexnext5e 4 3 5 1 5 3 2 3所有结点存储于所有结点存储于一个表中一个表中每个结点拉出一个每个结点拉出一个邻接边链表邻接边链表(以此结以此结点为始点的所有邻点为始点的所有邻接点接点)有向图有向图无向图无向图v图图邻接表示例说明邻接表示例说明v特点特点l无向图中顶点无向图中顶点ViVi的度为第的度为第i i个单

29、链表中的结点数个单链表中的结点数l有向图中有向图中u顶点顶点ViVi的出度为第的出度为第i i个单链表中的结点个数个单链表中的结点个数u顶点顶点ViVi的入度为整个单链表中邻接点域值是的入度为整个单链表中邻接点域值是i i的结点个数（的结点个数（必须遍历整个邻接表必须遍历整个邻接表） 为了求入度的便利为了求入度的便利, , 可以建立逆邻接表可以建立逆邻接表, , 即链表为即链表为入边表入边表; ;v逆邻接表：逆邻接表：有向图中对每个结点建立有向图中对每个结点建立以以ViVi为头为头的弧的的弧的单链表单链表例例G1bdac1234acdbvexdatafirstarc 3 2 4 1adjvex

30、next原邻接表原邻接表出边表出边表以以a a为始点为始点的边链的边链1234acdbvexdatafirstarc 4 1 1 3adjvexnext逆邻接表逆邻接表以以a a为终点的为终点的边链边链入边表入边表G1bdac1从从无向图无向图的邻接表可以得到如下结论的邻接表可以得到如下结论 （1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有）所有链表链表中结点数目的一半为图中边数；中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e 。2从从有向图有向图的邻接表可以得到如下结论的邻接表可以得到如下结论（1）第）第i 个链表中结

31、点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有）所有链表链表中结点数目为图中弧数；中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e 。v 结论结论 从有向图的邻接表可知，从有向图的邻接表可知，不能求出顶点的入度不能求出顶点的入度。为此，我们可以另外建立有向图的逆邻接表，以便为此，我们可以另外建立有向图的逆邻接表，以便求出每一个顶点的入度。求出每一个顶点的入度。有向图的逆邻接表有向图的逆邻接表与邻接与邻接表类似，只是它是从入度考虑结点，而不是从出度表类似，只是它是从入度考虑结点，而不是从出度考虑结点。考虑结点。 3. 建立的邻接表建立的邻接表不是惟一不

32、是惟一的，与键盘输入边的的，与键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也顺序有关，输入的边的顺序不同，则得到的链表也不同。不同。v网网的邻接表示例说明的邻接表示例说明adjvex infonextarcdatafirstarc例：已知某网的邻接（出边）表，请画出该网络。例：已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的存储当邻接表的存储结构形成后，图结构形成后，图便唯一确定！便唯一确定！邻接表的邻接表的缺点：缺点：邻接表的邻接表的优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点； 判断两顶点间是否有边或弧，需搜判断两顶点间是否有边或

33、弧，需搜索两结点对应的单链表，没有邻接矩索两结点对应的单链表，没有邻接矩阵方便。阵方便。讨论：讨论：邻接表与邻接矩阵有什么异同之处？邻接表与邻接矩阵有什么异同之处？1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于该行中非零元素的个数。链表中结点个数等于该行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空

34、间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵邻接矩阵多用于多用于稠密图稠密图的存储（的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而；而邻接表邻接表多用于多用于稀疏图稀疏图的存储（的存储（enen2 2) )十字链表是将有向图的邻接表和逆邻接表结合起来的一十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构。种有向图链式存储结构。结点结构结点结构 有向图的每一条弧有一个弧结点，每一个顶点必有一个有向图的每一条弧有一个弧结点，每一个顶点必有一个顶点结点

35、，其结构为：顶点结点，其结构为： 弧结点弧结点顶点结点顶点结点tailvex: 指示弧尾顶点的位置；指示弧尾顶点的位置；headvex: 指示弧头顶点的位置；指示弧头顶点的位置；hlink:指向弧头相同的下一条弧；指向弧头相同的下一条弧；tlink: 指向弧尾相同的下一条弧指向弧尾相同的下一条弧.vertex: 存放顶点的有关信息存放顶点的有关信息firstin: 指向以该顶点为指向以该顶点为弧头弧头 的第一个弧结点；的第一个弧结点；firstout: 指向以该顶点为指向以该顶点为弧尾弧尾 的第一个弧结点。的第一个弧结点。tailvex headvexhlinktlinkvertexfirst

36、infirstout整体结构整体结构通过通过hlink将将弧头弧头相同的弧连在一个链表上；相同的弧连在一个链表上；通过通过tlink将将弧尾弧尾相同的弧连在一个链表上相同的弧连在一个链表上; hlink链和链和tlink链的头结点就是顶点结点链的头结点就是顶点结点有向图的十字链表十字链表表示法例例12 341234 1 3 1 2 3 4 3 1 4 3 4 2 4 1 1 14 43 32 2弧结点弧结点顶点结点顶点结点tailvex headvexhlinktlinkvertexfirstinfirstouttlinktlink有向图的十字链表存储结构：有向图的十字链表存储结构：#defi

37、ne MaxVerNum 20typedef struct ArcNode int tailvex,headvex;struct ArcNode * hlink,* tlink;InfoType info;ArcNode;typedef struct VexNode VertexType vertex;ArcNode * firstin, * firstout;VexNode;typedef struct VexNode xlist MaxVerNum;int vexnum,arcnum;OLGraph;/*弧的尾和头顶点的位置弧的尾和头顶点的位置*/*指向头相同和尾相同弧的链域指向头相同和尾

38、相同弧的链域 */*指向该顶点第一条入弧和出弧指向该顶点第一条入弧和出弧*/*顶点相关信息顶点相关信息 */*有向图的顶点数和弧数有向图的顶点数和弧数*/*表头数组表头数组*/*弧结点的结构类型弧结点的结构类型*/*顶点的结构类型顶点的结构类型*/*图的结构类型图的结构类型*/*弧的权值信息弧的权值信息 */邻接多重表是无向图的另一种链式存储结构。邻接多重表是无向图的另一种链式存储结构。每一个顶点有一个顶点结点，顶点结点结构为：每一个顶点有一个顶点结点，顶点结点结构为：图的每一条边有一个边结点，边结点的结构为：图的每一条边有一个边结点，边结点的结构为：其中：其中：vertex存放顶点的信息。存

39、放顶点的信息。 firstedge指向第一条依附于该顶点的边结点。指向第一条依附于该顶点的边结点。mark为标记域，用以标记该条边是否被处理过为标记域，用以标记该条边是否被处理过 。ivex 和和jvex为该边所依附的两个顶点。为该边所依附的两个顶点。 ilink指向下一条依附于顶点指向下一条依附于顶点ivex的边。的边。 jlink指向下一条依附于顶点指向下一条依附于顶点jvex 的边。的边。 vertexfirstedgeivexilinkjvexjlinkmark无向图的邻接多重表表示法图的邻接多重表数据类型描述：图的邻接多重表数据类型描述：#define MaxVerNum 20typ

40、edef enum unvisited,visited VisitIf;typedef struct EdgeNodeVisitIf mark;int ivex,jvex;struct EdgeNode *ilink, *jlink;EdgeNode;typedef struct VexNodeVertexType vertex;EdgeNode *fistedge;VexNode;typedef structVexNode adjmulistMaxVerNum;int vexnum,edgenum;AMLGraph;/*访问标记访问标记*/*该边依附的两个顶点的位置该边依附的两个顶点的位置*

41、/*指向依附这两个顶点的下一条边指向依附这两个顶点的下一条边*/*指向第一条依附该顶点的边指向第一条依附该顶点的边*/*无向图的当前顶点数和边数无向图的当前顶点数和边数*/*边结点的结构类型边结点的结构类型*/*顶点的结构类型顶点的结构类型*/*图的结构类型图的结构类型*/例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 2和树的遍历类似，图的遍历也是从某个顶点出发，和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。沿着某条搜索路径对图中所有顶点各作一次访问。图访问的四个难点：图访问的四个难点：首结点首结点 、非连通图非连通图

42、 、回路、多个相连顶点回路、多个相连顶点我们可以设置一个全局型标志数组我们可以设置一个全局型标志数组visited来标志某来标志某个顶点是否被访过，未访问的值为个顶点是否被访过，未访问的值为0，访问过的值为，访问过的值为1。根据搜索路径的方向不同，图的遍历有两种方法：根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索遍历和广度优先搜索遍历。深度优先搜索遍历和广度优先搜索遍历。 7.3 图的遍历深度优先遍历深度优先遍历(DFS)v1. 方法：方法：l从图的某一顶点从图的某一顶点V0V0出发，访问此顶点；出发，访问此顶点；l然后依次从然后依次从V0V0的未被访问的邻接点出发，深度优先遍的未被

43、访问的邻接点出发，深度优先遍历图，直至图中所有和历图，直至图中所有和V0V0相通的顶点都被访问到；相通的顶点都被访问到；l若此时图中尚有顶点未被访问，则另选图中一个未被若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止点都被访问为止SG1SG2SG3W1、W2和和W3 均为均为 V 的邻的邻接点，接点，SG1、SG2 和和 SG3 分分别为含顶点别为含顶点W1、W2和和W3 的子图。的子图。访问顶点访问顶点 V ;for (W1、W2、W3 ) 若若该邻接点该邻接点W未被访问未被访问， 则则从

44、它出发进行深度优先搜索遍历。从它出发进行深度优先搜索遍历。Vw1w3w2从上页的图解可见从上页的图解可见:1. 从深度优先搜索遍历连通图的过程类似于从深度优先搜索遍历连通图的过程类似于树的先根遍历树的先根遍历;解决的办法是解决的办法是:为每个顶点设立一个为每个顶点设立一个 “访问访问标志标志 visitedw”;2. 如何判别如何判别V的邻接点是否被访问？的邻接点是否被访问？例例V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7深度优先遍历深度优

45、先遍历从图中某顶点从图中某顶点v v出发出发： V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1访问顶点访问顶点v v；依次从依次从v v的的未被访问的邻接点未被访问的邻接点出发，对图进行深度优先遍历；出发，对图进行深度优先遍历；先序遍历先序遍历若树非空若树非空访问根结点；访问根结点；按照从左到右的顺序先序遍历根按照从左到右的顺序先序遍历根结点的每一棵子树。结点的每一棵子树。如果将图中顶点的如果将图中顶点的邻接点看作树中结点邻接点看作树中结点的孩子，图的深度优的孩子，图的深度优先遍历与树的先序遍先遍历与树的先序遍历是否很类似？历是否很类似？比较：比较：深度遍历：深

46、度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：深度遍历：V1V1 V2 V2 V4 V4 V8 V8 V3 V3 V6 V6 V7 V7 V5V5V6V6V1V1V2V2V4V4V5V5V3V3V7V7V8V8V1V1V2V2V4V4V5V5V3V3V7V7V6V6V8V8由于没有规定访问邻接点的顺序由于没有规定访问邻接点的顺序, ,深度优先序深度优先序列不是唯一的列不是唯一的 若若图是连通的或图是连通的或强连通的，则从图中某一个顶强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，点出发可以访问到图中所有顶点， 否则只能访问到一部分顶点，再否则只能访问到一部分顶点，再从

47、未被访问从未被访问的顶点的顶点中选一个顶点出发访问未被访问的顶点。中选一个顶点出发访问未被访问的顶点。 另外，没有规定访问邻接点的顺序另外，没有规定访问邻接点的顺序, , 从某一个从某一个顶点出发的遍历结果是顶点出发的遍历结果是不唯一不唯一的。的。结论：结论：【算法说明】【算法说明】 (1)(1)在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由 v v 出发，访问它的出发，访问它的任一邻接任一邻接顶点顶点 w1w1；(2)(2)再从再从 w1 w1 出发，访问与出发，访问与 w1w1邻接但还没有访问过的顶点邻接但还没有访问过的顶点 w2w2；(3)(3)然后再从然后再从 w2

48、 w2 出发，进行类似的访问，出发，进行类似的访问， 如此进行下去，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点直至到达所有的邻接顶点都被访问过的顶点 u u 为止。为止。(4)(4)接着，退回一步，退到接着，退回一步，退到前一次刚访问过的前一次刚访问过的顶点，看是否还顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶再退回一步进行搜索。重复上述过程，直到连通图中所

49、有顶点都被访问过为止。点都被访问过为止。 v深度优先遍历算法深度优先遍历算法l递归算法递归算法算法调用示例算法调用示例开始开始访问访问V0,置标志置标志求求V0邻接点邻接点有邻接点有邻接点w求下一邻接点求下一邻接点wV0W访问过访问过结束结束NYNYDFS开始开始标志数组初始化标志数组初始化i=1Vi访问过访问过DFSi=i+1i=Vexnums结束结束NNYY图的深度优先遍历的算法图的深度优先遍历的算法深度优先遍历的递归算法深度优先遍历的递归算法DFS从从某个顶点某个顶点出发的出发的深度优先遍历的递归算法深度优先遍历的递归算法void DFS(Graph G,int v) visit (v)

50、;visitedv=TRUE;for(w=FisrtAdjVertex (G,v);w; w=NextAdjVertex (G,v,w)if(!visitedw)DFS(G,w);/*访问访问v，标志位置位，标志位置位*/*w为为v的首个邻接点；的首个邻接点；w存在；存在；w赋值为赋值为v的下一个邻接点的下一个邻接点*/*对对v尚未访问的邻接顶点尚未访问的邻接顶点w递归调用递归调用DFS*/boolean visitedMaxVerNum;/访问标志数组访问标志数组void DFSTraverse(Graph G)/对图对图G作深度优先遍历作深度优先遍历for(v=0;vG.n;+v) /访问

51、标志数组初始化访问标志数组初始化visitedv=FALSE;for(v=0;vG.n;+v) /对尚未访问的顶点调用对尚未访问的顶点调用DFS if(!visitedv) DFS(G,v); 对对图的图的深度优先遍历的算法：深度优先遍历的算法：以以邻接矩阵邻接矩阵为存储结构的深度优先遍历算法为存储结构的深度优先遍历算法:0111100010000100100001001000001010000010011000010001100100000110 无向图的邻接矩阵无向图的邻接矩阵 3 1 2 4 5 7 6 8 无向图无向图 算法描述为下面形式：算法描述为下面形式：void DFS (MGr

52、aph G,int i) / 从顶点从顶点i 出发遍历出发遍历 int j; visit(i); /访问顶点访问顶点i visitedi=1; for(j=0; jadjlisti.vertex); visitedi=True; p=G-adjlisti.firstedge; while(p) if (!visitedp-adjvex) DFS (G,p-adjvex); p=p-next; /*以以Vi为起点对为起点对G进行进行DFS搜索搜索*/*访问顶点访问顶点Vi*/*取取Vi边表的头指针边表的头指针*/*依次搜索依次搜索Vi的邻接点的邻接点Vj=p-adjvex*/*若若Vj未访问，则

53、以未访问，则以Vj为起点为起点DFS搜索搜索*/*找找Vi的下一个邻接点的下一个邻接点*/图的邻接表存储结构图的邻接表存储结构 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V10 01 12 23 34 45 56 67 7V0V0V1V1V2V2V3V3V4V4V5V5V6V6V7V71 12 20 01 11 15 57 77 73 30 06 64 42 26 65 52 24 43 3V0V0V1V1V3V3V7V7V4V4V2V2V5V5V6V6例例:深度遍历：深度遍历：V0V1 V3 V7 V4 V2 V5 V6在遍历时，对图中每个顶点至多调用一次在遍

54、历时，对图中每个顶点至多调用一次DFS 函数，因函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，索。因此，遍历图的过程实质上是对每个顶点查找其邻接点遍历图的过程实质上是对每个顶点查找其邻接点的过程的过程。其耗费的时间则取决于所采用的存储结构。其耗费的时间则取决于所采用的存储结构。1、当用二维数组表示邻接矩阵图的存储结构时，查找、当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为每个顶点的邻接点所需时间为O（n） ，其中，其中n为图中顶点数。为图中顶点数。而且对所有顶点递归访问而且对所有顶点递归访问1次

55、，所以遍历图的时间复杂性为次，所以遍历图的时间复杂性为O(n2) 。2、当以邻接表作图的存储结构时，找邻接点所需时间、当以邻接表作图的存储结构时，找邻接点所需时间为为O（e），其中），其中e为无向图中边的数或有向图中弧的数。为无向图中边的数或有向图中弧的数。 由此，由此，当以邻接表作存储结构时，深度优先搜索遍历图当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为的时间复杂度为O（n+e）。）。 深度优先搜索的算法复杂度：深度优先搜索的算法复杂度： 广度优先遍历广度优先遍历(BFS)v 广度优先搜索遍历类似于树的按层次遍历广度优先搜索遍历类似于树的按层次遍历v 方法：方法：l 首先访问顶点

56、首先访问顶点i i，并将其访问标志置为已被访问，即，并将其访问标志置为已被访问，即visitedi=1visitedi=1；l 接着依次访问与顶点接着依次访问与顶点i i有边相连的所有顶点有边相连的所有顶点W1W1，W2W2，WtWt；l 然后再按顺序访问与然后再按顺序访问与W1W1，W2W2，WtWt有边相连又未曾访问有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止过的顶点；依此类推，直到图中所有顶点都被访问完为止 。 l 若此时图中尚有顶点未被访问，则另选图中一个未被访问若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访

57、的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止问为止即广度优先搜索遍历图的过程中以即广度优先搜索遍历图的过程中以vivi为起始点，由近至远，为起始点，由近至远，依次访问和依次访问和vivi有路径相通且路径长度为有路径相通且路径长度为1 1，2 2，的顶点。的顶点。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4在遍历过程中在遍历过程中所经过的路径所经过的路径求图求图G G中以中以V0V0起点的的广度优先序列：起点的的广度优先序列：V0,V1,V2,V3,V4,V5,V6,V7

58、V0,V1,V2,V3,V4,V5,V6,V7由于没有规定访问邻接由于没有规定访问邻接点的顺序点的顺序, ,广度优先序列不是广度优先序列不是唯一的唯一的例例:广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：广度遍历：V1 V2 V3 V4 V6 V7 V8 V5V6V6V1V1V2V2V4V4V5V5V3V3V7V7V8V8例例:V1V1V2V2V4V4V5V5V3V3V7V7V6V6V8V8从图中某顶点从图中某顶点vi出发：出发：访问顶点访问顶点vi vi ；访问访问vi vi 的所有未被访问的邻接点的所有未被访问的邻接点w w1 1,w,w2 2,w,wk k；

59、依次从这些邻接点依次从这些邻接点( (在步骤在步骤2 2中访问的顶点中访问的顶点) )出发，访问它们出发，访问它们的所有未被访问的邻接点的所有未被访问的邻接点; ; 依此类推，直到图中所有访问过依此类推，直到图中所有访问过的顶点的邻接点都被访问；的顶点的邻接点都被访问；为实现为实现 3)3)，需要保存在步骤，需要保存在步骤(2)(2)中访问的顶点，而且访中访问的顶点，而且访问这些顶点邻接点的顺序为：问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被先保存的顶点，其邻接点先被访问访问。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1v广度优先遍历算法（类似于树的

60、按层遍历）广度优先遍历算法（类似于树的按层遍历）在广度优先遍历算法在广度优先遍历算法中，需设置一队列中，需设置一队列Q Q，保，保存已访问的顶点，并控制存已访问的顶点，并控制遍历顶点的顺序。遍历顶点的顺序。开始开始访问访问V0,置标志置标志求求V邻接点邻接点ww存在吗存在吗V下一邻接点下一邻接点ww访问过访问过结束结束NYNYBFS初始化队列初始化队列V0入队入队队列空吗队列空吗队头队头V出队出队访问访问w,置标志置标志w入队入队NY从从连通连通图中某个顶图中某个顶点出发的点出发的广度优先广度优先遍历的递归算法遍历的递归算法v广度优先遍历算法广度优先遍历算法开始开始标志数组初始化标志数组初始化