《ch3-2图1-《软件技术基础》-教学课件.ppt》由会员分享，可在线阅读，更多相关《ch3-2图1-《软件技术基础》-教学课件.ppt（54页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.2 图3.2.1 图的基本概念3.2.2 图的存储结构3.2.3 图的遍历3.2.4 生成树和最小生成树3.2.5 小结13.2.1 图的基本概念v图(Graph)图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序 对或有序对23.2.1 图的基本概念v有向图有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是是顶点，v为弧尾，w为弧头例例245136有向图有向图G1G1图图G1中：中：V(G1)=1,2,3,4
2、,5,6 E(G1)=,33.2.1 图的基本概念v无向图无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)无向图无向图G2G21573246图图G2中：中：V(G2)=1,2,3,4,5,6,7 E(G2)=(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)4v权与图的边或弧相关的数叫v网图（网络）带权的图叫1452375318642网图6v子图如果图G(V,E)和图G(V,E),满足：lV VlE E 则称G为G的子图35624513
3、6图与子图图与子图7顶点的度v无向图中，顶点的度TD(Vi)为与Vi顶点相连的边数v有向图中，顶点的度分成入度ID(V)与出度OD(V)l入度ID(V)：以该顶点为头的弧的数目l出度OD(V)：以该顶点为尾的弧的数目例例例例2 24 45 51 13 36 6G1G1顶点顶点顶点顶点2 2入度入度入度入度ID(2)=1ID(2)=1 出度出度出度出度OD(2)=3OD(2)=3顶点顶点顶点顶点4 4入度入度入度入度ID(4)=1ID(4)=1 出度出度出度出度OD(4)=0OD(4)=0例例例例1 15 57 73 32 24 4G2G26 6顶点顶点顶点顶点5 5的度的度的度的度TD(5)=
4、3TD(5)=3顶点顶点顶点顶点2 2的度的度的度的度TD(2)=4TD(2)=4TD(2)=ID(2)+OD(2)=1+3=48v路径顶点vp到顶点vq之间的路径（path）是指顶点序列vp,vi1,vi2,vim,vq.。其中，（vp,vi1），(vi1,vi2)，,(vim,.vq)分别为图中的边。v路径长度沿路径边的数目或沿路径各边权值之和v回路第一个顶点和最后一个顶点相同的路径叫v简单路径序列中顶点不重复出现的路径叫v简单回路除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫G1245136路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3
5、，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，310v连通从顶点V到顶点W有一条路径，则说V和W是连通的v连通图图中任意两个顶点都是连通的叫连通图连通图24513611v生成树所谓连通图G的生成树，是G的包含其全部n 个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。l特点：u1）任意两顶点间有且仅有一条路经u2）在生成树中添加任意一条属于G的边必定会产生回路u3）若生成树中减少任意一条边，则必然成为非连通图 连通图连通图G GG G的生成树的生成树例例24513624513613（一）邻接矩阵表示顶点间相联关系的矩阵v定义：设G=(V,E)是有n 1个顶
6、点的图，G的邻接矩阵A是具有以下性质的n阶方阵G2153243.2.2 图的存储结构2413G115v特点：l有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为nl有向图中，u顶点Vi的出度是A中第i行元素之和u顶点Vi的入度是A中第i列元素之和邻接矩阵表示顶点间相联关系的矩阵 V1 V2 V3 V4 V1 0 0 1 0 V2 0 0 0 1 V3 0 0 0 1 V4 1 0 0 0入度 出度1 11 12 10 1V1V3V2V416v特点：l网图的邻接矩阵可定义为：邻接矩阵表示顶点间相联关系的矩阵 1452375318642网图网图18邻接矩阵的特点：若G为有向图，则：v有向图邻
7、接矩阵不一定对称；有n个顶点的有向图需存储空间为n；v顶点Vi的出度是A中第i 行元素之和；v顶点Vi的入度是A中第i 列元素之和；若G为无向图，则：v邻接矩阵A为对称矩阵，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2；v第行非元素的个数为顶点Vi的度，TD(Vi)。l l缺点：缺点：缺点：缺点：统计图中边的总数时，需按行按列逐个检测、代价大。统计图中边的总数时，需按行按列逐个检测、代价大。统计图中边的总数时，需按行按列逐个检测、代价大。统计图中边的总数时，需按行按列逐个检测、代价大。19图的邻接矩阵存储表示v用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数
8、组来存储顶点信息，另外还有图的顶点数和边数。#define MaxVertexNum 100 /*最大顶点数设为最大顶点数设为100*/typedef char VertexType;/*顶点类型设为字符型顶点类型设为字符型*/typedef int EdgeType;/*边的权值设为整型边的权值设为整型*/typedef struct VertexType vexsMaxVertexNum;/*顶点表顶点表*/EdeType edgesMaxVertexNumMaxVertexNum;/*邻接矩阵即边表邻接矩阵即边表*/int n,e;/*顶点数和边数顶点数和边数*/Mgragh;/*Mar
9、agh是以邻接矩阵存储的图类型是以邻接矩阵存储的图类型*/20（二）邻接表邻接表是一种顺序存储(顶点顺序表)与链式存储(边的单链表)结合的存储方法，类似于树的孩子链表表示法。实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧），再将所有点的邻接表表头放到数组中。adjvex next邻接点域 指针域边表边表3.2.2 图的存储结构21（二）邻接表顶点表顶点表：typedef struct tnode int vexdata;/存放顶点信息 EdgeNode *firstedge;/边表头指针VertexNode;vexdata firste
10、dge顶点域边表头指针顶点表顶点表边表边表typedef struct node int adjvex;/邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next;/链域，指示下一条边或弧EdgeNode;adjvex next邻接点域 指针域边表边表22例例aecbd无向图无向图G21234acdbvexdata firstarc 4 2 1 2adjvex next5e 4 3 5 1 5 3 2 3邻接表24v特点l无向图中顶点Vi的度为第i个单链表中的结点数邻接表aecbd无向图无向图G21234acdbvexdata firstarc 4 2 1 2adjv
11、ex next5e 4 3 5 1 5 3 2 326v逆邻接表：有向图中对每个顶点Vi建立以Vi为头的弧的单链表G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next图的存储结构28有向图的十字链表表示法typedef struct dnode int data;/存与顶点有关信息存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout;/指向以该顶点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点DD;DD gM;/g
12、0不用不用data firstin firstout顶点值域顶点值域指针域指针域指针域指针域顶点表节点结构顶点表节点结构顶点结点：3.2.2 图的存储结构29例例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1有向图的十字链表表示法31由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：v 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。v 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。v 在图结构中，如果有回路存在，那么
13、一个顶点被访问之后，有可能沿回路又回到该顶点。v 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。3.2.3 图的遍历32深度优先遍历(DFS)v方法：l从图的某一顶点V0出发，访问此顶点；l然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；l若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止3.2.3 图的遍历33例例V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V73.2.3 图的遍历V1
14、V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V734V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V53.2.3 图的遍历35广度优先遍历(BFS)v方法：l从图的某一顶点V0出发，访问此顶点，l再依次访问V0的各个未曾访问过的邻接点；l然后分别从这些邻接点出发，依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到；l若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止
15、38V1V2V4V5V3V7V6V8例例广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V6 V7 V8 V539对以邻接矩阵为存储结构的整个图G进行广度优先遍历实现的C语言描述 void BFSTraverseAL(MGraph*G)/*广度优先遍历以邻接矩阵存储的图广度优先遍历以邻接矩阵存储的图G*/int i;for(i=0;in;i+)visitedi=FALSE;/*标志向量初始化标志向量初始化*/for(i=0;in;i+)if(!visitedi)BFSM(G,i);/*vi未访问过，从
16、未访问过，从vi开始开始BFS搜索搜索*/*BFSTraverseAL*/40void BFSM(MGraph*G,int k)/*以以Vi为出发点，对邻接矩阵存储的图为出发点，对邻接矩阵存储的图G进行进行BFS搜索搜索*/int i,j;CirQueue Q;InitQueue(&Q);printf(visit vertex:V%cn,G-vexsk);/*访问原点访问原点Vk*/visitedk=TRUE;EnQueue(&Q,k);/*原点原点Vk入队列入队列*/while(!QueueEmpty(&Q)i=DeQueue(&Q);/*Vi出队列出队列*/for(j=0;jn;j+)/*
17、依次搜索依次搜索Vi的邻接点的邻接点Vj*/if(G-edgesij=1&!visitedj)/*若若Vj未访问未访问*/printf(visit vertex:V%cn,G-vexsj);/*访问访问Vj*/visitedj=TRUE;EnQueue(&Q,j);/*访问过的访问过的Vj入队列入队列*/*BFSM*/41生成森林：非连通图每个连通分量的生成树一起组成 非连通图的3.2.4 生成树生成树v定义：设E(G)为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G)，其中T(G)是遍历图过程中历经的边的集合；B(G)是剩余的边的集合。显然，
18、T(G)和图G中所有顶点一起构成连通图G的极小连通子图。按照3.2.1节的定义，它是连通图的一棵生成树 v深度优先生成树与广度优先生成树42V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树广度遍历广度遍历：V1 V2 V3 V4 V5 V6 V7 V843例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林44生成树v说明l一个图可以有许多棵不同的生成树l所有生成树具有以下共同特点：u生
19、成树的顶点个数与图的顶点个数相同u生成树是图的极小连通子图u一个有n个顶点的连通图的生成树有n-1条边u生成树中任意两个顶点间的路径是唯一的u在生成树中再加一条边必然形成回路l含n个顶点n-1条边的图不一定是生成树45V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8无向图无向图G G和它的生成树和它的生成树V1V2V4V5V3V7V6V8无向图无向图G G对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n1条边。46最小生成树要在要在n n个城市间建立通信联络网，个城市间建立通信联络网，顶点顶点表示城市表示城市权权城市间
20、建立通信线路所需花费代价城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小该通信网所需花费的总代价）最小最小代价生成树最小代价生成树v问题分析1654327131791812752410n n个城市间，最多可设置个城市间，最多可设置n(n-1)/2n(n-1)/2条线路条线路n n个城市间建立通信网，只需个城市间建立通信网，只需n-1n-1条线路条线路问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择n-1n-1条，能把所有城市（顶点）条，能把所有城市（顶点）均连起来
21、，且总耗费（各边权值之和）最小均连起来，且总耗费（各边权值之和）最小v问题提出如果无向图是一个网图，它的所有生成树中必有一棵边的权值总和最小的生成树，这棵生成树为最小生成树47v构造最小生成树方法l方法一：普里姆(Prim)算法u算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合Y初始令U=u0,(u0 V),TE=Y在所有u U,v V-U的边(u,v)E中，找一条代价最小的边(u0,v0)Y将(u0,v0)并入集合TE，同时v0并入UY重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树48v构造最小生成树方法l方法一：普里姆(Prim)算法13116314164
22、3142116432142516543214253551654326136642549l方法二：克鲁斯卡尔(Kruskal)算法u算法思想：设连通网N=(V,E)，令最小生成树Y初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量Y在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边Y依此类推，直至T中所有顶点都在同一连通分量上为止例例165432651356642516543212345v构造最小生成树方法51小结1、理解图的基本概念2、掌握图的存储结构:邻接矩阵 与 邻接表3、掌握图的遍历(深度优先遍历 和 广度优先遍历)4、掌握构造最小生成树的方法:Prim算法 和 Kruskal算法54