首页计算机计算机基础数据结构 06 第六章 图.pptx

06 第六章 图.pptx

页数:69页文件大小:2.10 MB来源: 数据结构ppt课件

本课件为数据结构第六章图,先给出图的定义、基本术语与连通性概念,介绍邻接矩阵、邻接表与十字链表等存储结构及深度优先、广度优先遍历,随后讲解最小生成树的Prim与Kruskal算法,最后介绍拓扑排序、关键路径以及Dijkstra与Floyd最短路径算法。

第六章图目录页,列出图的定义术语、存储结构、遍历、生成树、拓扑排序与最短路径
哥尼斯堡七桥问题示意图,引出图论起源并说明一次走遍七桥的判定难题
多叉路口交通灯管理页,说明顶点间关系任意时的存储与顶点染色操作
查看本课件的文字版(共 69 页,供检索与复制)

第1页:第六章图目录

实例图的定义和术语图的存储结构本章小结第六章图图的遍历生成树图论的起源拓扑排序最短路径课后作业

第2页:图论的起源:七桥问题

十八世纪,有一座古老而美丽的城市叫做哥尼斯堡(今俄罗斯加里宁格勒)。布勒格尔河的两条支流在这里汇合,然后横贯全城,流入大海。河心有一个小岛。河水把城市分成了4块,于是,人们建造了7座各具特色的桥,把哥尼斯堡连成一体。当时那里的居民都热衷于一种游戏:看谁能从某点出发一次走遍这七座桥,每座桥只走一次,最后回到原出发点。在众多尝试者中竟无一人成功。ABCD图论的起源——哥尼斯堡七桥问题ABCD瑞士数学家欧拉(Leonhard Euler,1707—1783)

第3页:实例:多叉路口交通灯管理

多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED1.顶点数任意,顶点之间关系任意2.如何存储3.数据操作:顶点染色(遍历与找邻接点)图的应用实例

第4页:实例:公园导游问题

公园导游问题1.顶点数任意,顶点之间关系任意2.如何存储3.数据操作:任意两点之间最短路径入口图的应用实例

第5页:图的定义和术语

图(Graph)
由两个集合V(G)和VR(G)组成,记为G=(V,VR)其中:V(G)是顶点的非空有限集VR(G)是边的有限集合,边是顶点的有序对或无序对
有向图(Digraph)
由两个集合V(G)和VR(G)组成其中:V(G)是顶点的非空有限集VR(G)是有向边(即弧)的有限集合,弧是顶点的有序对,记<v,w>,v为弧尾(Tail),w为弧头(Head)
无向图(Undigraph)
由两个集合V(G)和VR(G)组成其中:V(G)是顶点的非空有限集VR(G)是边的有限集合,边是顶点的无序对,记(v,w)或(w,v),并且(v,w)=(w,v)图的定义和术语

第6页:有向图与无向图举例

例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(G2)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}图的定义和术语

第7页:完全图与度

有向完全图
n个顶点的有向图最大边数是n(n-1)
无向完全图
n个顶点的无向图最大边数是n(n-1)/2;
权
与图的边或弧相关的数
网
带权的图
子图
如果图G(V,VR)和图G‘(V’,VR‘),满足: V’ V并且VR’ VR则称G‘为G的子图;
邻接点
顶点v和顶点w之间存在一条边,则称v和w互为邻接点;边(v,w)和顶点v和w相关联 顶点的度 无向图中,顶点的度为与每个顶点相连的边数 有向图中,顶点的度分成入度与出度 入度:以该顶点为头的弧的数目 出度:以该顶点为尾的弧的数目;示例图的定义和术语

第8页:路径与连通

