数据结构课件一讲

第七章图

本章介绍另一种非线性数据结构——

图 图：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。

第一讲图的概念和存储结构第二讲图的遍历第三讲生成树第四讲拓扑排序和关键路径第五讲最短路径1．熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系；

2．熟练掌握图的两种遍历：深度优先遍历和广度优先遍历的算法；

3．理解各种图的算法。

学习要点:

第一讲

图的概念存储结构一、图的定义

图G由两个集合构成，记作G=<V,E>其中V是顶点的非空有限集合，E是边的有限集合，其中边是顶点的无序对或有序对集合。G1=<V,E>V={v0,v1,v2,v3,v4}E={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}G1图示无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；例

V0

V4

V3

V1

V2

图的概念G2图示有序对<vi,vj>：用以vi起点、以vj为终点的有向线段表示，称为有向边或弧；称vi为弧尾，vj为弧头无向图：在图G中，若所有边是无向边，则称G为无向图；有向图：在图G中，若所有边是有向边，则称G为有向图；混和图：在图G中，既有无向边也有有向边，则称G为混合图；

V0

V1

V2

V3G2=<V,E>V={v0v1,v2,v3}E={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>}1、邻接点及关联边邻接点：边的两个顶点,v、u互为邻接点关联边：若边e=(v,u),则称顶点v、u

关联边e2、顶点的度、入度、出度

在无向图中：顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度

e二、图的基本术语

V0

V4

V3

V1

V2

V0

V1

V2

V33、完全图、权、网有向完全图——具有n(n-1)条弧的n个顶点的有向图称为~

无向完全图——有n(n-1)/2

条边的n个顶点的无向图称为~

权——与图的边或弧相关的数叫~

网——带权的图叫~例213213有向完全图无向完全图例14523753186424、路径和回路

路径：从一个顶点到另一顶点所经过的顶点序列。如：A，B，E，D

路径长度：路径上的边数。

回路：若一条路径上的起点和终点相同，这条路径就叫回路。如：B，C，B

简单路径：无重复顶点的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点之外，其余的顶点不重复出现的回路。ABCDE012345、连通图（强连通图）

在无（有）向图G=<V,E>中，若对任何两个顶点v、u

都存在从v到u

的路径，则称G是连通图（强连通图）

非连通图

连通图

强连通图

非强连通图

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V46、子图

设有两个图G=（V，E）、G1=（V1，E1），若V1

V，E1

E，则称G1是G的子图；

例

(b)、(c)

是(a)

的子图(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V27、连通分量（强连通分量）

无向图G

的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；连通分量非连通图

V0

V2

V3

V1

V5

V4有向图D

的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的；强连通分量

V0

V1

V2

V3

V0

V2

V3

V18、生成树包含无向图G所有顶点的的极小连通子图称为G的生成树极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件

T是G的连通子图

T包含G的所有顶点

T中无回路连通图G1G1的生成树

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2T1是G1的生成树例245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}例213213有向完全图无向完全图例245136G1顶点2入度：出度：顶点4入度：

出度：例157324G26顶点5的度：顶点2的度：341310例157324G26例245136G1路径：1，2，3，5，6，3路径长度：简单路径：

1，2，3，5，6，3，13，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：回路：1，2，5，7，6，5，2，1简单回路：51，2，3，5，6回路：简单回路：1，2，5，7，61，2，3，1连通图例245136强连通图356例非连通图连通分量例245136356例245136图与子图图的存储结构例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3一、多重链表邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G2

二、数组表示法

如何表示顶点间的关系？？网的邻接矩阵可定义为：例1452375318642

邻接矩阵表示法中图的存储表示#definen6/*图的顶点数*/#definee8/*图的边数*/typedefcharvextype;/*顶点的数据类型*/typedeffloatadjtype;/*权值类型*/typedefstruct{vextypevexs[n];adjtypearcs[n][n];}graph;21435BADCE21534000000000000000000000000=807080705040503040203020arcs6203050407080邻接矩阵表示法中无向网络的建立算法CREATEGRAPH(graph*ga){inti,j,k;floatw;for(i=0;i<n;i++)ga->vexs[i]＝getchar();/*读入顶点信息，建立顶点表*/

for(i=0;i<n;i++)for(j=0;j<n;j++)ga->arcs[i][j]＝0;/*邻接矩阵初始化*/

for(k=0;k<e;k++){scanf(“%d%d%f”,&i,&j,&w);/*读入e条边上的权*/ga->arcs[i][j]＝w;ga->arcs[j][i]＝w;}}例1452375318642

3、邻接表实现：顶点：通常按编号顺序将顶点数据存储在一维数组中；关联同一顶点的边：用线性链表存储。即为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边例aecbdG21234acdbvexdatafirstarc4212^^^adjvexnext5e435^15323^该结点表示边（ViVj）,其中的2是Vj在一维数组中的位置例G1bdac1234acdbvexdatafirstarc341^^^^2adjvexnext头结点：typedefstructtnode{intvexdata;//存放顶点信息

structnode*firstarc;//指示第一个邻接点}TD;TDga[M];//ga[0]不用vexdatafirstarc表结点：typedefstructnode{intadjvex;//邻接点域，存放与Vi邻接的点在表头数组中的位置

structnode*next;//链域，指示下一条边或弧的指针}JD;adjvexnext特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数判定两顶点v,u是否邻接：要看v对应线性链表中有无对应的结点u在G中增减边：要在两个单链表插入、删除结点；设存储顶点的一维数组大小为m(m

图的顶点数n),图的边数为e，G占用存储空间为：m+2*e。G占用存储空间与G的顶点数、边数均有关；适用于边稀疏的图例aecbdG21234acdbvexdatafirstarc4212^^^adjvexnext5e435^15323^逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnext顶点：用一维数组存储（按编号顺序）以同一顶点为终点的弧：用线性链表存储4、有向图的十字链表表示法弧结点：typedefstructarcnode{inttailvex,headvex;//弧尾、弧头在表头数组中位置

structarcnode*hlink；//指向弧头相同的下一条弧

structarcnode*tlink;//指向弧尾相同的下一条弧}AD;tailvexheadvexhlinktlink顶点结点：typedefstructdnode{intdata;//存与顶点有关信息

structarcnode*firstin；//指向以该顶点为弧头的第一个弧结点

structarcnode*firstout;//指向以该顶点为弧尾的第一个弧结点}DD;DDg[M];//g[0]不用datafirstin