数据结构与算法(吴跃)ch4-1)

1、4.1 图图引子引子右图为一个新兴小镇右图为一个新兴小镇.其中其中3个红色小块为社区房屋个红色小块为社区房屋, 1个个白色小块为商店白色小块为商店. 现在要铺现在要铺设天然气管道设天然气管道, 造价和天然造价和天然气管长度成正比气管长度成正比. 如何铺设如何铺设管道使得所有房屋和商店都管道使得所有房屋和商店都通气且造价最低通气且造价最低? 4.1 图图引子引子问题1: 造价和管线长度成正比,如何表示管线长度?4.1 图图引子引子问题2: 如何以最少连线连通所有房屋和商店?问题3: 如何连通所有房屋和商店且造价最低?4.1 图图引子引子问题4: 如何用计算机技术解决现实中大量社区的最优化管道铺设

2、问题?4.1 图图引子引子思路现实问题图形化: 社区(房屋,商店)为点, 连通的点之间用线表示,点之间距离(管线长度)用权值表示,得到一个有权图计算机存储图形数据: 存储点,线,权值最优管线问题分析: 求连通图的最小权值和解决算法思路: ? 4.1 图图引子引子深入思考:有哪些解决方案? 哪个方案更优? 如何分析算法优劣?这种解决方案还可以解决哪种类型的实际问题?4.1 图的定义和术语v图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对v有向图有向图G是由两个集合V(G)和E(G)组成的

3、 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头v无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)例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), (2,4),(2,5), (5,6), (5,7)v有向完全图

4、n个顶点的有向图最大边数是n(n-1)v无向完全图n个顶点的无向图最大边数是n(n-1)/2v权与图的边或弧相关的数叫v网带权的图叫v子图如果图G(V,E)和图G(V,E),满足：lVVlEE 则称G为G的子图v邻接点对于无向图G(V,E),如果边(v,v) E,则称v和v互为邻接点。即：v和v相邻接。v依附边(v,v) 依附于顶点v和v。v相关联边(v,v) 和顶点v和v相关联。v顶点的度l无向图中，顶点的度为与每个顶点相连的边数l有向图中，顶点的度分成入度与出度u入度：以该顶点为头的弧的数目u出度：以该顶点为尾的弧的数目v如果顶点vi的度记为TD(vi)，则有n个顶点，e条边或弧的图，满足

5、：v路径路径是顶点的序列V=Vi0,Vi1,Vin，满足(Vij-1,Vij)E 或 E,(1jn)niivTD1)(21ev路径长度沿路径边的数目或沿路径各边权值之和v回路/环第一个顶点和最后一个顶点相同的路径叫v简单路径序列中顶点不重复出现的路径叫v简单回路/简单环除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫v连通在无向图中，从顶点V到顶点W有一条路径，则说V和W是连通的v连通图图中任意两个顶点都是连通的叫v连通分量非连通图的每一个连通部分叫v强连通图有向图中，如果对每一对（Vi,Vj）V, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是v强连通分量有向图中的极

6、大强连通子图叫v生成树一个连通图的生成树是一个极小连通子图，它含有图中的全部顶点，但只有足以构成一棵树的n-1条边例213213有向完全图无向完全图356例245136图与子图例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例157324G26顶点5的度：3顶点2的度：4例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：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，1连通图例2451

7、36强连通图356例非连通图例2451364.2 图的存储结构多重链表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3邻接矩阵表示顶点间相联关系的矩阵v定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵，其它0E(G)v,v或)v,(v若1,jijijiA例G12413例15324G200110001011101010101010100001100000000110v特点：l无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2l有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nl无向图中顶点Vi的

8、度TD(Vi)是邻接矩阵A中第i行元素之和l有向图中，u顶点Vi的出度是A中第i行元素之和u顶点Vi的入度是A中第i列元素之和l网络的邻接矩阵可定义为：ijij,(v ,v )v ,vE(G) , ijA i j若或，其它5735487214263816例1452375318642关联矩阵表示顶点与边的关联关系的矩阵v定义：设G=(V,E)是有n1个顶点，e0条边的图，G的关联矩阵A是具有以下性质的ne阶矩阵为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：ijijiijijiA, 1, 0, 1,边不相连顶点与，边相连顶点与，无向图：jijijiA01,1100011000011

9、0114321例G124131234例15324G2123456110000000110011100101001000011432156例BDAC123456ABCD432156101011110000011100000111v特点l关联矩阵每列只有两个非零元素，是稀疏矩阵；n越大，零元素比率越大l无向图中顶点Vi的度TD(Vi)是关联矩阵A中第i行元素之和l有向图中，u顶点Vi的出度是A中第i行中“1”的个数u顶点Vi的入度是A中第i行中“-1”的个数邻接表v实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）typedef struct

10、 node int adjvex; /邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next; /链域，指示下一条边或弧JD;adjvex next表头接点：typedef struct tnode int vexdata; /存放顶点信息 struct node *firstarc; /指示第一个邻接点TD;TD gaM; /ga0不用vexdata firstarc例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex nex

11、t5e 4 3 5 1 5 3 2 3v特点l无向图中顶点Vi的度为第i个单链表中的结点数l有向图中u顶点Vi的出度为第i个单链表中的结点个数u顶点Vi的入度为整个单链表中邻接点域值是i的结点个数l逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next邻接矩阵与邻接表的对比 对于n个顶点、e条边，邻接矩阵需要nn矩阵（有向图） 或n（n+1）/2(无向图压缩存储)个存储单元，邻接表需要n个头节点和2e个表节点（无向图），有向图需要n个头节点和e个表节点。在边稀疏情况下（en(n-1)/2），邻接

12、表比邻接矩阵节省存储空间。要判定任意两个顶点（vi和vj）之间是否有边或弧相连，邻接表需要搜索第i个或第j个链表，不如邻接矩阵方便。有向图的十字链表表示法弧结点：typedef struct arcnode int tailvex, headvex; /弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧 struct arcnode *tlink; /指向弧尾相同的下一条弧AD;tailvex headvex hlink tlink顶点结点：typedef struct dnode int data; /存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout; /指向以该顶点为弧尾的第一个弧结点DD;DD gM; /g0不用data firstin firstout例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1无向图的邻接多重表表示法顶点结点：typedef struct dnode int data; /存与顶点有关的信息 struct node *firstedge; /指向第一条依附于该顶点的边DD;DD gaM; /ga0不用data