路径
路径是顶点的序列V={Vi0,Vi1,……Vin},满足(Vij-1,Vij) VR或<Vij-1,Vij> VR,(1<j n)
路径长度
沿路径边的数目或沿路径各边权值之和
回路
第一个顶点和最后一个顶点相同的路径
简单路径
序列中顶点不重复出现的路径
简单回路
除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路;
连通
从顶点V到顶点W有一条路径,则说V和W是连通的
连通图
图中任意两个顶点都是连通的图
连通分量
非连通图的每一个连通部分
强连通图
有向图中,如果对每一对Vi,Vj V,Vi Vj,从Vi到Vj和从Vj到Vi都存在路径,则称G是~示例1示例2图的定义和术语

第9页:完全图与子图举例

213有向完全图无向完全图图与子图341310213245136536顶点5的度:顶点2的度:1573246顶点2入度:出度:顶点4入度:出度:245136536定义及术语图的定义和术语

第10页:路径示例

路径: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例157324G26例245136G1定义及术语图的定义和术语

第11页:连通图与连通分量

连通图强连通图非连通图有两个连通分量245136V0V4V3V1V2356V0V1V2V3V0V3V2V1V4V5BACDFE图的定义和术语

第12页:抽象数据类型图的定义

ADTGraph{数据对象:V是具有相同特性的数据元素的集合称为顶点集数据关系:R={VR},两个顶点关系的集合VR={<v,w>| v,w∈V, <v,w>表示从v到w的弧}基本操作:CreatGraph(&G, V, VR);按V和VR的定义构造图GGetVex(G, v);返回图G中顶点v的值DestroyGraph(&G):销毁图GLocateVex(G, u);返回图G中顶点u的"位置”PutVex(&G, v, value);将图G中顶点v赋值为valueFirstAdjVex(G, v);返回v的第一个邻接点NextAdjVex(G, v, w);返回v的(相对于w)下一个邻接点抽象数据类型图的定义

第13页:图的基本操作(续)

基本操作(续):InsertVex(&G, v);在图G中增添新顶点vDeleteVex(&G, v);删除图G中顶点v及其相关的弧InsertArc(&G, v, w);在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w,v>DeleteArc(&G, v, w);在G中删除弧<v,w>,若G是无向的,则还删除对称弧<w,v>DFSTraverse(G, v, Visit());从顶点v起深度优先遍历图GBFSTraverse(G, v, Visit());从顶点v起广度优先遍历图G}ADTGraph抽象数据类型图的定义

第14页:邻接矩阵存储结构

设G=(V,E)是有n 1个顶点的图,邻接矩阵存储结构用两个数组分别存储图中顶点的信息(一维数组)和顶点间相关联的关系(边或弧,n阶方阵)AdjMatrix[i][j]=0否则1 (vi,vj)或<vi,vj> VR245136

  • 0 1 1 0 0 01 0 1 1 0 01 1 0 0 1 10 1 0 0 0 00 0 1 0 0 10 0 1 0 1 0图的存储结构——邻接矩阵

第15页:邻接矩阵的类型定义

设G=(V,E)是有n 1个顶点的图,邻接矩阵存储结构用两个数组分别存储图中顶点的信息(一维数组)和顶点间相关联的关系(边或弧,n阶方阵)# define Max_Vertex_Num 20//图中最大顶点个数

typedefstruct ArcCell{VRTypeadj;// VRType——顶点关系类型,对无权图,用1或0表示相邻否;对带权图,则为权值InfoType*info;//该弧相关信息指针(可无)} ArcCell,AdjMatrix[Max_Vertex_Num] [Max_Vertex_Num];弧及邻接矩阵结构AdjMatrix[i][j]=0否则1 (vi,vj)或<vi,vj> VR弧类型邻接矩阵类型typedefintVRType;图的存储结构——邻接矩阵

第16页:图的邻接矩阵定义

设G=(V,E)是有n 1个顶点的图,邻接矩阵存储结构用两个数组分别存储图中顶点的信息(一维数组)和顶点间相关联的关系(边或弧,n阶方阵)

typedefstruct{VertexType vexs[Max_Vertex_Num];//顶点向量AdjMatrix arcs;//邻接矩阵int vexnum, arcnum;//图中顶点及弧的数目}MGraph;图的定义typedefintVertexType;typedefcharVertexType;图的存储结构——邻接矩阵

第17页:有向图邻接矩阵示例

G1.arcs=0 1 1 00 0 0 00 0 0 11 0 0 0MGraphG1;G1.vexnum=4;//顶点数G1.arcnum=4;//弧数for(k=0;k<G1.vexnum;k++)//顶点向量scanf(“%c”, &G1.vexs[k]);G12413 设G=(V,E)是有n 1个顶点的图,邻接矩阵存储结构用两个数组分别存储图中顶点的信息(一维数组)和顶点间相关联的关系(边或弧,n阶方阵)

typedefstruct{VertexType vexs[Max_Vertex_Num];AdjMatrix arcs;int vexnum, arcnum;}MGraph;图的存储结构——邻接矩阵

第18页:无向图邻接矩阵示例

0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0 G2.arcs=MGraphG2;G2.vexnum=5;//顶点数G2.arcnum=6;//边数for(k=0;k<G2.vexnum;k++)//顶点向量scanf(“%c”, &G2.vexs[k]);15324G2 设G=(V,E)是有n 1个顶点的图,邻接矩阵存储结构用两个数组分别存储图中顶点的信息(一维数组)和顶点间相关联的关系(边或弧,n阶方阵)图的存储结构——邻接矩阵

第19页:邻接矩阵的特点

特点: 无向图的邻接矩阵对称,可压缩存储; 有向图邻接矩阵不一定对称; 无向图中顶点Vi的度是 有向图中, 顶点Vi的出度是 顶点Vi的入度是邻接矩阵中第i行元素之和邻接矩阵中第i行元素之和邻接矩阵中第i列元素之和G2.arcsG1.arcs15324G2G12413判断两顶点是否为邻接点:在图中增加、删除边:只需判邻接矩阵对应分量是否为1只需对邻接矩阵对应分量赋值1或清0图的存储结构——邻接矩阵

第20页:带权图的邻接矩阵

带权图(网)的邻接矩阵:AdjMatrix[i][j]=0或∞否则 ij(vi,vj)或<vi,vj> VR14523753186420 5 7 0 35 0 0 4 87 0 0 2 10 4 2 0 63 8 1 6 0 8273496221V32V2V4V1V6V5∞ 8 ∞ 7 4 98 ∞ 2 1 ∞ ∞∞ 2 ∞ 3 ∞ 27 1 3 ∞ ∞ 24 ∞ 2 ∞ ∞ 69 ∞ 2 2 6 ∞1234561 2 3 4 5 6图的存储结构——邻接矩阵

第21页:邻接表存储结构:弧结点

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表aecbdG11234acdb5e42^35^12^451^323^弧结点

typedefstruct Arcnode{ int adjvex;struct Arcnode *nextarc;}ArcNode;adjvex nextarcbdaceabcde图的存储结构——邻接表

第22页:邻接表:顶点结点

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表aecbdG11234acdb5e42^35^12^451^323^

typedefstruct Vnode{ VertexType data;ArcNode *firstarc;}VNode,AdjList[Max_Vertex_Num];顶点结点data firstarc顶点类型顶点数组类型图的存储结构——邻接表

第23页:邻接表:图的结构定义

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表aecbdG11234acdb5e42^35^12^451^323^

typedefstruct{AdjListvertices;int vexnum, arcnum;//顶点及弧的数目}ALGraph;图的定义ALGraphG1;G1.vexnum=5;G1.arcnum=6;G1.vertices图的存储结构——邻接表

第24页:无向图邻接表结点数

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表aecbdG11234acdb5e42^35^12^451^323^ALGraphG1;G1.vexnum=5;G1.arcnum=6;G1.vertices无向图中,单链表中结点个数是几??无向图中,单链表中结点个数=边数*2图的存储结构——邻接表

第25页:有向图邻接表结点数

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表ALGraphG2;G2.vexnum=4;G2.arcnum=4;G2.verticesG2bdac4^^1^32^1234acdb有向图中,单链表中结点个数是几??有向图中,单链表中结点个数=弧数

typedefstruct{AdjListvertices;int vexnum, arcnum;//顶点及弧的数目}ALGraph;图的定义图的存储结构——邻接表

第26页:邻接表特点:无向图求度

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表aecbdG11234acdb5e42^35^12^451^323^ALGraphG1;G1.vexnum=5;G1.arcnum=6;G1.vertices 特点 无向图中顶点Vi的度为第i个单链表中的结点数图的存储结构——邻接表

第27页:邻接表特点:有向图求度

实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧),再用一个顶点数组指向每个单链表ALGraphG2;G2.vexnum=4;G2.arcnum=4;G2.vertices 特点 无向图中顶点Vi的度为第i个单链表中的结点数G2bdac4^^1^32^1234acdb第i个单链表中的结点数 顶点Vi的入度为整个单链表中邻接点域为i的结点个数 有向图中 顶点Vi的出度为找邻接点容易 图的存储结构——邻接表

第28页:逆邻接表

1234acdbdatafirstarcG1bdac 逆邻接表:有向图中对每个结点建立以Vi为头的弧的单链表4^adjvexnextarc1^1^3^找逆邻接点容易 图的存储结构——邻接表

第29页:网的邻接表表示

网的邻接表表示8273496221V32V2V4V1V6V5adjvexweightnextarc弧结点123456V1V2V3V4V5V628475469∧183241∧22435262∧17213362∧143266∧19324256∧图的存储结构——邻接表

第30页:深度优先遍历

深度优先遍历(DFS)——类似于树的先根遍历 方法:从图的某一顶点V0出发,访问此顶点;然后依次从V0的未被访问的邻接点出发,深度优先遍历图,直至图中所有和V0相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历:V1 V3 V7V6 V2 V5 V8 V4 图的遍历V1V2V4V8V5V3V6V7

第31页:深度优先遍历过程

V1V2V4V5V3V7V6V8深度遍历:V1 V6 V7V3 V2 V5 V8 V4 图的遍历——深度优先遍历V1V3V2V4V5V6V7V8DFS——Depth First Search

第32页:遍历序列不唯一

V1V2V4V5V3V7V6V8深度遍历:V1 V6 V7V3 V2 V5 V8 V4 深度遍历:V1 V3 V4V6 V2 V7 V8 V5 V1V2V4V5V3V7V6V8深度遍历:V1 V6 V5V7 V2 V3 V8 V4 V1V3V2V4V5V6V7V8V1V2V4V8V3V6V7V5图的遍历序列不唯一图的遍历——深度优先遍历DFS——Depth First Search

第33页:深度优先遍历实现

V1V2V4V5V3V7V6V8深度遍历:V1V3V7V6V2V5V8V40 0 0 0 0 0 0 0visited[M]1 2 3 4 5 6 7 811111111278364151282datafirstarcadjvexnextarc1234134255678678736354^^^^^^^^结束V1V3V2V4V5V6V7V8深度优先遍历算法实现

第34页:给定存储结构序列唯一

V1V2V4V5V3V7V6V8深度遍历:V1V3V7V6V2V4V8V50 0 0 0 0 0 0 0visited[M]1 2 3 4 5 6 7 81111111127836482712341342vexdatafirstarc^^^adjvexnext55^^678678^^^结束V1V3V2V4V5V6V7V8深度优先遍历算法实现给定图的存储结构时,所得遍历序列唯一

第35页:深度优先遍历流程图

void DFSTraver (ALGraph G){int i;}开始标志数组初始化i=1Vi访问过DFSi=i+1i==M结束NNYY初始值为00 0 0 0 0 0 0 0visited[M]1 2 3 4 5 6 7 8intvisited[MAX];1 101 1 101visited[M]1 2 3 4 5 6 7 8for(i=1;i<=G.vexnum;i++)if(visited[i]==0)DFS(G,i);对未访问的顶点i调用DFSDFS广度优先遍历图的遍历——深度优先遍历DFS——Depth First Search深度优先遍历图G

第36页:DFS递归算法

开始访问v,置标志求v邻接点有邻接点w求下一邻接点w vw访问过结束NYNYDFS(G,v)

voidDFS(ALGraph G, intv){ ArcNode *w; int i;}递归遍历v,设置标志位4^1^1234acdb^32^datafirstarcG.verticesprintf("%d\t",v);visited[v]=1;w=G.vertices[v].firstarc;while(w!=NULL){ i=w->adjvex;if(visited[i]==0)DFS(G,i);w=w->nextarc;}求v的第一个邻接点w判断邻接点是否存在adjvexnextarc取邻接点下标若邻接点未被访问,再从邻接点开始遍历求下一个邻接点从顶点v出发遍历图深度优先遍历图的遍历——深度优先遍历DFS——Depth First Search

第37页:广度优先遍历

广度优先遍历(BFS)——类似于树的层次遍历 方法:从图的某一顶点V0出发,访问此顶点后,依次访问V0的所有未曾访问过的邻接点;然后分别从这些邻接点出发,广度优先遍历图,直至图中所有已被访问的顶点的邻接点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历:V1 V6 V8V7 V2 V5 V4 V3 图的遍历V1V3V2V4V5V6V7V8

第38页:广度优先遍历序列

V1V2V4V5V3V7V6V8广度遍历:V1 V7 V5V8 V2 V6 V4 V3 V1V2V4V5V3V7V6V8广度遍历:V1 V6 V8V7 V2 V5 V4 V3 V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8图的遍历——广度优先遍历BFS——Breadth First Search

第39页:广度优先遍历用队列实现

V1V2V4V5V3V7V6V8广度遍历:V1 V7 V5V8 V2 V6 V4 V3 V1V2V4V5V3V7V6V8广度遍历:V1 V6 V8V7 V2 V5 V4 V3 广度遍历:V8 V2 V1V3 V4 V7 V6 V5 利用队列实现图的广度优先遍历V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8V2V3图的遍历——广度优先遍历BFS——Breadth First Search

第40页:广度优先遍历的实现

14235554315114312341342vexdatafirstarc^^^adjvexnextarc55^^2210 1 2 3 4 5fr0 0 0 0 0visited[M]1 2 3 4 5遍历序列:11广度优先遍历的实现rf4414r13313r2122rf5155rfff结束NULLNULLNULLNULLNULL

  • 访问一个顶点并入队
  • 出队一个顶点,访问其未被访问过的邻接点并入队队列不为空时,

第41页:广度优先遍历流程图

intvisited[Max];

void BFStraver(ALGraph G){ int i;for(i=1;i<=G.vexnum;i++)if(visited[i]==0)BFS(G , i );}开始标志数组初始化i=1Vi访问过BFSi=i+1i==M结束NNYY0 0 0 0 0 0 0 0visited[M]1 2 3 4 5 6 7 81 101 1 101visited[M]1 2 3 4 5 6 7 8对未访问的顶点i调用BFSBFS图的遍历——广度优先遍历BFS——Breadth First Search广度优先遍历图G

第42页:BFS算法

开始访问v,置标志求V邻接点ww存在吗V下一邻接点 ww访问过结束NYNYBFS初始化队列v入队队列空?队头V出队访问w,置标志w入队NaaY

  • 访问一个顶点并入队
  • 出队一个顶点,访问其未被访问过的邻接点并入队队列不为空时,从顶点v出发遍历图
void BFS( ALGraph G, intv){}int qu[MAX],f=0,r=0;ArcNode *p;printf("%d\t",v); visited[v]=1;qu[r++]=v;while(f<=r){v=qu[f++];p=G.vertices[v].firstarc;while(p!=NULL){v=p->adjvex;if(visited[v]==0){ visited[v]=1;printf("%d\t",v);qu[r++]=v;}p=p->nextarc;}}遍历v,设置标志位v入队队列不为空时队头出队,求其邻接点当邻接点存在时,访问所有未访问过的邻接点并入队广度优先遍历

第43页:生成树的定义

定义:所有顶点均由边连接在一起,但不存在回路的图 深度优先生成树和广度优先生成树——利用遍历经过的分支构成生成树 生成森林:非连通图每个连通分量的生成树一起组成非连通图的~ 说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点: 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树GHKI生成树——解决最小代价问题图的遍历——

  • 访问每一个结点
  • 每个结点只访问一次示例深度广度生成树生成森林最小生成树

第44页:连通图的生成树

连通图G1V0V4V3V1V2连通图G1的一棵生成树V0V4V3V1V2BACDFEBACDFE生成树

第45页:生成树不唯一

V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5生成树图的生成树不唯一生成树

第46页:深度与广度优先生成树

V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树V1V2V4V5V3V7V6V8深度优先生成树与广度优先生成树深度遍历:V1 V3 V7V6 V2 V5 V8 V4 广度遍历:V1 V6 V8V7 V2 V5 V4 V3 生成树

第47页:深度优先生成森林

ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林生成森林生成树

第48页:最小生成树问题

问题提出要在n个城市间建立通信联络网,顶点——表示城市权——城市间建立通信线路所需花费代价希望找到一棵生成树,它的每条边上的权值之和(即建立该通信网所需花费的总代价)最小———最小代价生成树 问题分析n个城市间建立通信网,只需n-1条线路问题转化为:如何在可能的线路中选择n-1条,能把所有城市(顶点)均连起来,且总耗费(各边权值之和)最小1654327131791812752410最小生成树

第49页:Prim算法思想

算法思想:设N=(V,{E})是连通网,G=(U,{TE})是N上最小生成树 初始令U={u0},(u0 V),TE= 在所有u U,v V-U的边(u,v) E中,找一条代价最小的边(u0,v0) 将(u0,v0)并入集合TE,同时v0并入U 重复上述操作直至U=V为止,则G=(V,{TE})为N的最小生成树,共重复n-1次构造最小生成树——Prim算法最小生成树中不在最小生成树中1654327131791812752410

第50页:Prim算法构造过程

1654326513566425131163141164314216432142516543214253构造最小生成树——Prim算法

第51页:Prim算法构造示例

abcdegf195141827168213127aae14ade148acde1483abcde51483abcdeg5141683abcdeg5141683f21构造最小生成树——Prim算法构造过程

第52页:Kruskal算法思想

算法思想:设连通网N=(V,{E}),令最小生成树 初始状态为只有n个顶点而无边的非连通图T=(V,{ }),每个顶点自成一个连通分量165432123451654326513566425 在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边,选取下一条代价最小的边 依此类推,直至T中所有顶点都在同一连通分量上为止构造最小生成树——Kruskal算法

第53页:Kruskal算法构造过程

1654326513566425165432(初始)1165432(1)21165432(2)321165432(3)4321165432(4)54321165432(5)构造最小生成树——Kruskal算法构造过程

第54页:Kruskal算法实现

(1)用顶点数组和边数组存放顶点和边信息(2)初始,令每个顶点的SubNet互不相同;每个边的flag为0(3)选出权值最小且flag为0的边(4)

  • 若该边依附的两个顶点的SubNet值不同,即非连通,则令该边的flag=1,选中该边;再令该边依附的两顶点的SubNet以及两集合中所有顶点的SubNet相同
  • 若该边依附的两个顶点的SubNet值相同,即连通,则令该边的flag=2,即舍去该边(5)重复上述步骤,直到选出n-1条边为止
typedefstruct{ int data;intSubNet;}VEX;VEX v[N];typedefstruct{ int vexh, vext;//边的两顶点int weight;//权值intflag;//标志,0—待选}EDGE;1—选中EDGE e[M];2—舍弃顶点结点边结点Kruskal算法实现

第55页:Kruskal算法演示

dataSubNet1245361245361245363345vexhweight112213233544vextflag61535500000001342567895 66664260000111112Kruskal算法演示165432651356642516543212345142112222

第56页:学生选修课程问题

学生选修课程问题:以顶点表示课程、有向弧表示先决条件,通过拓扑排序确定无矛盾的学习顺序。下表列出各课程的先修课。

课程代号、课程名称与先修课对照
课程代号课程名称先修课
C1程序设计基础无
C2离散数学C1
C3数据结构C1、C2
C4汇编语言C1
C5语言设计和分析C3、C4
C6计算机原理C11
C7编译原理C3、C5
C8操作系统C3、C6
C9高等数学无
C10线性代数C9
C11普通物理C1、C9、C10
C12数值分析C9

第57页:AOV网与拓扑排序

拓扑排序
解决具有优先关系的活动排序问题 定义
AOV网
用顶点表示活动,用弧表示活动间优先关系的有向图称为顶点表示活动的网(ActivityOnVertexnetwork),简称AOV网 若<vi,vj>是图中有向边,则vi是vj的直接前驱;vj是vi的直接后继 AOV网中不允许有回路,这意味着某项活动以自己为先决条件
拓扑排序
把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~ 检测AOV网中是否存在环方法:对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环

第58页:拓扑排序的方法

拓扑排序的方法 在有向图中选一个没有前驱的顶点且输出之 从图中删除该顶点和所有以它为尾的弧 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止拓扑排序——解决具有优先关系的活动排序问题BDAC拓扑序列:ABCDBDACACBD或:BDACBDAC拓扑序列:A无法求得其拓扑有序序列因为图中存在回路BDCAAOV网的拓扑序列不唯一拓扑排序能够检测图中是否有环存在

第59页:课程拓扑序列

c4c1c2c3c12c9c10c11c6c7c8c5拓扑序列:--C2--C3--C4--C5--C7--C9--C10--C12--C11--C6--

C8拓扑排序
解决具有优先关系的活动排序问题C1或:C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8c4c1c2c3c12c9c10c11c6c7c8c5拓扑排序过程中,对数据的主要操作是什么??求结点的入度、
邻接点输出入度为0的顶点删除以其为尾的弧
邻接点入度减1

第60页:拓扑排序算法实现:邻接表

拓扑排序——解决具有优先关系的活动排序问题 算法实现 以邻接表作存储结构(加入入度域)bdac4^4^1234acdbdatafirstarc32^adjvexnextarc0121^in表头结点

typedefstruct Vnode{ VertexType data;int in;//入度域Arcnode *firstarc;}Vnode,AdjList[Max_Vertex_Num];图的定义typedefstruct{ AdjList vertices;int vexnum, arcnum;}ALGraph;

第61页:拓扑排序算法步骤

拓扑排序——解决具有优先关系的活动排序问题 算法实现 以邻接表作存储结构(加入入度域)bdac4^4^1234acdbdatafirstarc32^adjvexnextarc0121^in 把邻接表中所有入度为0的顶点进栈 栈非空时,栈顶元素Vj出栈并输出到拓扑序列中;查找Vj的直接后继Vk,将其入度减1;若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n,则有向图有环;否则,拓扑排序完毕

第62页:拓扑排序算法演示

32104123456top16toptop554325240122infirstarc^^^adjvexnextarc3^^0123456^v1v3v4v2v5v6data输出序列:v6top21topv10top40top31topv3102topv2topv405v5top132456拓扑排序算法演示结束有向图的邻接表存储结构一定时,其拓扑序列是唯一的NULLNULLNULLNULLNULLNULL

第63页:拓扑排序算法描述

拓扑排序——解决具有优先关系的活动排序问题 算法描述

StatusTopologicalSort(ALGraphG){ int i,j,k,count; ArcNode *p; SqStack S;CountInDegree(G);InitStack(S);for ( i=0; i<G.vexnum; ++i)if (!G.vertices[i].in)Push(S, i);count=0;while (!StackEmpty(S)){Pop(S, j); ++count; printf("%d ",G.vertices[j].data);for (p=G.vertices[j].firstarc;p; p=p->nextarc){k=p->adjvex;if (!(--G.vertices[k].in))Push(S,k);}}if (count<G.vexnum) returnERROR;returnOK;}求各顶点入度求入度入度为0的顶点入栈4^4^1234acdbfirstarc32^adjvexnextarc0121^inbdac计数栈非空时,拓扑排序邻接点入度-1若计数<顶点数,则有环存在

第64页:求顶点入度算法

voidCountInDegree(ALGraph &G){int i;ArcNode *p;for(i=0; i<G.vexnum; i++)G.vertices[i].in=0;for(i=0; i<G.vexnum; i++)for(p=G.vertices[i].firstarc; p; p=p->nextarc)G.vertices[p->adjvex] .in++;}拓扑排序算法拓扑排序——解决具有优先关系的活动排序问题4^4^1234acdbdatafirstarc32^adjvexnextarc0121^inbdac求各顶点入度顶点入度清0扫描邻接表,计算顶点入度

第65页:最短路径问题

问题提出用带权的有向图表示一个交通运输网,图中:

表示城市间的交通联系权
表示线路的长度或沿此线路运输所花的时间或费用等问题:从某顶点出发,沿图的边到达另一顶点所经过的路径中,
各边上权值之和最小的一条路径
最短路径 从某个源点到其余各顶点的最短路径最短路径516432085623013717329长度最短路径13<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120

第66页:Dijkstra算法思想

按路径长度递增次序产生最短路径把顶点的集合V分成两组:(1)S:{已求出最短路径的顶点}(2)T=V-S:{尚未确定最短路径的顶点}保证:(1)每一个顶点对应一个距离值S中顶点:从V0到此顶点的最短路径长度T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度(2)S中各顶点的距离值≤T中各顶点的距离值将T中顶点按最短路径递增的次序加入到S中,即每次从T中找出距离值最小的顶点加入到S中,直到S=V为止最短路径——Dijkstra算法

第67页:Dijkstra算法步骤

算法步骤 初使时令S={V0},T={其余顶点},T中顶点Vi对应的距离值 若存在<V0,Vi>,为<V0,Vi>弧上的权值 若不存在<V0,Vi>,为 从T中选取一个其距离值为最小的顶点W,加入S 对T中其余顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值比不加W的路径要短,则修改此距离值 重复上述步骤,直到S中包含所有顶点,即S=V为止最短路径——Dijkstra算法

第68页:Dijkstra算法演示

Dijkstra 算法的最短路径结果:下表汇总从源点 V0 到各终点的最短路径及其长度,算法按路径长度递增次序逐点确定。

从 V0 到各终点的最短路径与长度
终点最短路径路径长度
V1<V0,V1>13
V2<V0,V2>8
V3<V0,V2,V3>13
V4<V0,V2,V3,V4>19
V5<V0,V2,V3,V4,V5>21
V6<V0,V1,V6>20

第69页:第六章本章小结

掌握图的基本概念和术语本章小结掌握图的邻接矩阵、邻接表存储结构掌握图的遍历及遍历算法的实现掌握生成树的定义,掌握Prim和Kruskal构造最小生成树的方法掌握拓扑排序的求解方法掌握Dijkstra求取最短路径的方法

顶部目录