缑西梅数据结构图

《缑西梅数据结构图》由会员分享，可在线阅读，更多相关《缑西梅数据结构图（87页珍藏版）》请在装配图网上搜索。

1、会计学1缑西梅数据结构图缑西梅数据结构图2二有关图的常用术语二有关图的常用术语n n边边边边(v,w)(v,w)弧弧弧弧00001111222265433边边弧弧弧头弧头弧尾弧尾n有向图与无向图 在有向图中，顶点对 是有序的。在无向图中，顶点对(x,y)是无序的。n完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边,则此图为无向完全图。有 n 个顶点的有向图有n(n-1)条边,则此图为有向完全图。第1页/共87页3 n n邻接顶点邻接顶点邻接顶点邻接顶点若若若若 (v,w)(v,w)是是是是 E(G)E(G)中的一条边，则称中的一条边，则称中的一条边，则称中的一条边，则称 v v 与与

2、与与 w w 互为互为互为互为邻接顶点。邻接顶点。邻接顶点。邻接顶点。若若若若 是是是是 E(G)E(G)中的一条弧，则称中的一条弧，则称中的一条弧，则称中的一条弧，则称 顶点顶点顶点顶点v v 邻接到邻接到邻接到邻接到顶点，顶点顶点，顶点顶点，顶点顶点，顶点w w 邻接自邻接自邻接自邻接自顶点顶点顶点顶点v v。n n子图子图子图子图设有两个图设有两个图设有两个图设有两个图 GG(V,E)(V,E)和和和和 GG(V,E)(V,E)。若。若。若。若 VV V V 且且且且 EE E,E,则称则称则称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。n n权权权权

3、某些图的边具有与它相关的数某些图的边具有与它相关的数某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。这称之为权。这称之为权。这称之为权。这种带权图叫做种带权图叫做种带权图叫做种带权图叫做网络网络网络网络。0123子图子图0130123023第2页/共87页4n n路径路径路径路径 是一个顶点序列是一个顶点序列，并，并且相邻的两个顶点有边或弧相且相邻的两个顶点有边或弧相连。连。n n顶点的度顶点的度顶点的度顶点的度一个顶点一个顶点v的度是与的度是与它相关联的边的条数。记作它相关联的边的条数。记作TD(v)。在有向图中。在有向图中,顶点的度顶点的度等于该顶点的入度与出度之和。等于该

4、顶点的入度与出度之和。n n顶点顶点顶点顶点 v v 的入度的入度的入度的入度是以是以 v 为终点的有为终点的有向边的条数向边的条数,记作记作 ID(v);顶点顶点顶点顶点 v v 的出度的出度的出度的出度是以是以 v 为始点的有向边为始点的有向边的条数的条数,记作记作 OD(v)。第3页/共87页5顶点的出度顶点的出度:以顶点以顶点v 为弧尾的弧的数目为弧尾的弧的数目;顶点的入度顶点的入度:以顶点以顶点v v为为弧头的弧的数目。弧头的弧的数目。ABECF有向图顶点的度顶点的度(TD)=)=出度出度(OD)+)+入度入度(ID)TD(B)=OD(B)+ID(B)=1+2=3例如例如:第4页/共

5、87页6n n路径长度路径长度非带权图的路径长度是指此路非带权图的路径长度是指此路非带权图的路径长度是指此路非带权图的路径长度是指此路径上边的条数。带权图径上边的条数。带权图径上边的条数。带权图径上边的条数。带权图(网络网络网络网络)的路径长度是指路的路径长度是指路的路径长度是指路的路径长度是指路径上各边的权之和。径上各边的权之和。径上各边的权之和。径上各边的权之和。n n简单路径简单路径若路径上各顶点均不互相重复若路径上各顶点均不互相重复若路径上各顶点均不互相重复若路径上各顶点均不互相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径。则称这样的路径为简单路径

6、。n n回路回路 第一个顶点与最后一个顶点相同的路径第一个顶点与最后一个顶点相同的路径第一个顶点与最后一个顶点相同的路径第一个顶点与最后一个顶点相同的路径n n简单回路简单回路除第一个顶点与最后一个顶点除第一个顶点与最后一个顶点除第一个顶点与最后一个顶点除第一个顶点与最后一个顶点外，其余顶点不重复出现的回路。外，其余顶点不重复出现的回路。外，其余顶点不重复出现的回路。外，其余顶点不重复出现的回路。012301230123第5页/共87页7无向图中无向图中,若图中任意两个顶点若图中任意两个顶点之间都有路径相通，则称此图之间都有路径相通，则称此图为为连通图连通图;若无向图为非连通图，则图中若无向图

7、为非连通图，则图中各个各个极大连通子图极大连通子图称作此图的称作此图的连通分量连通分量。BACDFEBACDFE第6页/共87页8有向图中有向图中,若任意两个顶点之间都存在一条有向若任意两个顶点之间都存在一条有向路径，则称此有向图为路径，则称此有向图为强连通图强连通图。否则，其各个否则，其各个极大强连通子图极大强连通子图称作它的称作它的强连通强连通分量分量。ABECFABECF第7页/共87页9一个有一个有 n 个顶点和个顶点和 e 条边的连通图的条边的连通图的生成树生成树:是一个是一个极小连通子图，极小连通子图，它含有图中全部顶点，它含有图中全部顶点，但只有足以构成一棵树的但只有足以构成一棵

8、树的n-1n-1条边。条边。BACDFEBACDFE在极小连通子图中增加一条边，则一定有环。在极小连通子图中去掉一条边，则成为非连通图。第8页/共87页10有有有有n n个顶点，个顶点，个顶点，个顶点，n-1n-1条边的图必定是生成树吗条边的图必定是生成树吗条边的图必定是生成树吗条边的图必定是生成树吗？有向树：有向树：有向树：有向树：如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为如果一个有向图恰有一个顶点的入度为0 0，其，其，其，其余顶点的入度均为余顶点的入度均为余顶点的入度均为余顶点的入度均为1 1。一个有向图的生成森林：一个有向图的

9、生成森林：一个有向图的生成森林：一个有向图的生成森林：由若干个有向树组成，含有图由若干个有向树组成，含有图由若干个有向树组成，含有图由若干个有向树组成，含有图中全部顶点，但只有足以构成若干棵互不相交的有向树中全部顶点，但只有足以构成若干棵互不相交的有向树中全部顶点，但只有足以构成若干棵互不相交的有向树中全部顶点，但只有足以构成若干棵互不相交的有向树的弧的弧的弧的弧。BACDFEBACDFE第9页/共87页11若无向图中有21条边，则：1)保持该图不连通至少应具有多少个顶点？2)保持该图连通至少有多少个顶点，至多有多少个顶点？思考题1)m个顶点形成完全图，另一个顶点与这m个顶点不连通 m(m-1

10、)=21 m=7 n=m+1=82)至少有 7 个顶点(完全图)，至多有22个顶点(生成树)第10页/共87页127.2 7.2 图的存储图的存储结构结构n n设图设图设图设图 G=(V,E)G=(V,E)是一个有是一个有是一个有是一个有 n n 个顶点的图个顶点的图个顶点的图个顶点的图,图的图的图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组邻接矩阵是一个二维数组邻接矩阵是一个二维数组 AnnAnn，定义：，定义：，定义：，定义：一、邻接矩阵(Adjacency Matrix)n 顶点表-记录各个顶点信息 邻接矩阵-记录各个顶点之间的关系第11页/共87页13n n无向图的邻接矩阵是对称

11、的无向图的邻接矩阵是对称的;n n有向图的邻接矩阵一般是不对有向图的邻接矩阵一般是不对称的。称的。0123012第12页/共87页14n n在有向图中在有向图中,统计第统计第 i 行行 1 的的个数可得顶点个数可得顶点 i 的出度，统计的出度，统计第第 j 列列 1 的个数可得顶点的个数可得顶点 j 的的入度。入度。n n在无向图中在无向图中,统计第统计第 i 行行(列列)11的个数可得顶点的个数可得顶点i 的度。的度。第13页/共87页15186329542031网络的邻接矩阵网络的邻接矩阵网络的邻接矩阵网络的邻接矩阵第14页/共87页16#define INFINITYINT_MAX /最

12、大值最大值#define MAX_VERTEX_NUM20 /最大顶点个数最大顶点个数typedef enumDG,DN,UDG,UDN GraphKind;/有向图，有向网，无向图，无向网有向图，有向网，无向图，无向网typedef struct ArcCell VRType adj;/VRType表示顶点关系类型，无权图：表示顶点关系类型，无权图：0或或1；/有权图，权值，有权图，权值，InfoType*info;/该弧相关信息的指针该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexTyp

13、e vexsMAX_VERTEX_NUM;/顶点向量顶点向量 AdjMatrix arcs;/关系集（即邻接矩阵）关系集（即邻接矩阵）int vexnum,arcnum;/顶点数、边顶点数、边/弧弧数数 GraphKind kind;/图的种类图的种类MGraph;用邻接矩阵表示的结构定义用邻接矩阵表示的结构定义用邻接矩阵表示的结构定义用邻接矩阵表示的结构定义第15页/共87页17二、邻接表二、邻接表二、邻接表二、邻接表 (Adjacency List)(Adjacency List)邻接表邻接表邻接表邻接表:是图的一种链式存储结构。是图的一种链式存储结构。是图的一种链式存储结构。是图的一种链

14、式存储结构。边边边边/弧的结点结构弧的结点结构弧的结点结构弧的结点结构(表结点表结点表结点表结点)adjvex nextarc info顶点的结点结构顶点的结点结构(头结点头结点)data firstarc data;/顶点信息firstarc;/指向第一条依附该顶点的边/弧adjvex;/该边/弧所指向的顶点的位置nextarc;/指向下一条边/弧指针info;/该边/弧相关信息的指针第16页/共87页18 无向图的邻接表无向图的邻接表无向图的邻接表无向图的邻接表 同一个顶点发出的边链接在同一同一个顶点发出的边链接在同一个边链表中，每一个链结点代表个边链表中，每一个链结点代表一条边一条边(表

15、结点表结点),所有的头结点放所有的头结点放在一个一维数组里。在一个一维数组里。ABCDdata firstarcABCD0123adjvex nextarc 130210第17页/共87页19 有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABCABC012 邻接表邻接表(出边表出边表)ABC012逆邻接表逆邻接表(入边表入边表)102 011第18页/共87页20n n网络网络网络网络 (带权图带权图带权图带权图)的邻接表的邻接表的邻接表的邻接表BACD69528ABCD0123 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)

16、AD5BCADBCAD第19页/共87页21图的邻接表存储表示图的邻接表存储表示#define MAX_VERTEX_NUM 20typedef struct ArcNode /表结点表结点 int adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧指针指向下一条弧指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;typedef struct VNode/头结点头结点 VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧

17、指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;第20页/共87页22typedef struct typedef struct AdjList vertices;AdjList vertices;int vexnum,arcnum;int vexnum,arcnum;/图的当前顶点数和弧数图的当前顶点数和弧数图的当前顶点数和弧数图的当前顶点数和弧数GraphKind kind;GraphKind kind;/图的种类标志图的种类标志图的种类标志图的种类标志ALGraph;ALGraph;第21页/共87页23邻接表的构造算法（有向带权图）邻接表的构造算法（有

18、向带权图）void CreateGraph(ALGraph G)cin G.vexnum G.arcnum;/输入顶点数和边数输入顶点数和边数 for(int i=0;i G.verticesi.data;/输入顶点信息输入顶点信息 G.verticesi.firstarc=NULL;for(i=0;i tail head weight;ArcNode*p=new ArcNode;p-adjvex=head;p-info=weight;p-nextarc=G.verticestail.firstarc;/链入第链入第 /tail/tail 号链表的前端号链表的前端 G.verticestail

19、.firstarc=p;第22页/共87页24三、十字链表三、十字链表-有向图有向图n有向图:邻接表-出边表,求入度不方便;逆邻接表-入边表,求出度不方便 tailvex headvexhlinktlinkinfotailvex 和headvex分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指示弧头相同的下一条弧，而链域tlink指示弧尾相同的下一条弧.info指向该弧的相关信息。n弧结点数=弧数n十字链表每一条弧对应一个结点，每个顶点对应一个结点第23页/共87页25datafirstinfirstoutn顶点结点ndata存放和顶点相关的信息；nfirstin和firstout分

20、别指向以该顶点为弧头或 弧尾的第一个弧结点。第24页/共87页26BCADABCD01230103122331 十字链表举例第25页/共87页277.3 7.3 图的遍图的遍历历n n从图中某一顶点出发访遍图中从图中某一顶点出发访遍图中所有的所有的顶点，且使每个顶点顶点，且使每个顶点仅仅被访问一次被访问一次，这一过程就叫做，这一过程就叫做图的遍历图的遍历。n两个问题 1.如何确保每个顶点都被访问到？2.如何确保每个顶点只被访问一次？第26页/共87页28问题问题2：为避免重复访问，可设置：为避免重复访问，可设置一个标志顶点是否被访问过的一个标志顶点是否被访问过的辅助数组辅助数组 visited

21、 。visited 的初始状态为的初始状态为 0,在图的遍历在图的遍历过程中过程中,一旦某一个顶点一旦某一个顶点 i 被访被访问问,就立即让就立即让 visited i 为为 1,防止它被多次访问。防止它被多次访问。问题1：采用合适的遍历算法深度优先搜索 DFS(Depth First Search)广度优先搜索 BFS(Breadth First Search)第27页/共87页29n nDFS DFS 在在在在访问访问访问访问图中图中图中图中某一某一某一某一起始起始起始起始顶点顶点顶点顶点 v v 后后后后,由由由由 v v 出发出发出发出发,访访访访问它的问它的问它的问它的任一邻接任一邻

22、接任一邻接任一邻接顶点顶点顶点顶点 ww1 1;再从再从再从再从 ww1 1 出发出发出发出发,访问访问访问访问与与与与 ww1 1邻邻邻邻 接但还没有访问过接但还没有访问过接但还没有访问过接但还没有访问过的顶点的顶点的顶点的顶点 ww2 2;然后再从然后再从然后再从然后再从 ww2 2 出出出出发发发发,进行类似的访问进行类似的访问进行类似的访问进行类似的访问,如此进行下去如此进行下去如此进行下去如此进行下去,直至到达直至到达直至到达直至到达所所所所有的邻接顶点都被访问过有的邻接顶点都被访问过有的邻接顶点都被访问过有的邻接顶点都被访问过的顶点的顶点的顶点的顶点 u u 为止。为止。为止。为止

23、。n n接着接着接着接着,退回一步退回一步退回一步退回一步,退到前一次刚访问过的顶点退到前一次刚访问过的顶点退到前一次刚访问过的顶点退到前一次刚访问过的顶点,看看看看是否还有其它没有被访问的邻接顶点。如果有是否还有其它没有被访问的邻接顶点。如果有是否还有其它没有被访问的邻接顶点。如果有是否还有其它没有被访问的邻接顶点。如果有,则则则则访问此顶点访问此顶点访问此顶点访问此顶点,之后再从此顶点出发之后再从此顶点出发之后再从此顶点出发之后再从此顶点出发,进行与前述类进行与前述类进行与前述类进行与前述类似的访问似的访问似的访问似的访问;如果没有如果没有如果没有如果没有,就再退回一步进行搜索。重复就再退

24、回一步进行搜索。重复就再退回一步进行搜索。重复就再退回一步进行搜索。重复上述过程上述过程上述过程上述过程,直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。深度优先搜索深度优先搜索深度优先搜索深度优先搜索DFS(Depth_First Search)DFS(Depth_First Search)第28页/共87页30n n深度优先搜索过深度优先搜索过深度优先搜索过深度优先搜索过程程程程67ACDEGBFIHACDEGBFIH1234589123456789前进回退深度优先生成树深度优先生成树第29页/

25、共87页31n nBFSBFS在访问了起始顶点在访问了起始顶点在访问了起始顶点在访问了起始顶点 v v 之后之后之后之后,由由由由 v v 出发出发出发出发,依次访问依次访问依次访问依次访问 v v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1,w2,wt,w1,w2,wt,然后再然后再然后再然后再顺顺顺顺序访问序访问序访问序访问 w1,w2,wt w1,w2,wt 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还

26、未被再从这些访问过的顶点出发，再访问它们的所有还未被再从这些访问过的顶点出发，再访问它们的所有还未被再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，访问过的邻接顶点，访问过的邻接顶点，访问过的邻接顶点，如此做下去，直到图中所有顶点如此做下去，直到图中所有顶点如此做下去，直到图中所有顶点如此做下去，直到图中所有顶点都被访问到为止。都被访问到为止。都被访问到为止。都被访问到为止。n广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程（辅助队列）。广度优先搜索广度优先搜索广度优先搜索广度优先搜索BF

27、S(Breadth_First Search)BFS(Breadth_First Search)第30页/共87页32n n广度优先搜广度优先搜索过程索过程ACDEGBFIHACDEGBFH123456789123456789广度优先生成树广度优先生成树I第31页/共87页33 图的广度优先搜索算法void BFS(Graph G,int visited(int v)for(v=0;vG.vexnum;v+)visitedv=FALSE;InitQueue(Q);for(v=0;v=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;visit(w)

28、;EnQueue(Q,w);/if /while /if /BFS第32页/共87页思考思考1 1 1 1、如何确定一项工程的工期？最佳工期如何计算？、如何确定一项工程的工期？最佳工期如何计算？、如何确定一项工程的工期？最佳工期如何计算？、如何确定一项工程的工期？最佳工期如何计算？（关键路径问题）（关键路径问题）（关键路径问题）（关键路径问题）2 2 2 2、如何以最低造价架构城市之间的通信网？几个小、如何以最低造价架构城市之间的通信网？几个小、如何以最低造价架构城市之间的通信网？几个小、如何以最低造价架构城市之间的通信网？几个小区之间要建一个供水站，建在什么位置最合适？区之间要建一个供水站，

29、建在什么位置最合适？区之间要建一个供水站，建在什么位置最合适？区之间要建一个供水站，建在什么位置最合适？（最小生成树问题）（最小生成树问题）（最小生成树问题）（最小生成树问题）3 3 3 3、如何合理安排大一到大四的教学计划？、如何合理安排大一到大四的教学计划？、如何合理安排大一到大四的教学计划？、如何合理安排大一到大四的教学计划？（拓扑排（拓扑排（拓扑排（拓扑排序问题）序问题）序问题）序问题）4 4 4 4、从上海到北京怎么走最省时间或金钱？如何花费、从上海到北京怎么走最省时间或金钱？如何花费、从上海到北京怎么走最省时间或金钱？如何花费、从上海到北京怎么走最省时间或金钱？如何花费最少周游所有

30、城市？最少周游所有城市？最少周游所有城市？最少周游所有城市？（最短路径问题）（最短路径问题）（最短路径问题）（最短路径问题）第33页/共87页35 7.4.1 无向图的连通分量 和生成树n若图连通，可从图中任一顶点出发，进行深度优先搜索或广度优先搜索，分别得到深度优先生成树或广度优先生成树。7.4 7.4 图的连通性问题图的连通性问题n 当无向图为非连通图时,从图中某一顶点出发,进行深度优先搜索或广度优先搜索，不可能遍历到图中的所有顶点,只能访问到该顶点所在的最大连通子图(连通分量)的所有顶点。n 若从无向图的每一个连通分量中的一个顶点出发进行遍历,可求得无向图的所有连通分量。第34页/共87

31、页36n n求连通分量的算法需要对图的求连通分量的算法需要对图的每一个顶点进行检测：若已被每一个顶点进行检测：若已被访问过，则该顶点一定是落在访问过，则该顶点一定是落在图中已求得的连通分量上；若图中已求得的连通分量上；若还未被访问，则从该顶点出发还未被访问，则从该顶点出发遍历图，可求得图的另一个连遍历图，可求得图的另一个连通分量。通分量。n n对于非连通的无向图，所有连对于非连通的无向图，所有连通分量的生成树组成了非连通通分量的生成树组成了非连通图的生成森林。图的生成森林。第35页/共87页37BCDA非连通无向图及其两个连通分量非连通无向图及其两个连通分量非连通图的连通分量的极小连通子图非连

32、通图的连通分量的极小连通子图EFBAEFCDBAEFCD第36页/共87页387.4.2 7.4.2 最小生成树最小生成树最小生成树最小生成树n n使用不同的遍历图的方法，可使用不同的遍历图的方法，可以得到不同的生成树；从不同以得到不同的生成树；从不同的顶点出发，也可能得到不同的顶点出发，也可能得到不同的生成树。的生成树。n 最小生成树：对于连通网G，G的生成树各边也是带权的，各边权值总和最小的称为最小生成树。n 构造最小生成树的准则必须使用且仅使用该网络中的n-1 条边来 联结网络中的 n 个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。第37页/共87页39普里姆普里姆普里姆普里

33、姆(PrimPrim)算法算法算法算法-最小生成树不断壮大的过程最小生成树不断壮大的过程最小生成树不断壮大的过程最小生成树不断壮大的过程n n基本思想基本思想基本思想基本思想：取图中任意一个顶点取图中任意一个顶点取图中任意一个顶点取图中任意一个顶点v v v v作为生成树的根，之后往作为生成树的根，之后往作为生成树的根，之后往作为生成树的根，之后往生成树上添加新的顶点生成树上添加新的顶点生成树上添加新的顶点生成树上添加新的顶点w w w w，在添加的顶点，在添加的顶点，在添加的顶点，在添加的顶点w w w w和已经在生和已经在生和已经在生和已经在生成树上的顶点成树上的顶点成树上的顶点成树上的顶

34、点v v v v之间必定存在一条边，并且该边的权之间必定存在一条边，并且该边的权之间必定存在一条边，并且该边的权之间必定存在一条边，并且该边的权值在所有连通生成树上的顶点和非生成树上的顶点之值在所有连通生成树上的顶点和非生成树上的顶点之值在所有连通生成树上的顶点和非生成树上的顶点之值在所有连通生成树上的顶点和非生成树上的顶点之间的边中取值最小，之后继续往生成树上添加顶点，间的边中取值最小，之后继续往生成树上添加顶点，间的边中取值最小，之后继续往生成树上添加顶点，间的边中取值最小，之后继续往生成树上添加顶点，直到生成树上含有直到生成树上含有直到生成树上含有直到生成树上含有n-1n-1n-1n-1

35、条边为止。条边为止。条边为止。条边为止。第38页/共87页40算法：设G=(V,E)连通网,T=(U,TE)是G的最小生成树。（1）U=v0，TE=（2）while(UV)(u,v)=minw|uU,vV-U TE=TE+(u,v)U=U+v 采用邻接矩阵作为图的存储表示。第39页/共87页41252510504613228102514242216185050410原图 (a)(b)504310(c)(d)(e)(f)504321022125046121025142216123252212第40页/共87页42n n辅辅辅辅助助助助数数数数组组组组closedgeclosedge，记记记记录录

36、录录从从从从U U U U到到到到V-UV-UV-UV-U具具具具有有有有最最最最小小小小代代代代价价价价的的的的边边边边。对对对对每每每每个个个个v vi i V-UV-U，对对对对应应应应地地地地closedgei-1closedgei-1包包包包含含含含两个域：两个域：两个域：两个域：uu adjvexadjvex：存存存存放放放放生生生生成成成成树树树树上上上上的的的的顶顶顶顶点点点点信信信信息息息息uulowcostlowcost：存放该边上的权值。：存放该边上的权值。：存放该边上的权值。：存放该边上的权值。closedgei-closedgei-1.lowcost=mincost(

37、u,v1.lowcost=mincost(u,vi i)u u U U 50461322810251424221618120 1 2 3 4 5 60 1 2 3 4 5 6第41页/共87页43iclosedge123456UV-Ukadjvexlowcost01,2,3,4,5,6adjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcostadjvexlowcost50280100,51,2,3,4,602852540,5,41,2,3,602842242430,5,4,31,2,602831231820,5,4,3,21,62163181114

38、660,5,4,3,2,1第42页/共87页45克鲁斯卡尔克鲁斯卡尔克鲁斯卡尔克鲁斯卡尔(KruskalKruskal)算法算法算法算法-连通分量不断合并的过程连通分量不断合并的过程连通分量不断合并的过程连通分量不断合并的过程基本思想：为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。第44页/共87页46具体作法：设连通网N=(V,E),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,),图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，

39、则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点都在同一连通分量上为止。第45页/共87页4750461322810251424221618原图120211334405362646511012141618222425285061324第46页/共87页例例1654326513566425dataset124536124536124536vexhweight112213233544vextflag615355000000013425678933455666642600001111142111222216543212345第47页/共87页49练习：练习：abc

40、dfeg195321271814168712第48页/共87页507.5 7.5 有向无环图及其应有向无环图及其应用用n n有向无环图：一个无环的有向图称为有向无环图,简称DAG图。n n注意有向树、DAG图和有向图的区别。第49页/共87页51 几乎所有的工程都可分为若干个称作活动“的子工程，并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才能开始。对整个工程和系统，人们关心的是两方面的问题：u工程能否顺利进行？u完成整个工程所必须的最短时间？对应到有向图即为进行拓扑排序和求关键路径。DAG图通常用来描述一项工程或系统的进行过程第50页/共87页527.

41、5.1 拓扑排序拓扑排序n n例如，计算机专业学生的所有课例如，计算机专业学生的所有课程学习就是一个工程，每一门课程学习就是一个工程，每一门课程的学习就是整个工程的一些活程的学习就是整个工程的一些活动。其中有些课程要求先修课程，动。其中有些课程要求先修课程，有些则不要求。这样在有的课程有些则不要求。这样在有的课程之间有领先关系，有的课程可以之间有领先关系，有的课程可以并行地学习。并行地学习。一、用顶点表示活动的网络(AOV网络)第51页/共87页53 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程

42、序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 课程代号课程代号 课程名称课程名称 先修课程先修课程第52页/共87页54学生课程学习工程图C8C3C5C4C9C6C7C1C2第53页/共87页55n n可以用有向图表示一个工程。可以用有向图表示一个工程。在这种有向图中，用顶点表示在这种有向图中，用顶点表示活动，用有向边活动，用有向边表示活表示活动动Vi 必须先于活动必须先于活动Vj 进行。这进行。这种有向图叫做种有向图叫做顶点表示活动的顶点表示活动的AOV网络网络(Activ

43、ity On Vertices)。n 在AOV网络中不能出现有向回路,即有向 环。如果出现了有向环，则意味着某项活 动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它 是否存在有向环。第54页/共87页56n n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它的拓扑有序序网络构造它的拓扑有序序列。即将各个顶点列。即将各个顶点(代表各个代表各个活动活动)排列成一个线性有序的序排列成一个线性有序的序列，使得列，使得AOV网络中所有应存网络中所有应存在的前驱和后继关系都能得到在的前驱和后继关系都能得到满足。满足。n n这种构造这种构造AOV网络全部顶点的网络全部顶点的拓扑

44、有序序列的运算就叫做拓拓扑有序序列的运算就叫做拓扑排序。扑排序。n n如果通过拓扑排序能将如果通过拓扑排序能将AOV网网络的所有顶点都排入一个拓扑络的所有顶点都排入一个拓扑有序的序列中有序的序列中,则该网络中必定则该网络中必定不会出现有向环。不会出现有向环。第55页/共87页57拓扑排序的方拓扑排序的方拓扑排序的方拓扑排序的方法法法法 输入输入AOV网络。令网络。令 n 为顶点个为顶点个数。数。在在AOV网络中选一个入度为网络中选一个入度为0(没有前驱没有前驱)的顶点的顶点,并输出之并输出之;从图中删去该顶点从图中删去该顶点,同时删去它同时删去它的所有出边的所有出边;重复以上重复以上、步步,直

45、到直到 全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或拓扑排序完成；或拓扑排序完成；或拓扑排序完成；或 图中还有未输出的顶点图中还有未输出的顶点图中还有未输出的顶点图中还有未输出的顶点,但已跳出处理但已跳出处理但已跳出处理但已跳出处理循环。说明图中还剩下一些顶点循环。说明图中还剩下一些顶点循环。说明图中还剩下一些顶点循环。说明图中还剩下一些顶点,它们都它们都它们都它们都有直接前驱。这时网络中必存在有向环。有直接前驱。这时网络中必存在有向环。有直接前驱。这时网络中必存在有向环。有直接

46、前驱。这时网络中必存在有向环。第56页/共87页58C0C1C2C3C4C5拓扑排序的过程(a)有向无环图有向无环图(b)输出顶点输出顶点C4(c)输出顶点输出顶点C0C2C5C1C0C3C4C1C2C5C3C0C2C5C1C3(d)输出顶点输出顶点C3第57页/共87页59C1C2C5(e)输出顶点输出顶点C2C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5 最后得到的拓扑有序序列为 C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。(h)拓扑排序完成拓扑排序完成第58页/共87页60n n

47、如果如果AOV网络中存在有向环，网络中存在有向环，此此AOV网络所代表的工程是不网络所代表的工程是不可行的。可行的。n n例如例如,对学生选课工程图进行拓对学生选课工程图进行拓扑排序扑排序,得到的拓扑有序序列为得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第59页/共87页61AOV网络及其邻接表表示网络及其邻接表表示C0C1C2C3C4C5 C0 C1 C2 C3 C4 C5 012345indegree data firstarc 130103 1 adjvex nexta

48、rc 3 5 1 5 0 1 5 第60页/共87页62n n使用一个存放入度为零的顶点使用一个存放入度为零的顶点的栈的栈,供选择和输出无前驱的顶供选择和输出无前驱的顶点。点。n n拓扑排序算法可描述如下：拓扑排序算法可描述如下：uu建立入度为零的顶点栈建立入度为零的顶点栈建立入度为零的顶点栈建立入度为零的顶点栈;uu当入度为零的顶点栈不空时当入度为零的顶点栈不空时当入度为零的顶点栈不空时当入度为零的顶点栈不空时,重复执行重复执行重复执行重复执行 从顶点栈中退出一个顶点从顶点栈中退出一个顶点从顶点栈中退出一个顶点从顶点栈中退出一个顶点,并输出并输出并输出并输出之之之之;从从从从AOVAOV网络

49、中删去这个顶点和它发网络中删去这个顶点和它发网络中删去这个顶点和它发网络中删去这个顶点和它发出的边出的边出的边出的边,边的终顶点入度减一边的终顶点入度减一边的终顶点入度减一边的终顶点入度减一;如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至0,0,则该顶则该顶则该顶则该顶点进入度为零的顶点栈点进入度为零的顶点栈点进入度为零的顶点栈点进入度为零的顶点栈;uu 如果输出顶点个数少于如果输出顶点个数少于如果输出顶点个数少于如果输出顶点个数少于AOVAOV网络的顶网络的顶网络的顶网络的顶点个数点个数点个数点个数,则报告网络中存在有向环。则报告网络中存在有向环。则

50、报告网络中存在有向环。则报告网络中存在有向环。第61页/共87页65二、用边表示活动的网络二、用边表示活动的网络二、用边表示活动的网络二、用边表示活动的网络(AOE(AOE网络网络网络网络)n n有向边有向边活动活动(Activity)n n边上权值边上权值活动持续时活动持续时间间(Duration)n n顶点顶点事件事件(Event 或时间点或时间点)这样的有向图叫做这样的有向图叫做用边表示活动用边表示活动的网络的网络,简称简称 AOE(Activity On Edges)网络网络。n AOE网络在某些工程估算方面非常有用。例如，可以使人们了解：完成整个工程至少需要多少时间(假设网络中没有环

51、)?为缩短完成工程所需的时间,应当加快哪些活动?第64页/共87页66n n正常情况下，网中只有正常情况下，网中只有一个一个入度入度为零的点（为零的点（源点源点）和一个出度为）和一个出度为零的点（零的点（汇点汇点）。）。n n从源点到各个顶点从源点到各个顶点,以至从源点以至从源点到汇点的有向路径可能不止一条。到汇点的有向路径可能不止一条。这些路径的长度也可能不同。这些路径的长度也可能不同。完成不同路径的活动所需的时间完成不同路径的活动所需的时间虽然不同虽然不同,但只有各条路径上所但只有各条路径上所有活动都完成了有活动都完成了,整个工程才算整个工程才算完成。完成。n n完成整个工程所需的时间完成

52、整个工程所需的时间（最短（最短时间）时间）取决于取决于从源点到汇点的最从源点到汇点的最长路径长度长路径长度,即在这条路径上所即在这条路径上所有活动的持续时间之和。这条有活动的持续时间之和。这条路路径长度最长径长度最长的路径就叫做的路径就叫做关键路关键路径径(Critical Path)。第65页/共87页67n要找出关键路径，必须找出关键活动,即不按期完成就会影响整个工程完成的活动。n关键路径上的所有活动都是关键活动。因此,只要找到了关键活动,就可以找到关键路径。例如,下图就是一个AOE网。第66页/共87页68定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量：定义几个与计算关键

53、活动有关的量：定义几个与计算关键活动有关的量：事件事件Vk 的最早发生时间的最早发生时间Ve(k)是是从从源源点点V1 到到顶顶点点Vk 的的最最长长路路径长度。径长度。Ve1=0 Vek=maxVej+dut()事件Vj 的最迟发生时间Vlj 是在保证汇点Vn 在Ven 时刻完成的前提下，事件Vj 的允许的最迟开始时间。Vln=Ven Vlj=minVlk-dut()jk第67页/共87页69 活动活动ai 的最早开始时间的最早开始时间 ei 设设活活动动ai 在在边边上上,则则ei是是从从源源点点V1到到顶顶点点Vj 的的最最长长路径长度。因此路径长度。因此,ei=Vej。jkai 活动a

54、i 的最迟开始时间 li li是在不会引起时间延误的前提下,该活动允许的最迟开始时间。li=Vlk-dut()其中,dut()是完成 ai 所需的时间。第68页/共87页70 时间余量时间余量 li-ei 表示活动表示活动 ai 的最早开始时间和的最早开始时间和最迟开始时间的时间余量。最迟开始时间的时间余量。li=ei 表示活动表示活动 ai 是没有时间是没有时间余量的余量的关键活动关键活动。第69页/共87页71n n求求求求VeVe和和和和VlVl的递推公式的计算必须分别在的递推公式的计算必须分别在的递推公式的计算必须分别在的递推公式的计算必须分别在拓扑有拓扑有拓扑有拓扑有序序序序及及及及

55、逆拓扑有序逆拓扑有序逆拓扑有序逆拓扑有序的前提下进行。的前提下进行。的前提下进行。的前提下进行。n n为了简化算法为了简化算法为了简化算法为了简化算法,假定在求关键路径之前已经对各假定在求关键路径之前已经对各假定在求关键路径之前已经对各假定在求关键路径之前已经对各顶点实现了拓扑排序顶点实现了拓扑排序顶点实现了拓扑排序顶点实现了拓扑排序,并按拓扑有序的顺序对各并按拓扑有序的顺序对各并按拓扑有序的顺序对各并按拓扑有序的顺序对各顶点重新进行了编号。顶点重新进行了编号。顶点重新进行了编号。顶点重新进行了编号。第70页/共87页n n求关键路径步骤求关键路径步骤n n求求Ve(i)Ve(i)n n求求V

56、l(j)Vl(j)n n求求e(i)e(i)n n求求l(i)l(i)n n计算计算l(i)-e(i)l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动活动 e l l-e 00002266046258377077071031616014140033=Ve(j)=Vl(k)-dut()第71页/共87页731324a1=8a2=125678a10=12a9=6a

57、8=18a5=28a6=8a7=6a3=14a4=10VeVl1 2 3 4 5 6 7 8el1 2 3 4 5 6 7 8 9 1008122228404658584640282212800 0 812 12 22 2228404600812123222284046 第72页/共87页74利用关键路径法求利用关键路径法求AOEAOE网的各关键活动网的各关键活动算法算法 P.185P.185第73页/共87页75注意在拓扑排序求在拓扑排序求VeVe i 和逆拓扑有序求和逆拓扑有序求VlVl i 时时,所需为所需为 O(O(n n+e e),),求各个活动的求各个活动的e e k k 和和l

58、l k k 时所需时间为时所需时间为O(O(e e),),总总 共花费时间仍然是共花费时间仍然是O(O(n n+e e)。仅计算 Vei 和 Vli 是不够的，还须计算 ek 和 lk。不是任一关键活动加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上都有的关键活动。第74页/共87页767.6 最短路径最短路径(Shortest Path)n n最短路径问题：最短路径问题：如果从图中某如果从图中某一顶点一顶点(称为源点称为源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能不止一条，的路径可能不止一条，如何找到一条路径使得沿此路如何找到一条路径使得沿此路径上各边上的权值

59、总和达到最径上各边上的权值总和达到最小。小。n n问题解法问题解法uu单源最短路径问题单源最短路径问题单源最短路径问题单源最短路径问题 Dijkstra Dijkstra算法算法算法算法uu所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径 Floyd Floyd算法算法算法算法第75页/共87页77n n问题的提法：问题的提法：给定一个带权有给定一个带权有向图向图D与源点与源点 v，求从，求从 v 到到D中中其它顶点的最短路径。限定各其它顶点的最短路径。限定各边上的权值大于或等于边上的权值大于或等于0。n n为求得这些最短路径为求得这些最短路径,Dijk

60、stra提出提出按路径长度的递增次序按路径长度的递增次序,逐步产生最短路径的算法。逐步产生最短路径的算法。一、单源最短路径(Dijkstra算法)第76页/共87页78v0(v0,v1)10源点终点 最 短路 径路径长度(v0,v1,v2)(v0,v3,v2)(v0,v3)30 v1 v2 v3 v4100(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)例例例例1 1：6001234 509070(v0,v1,v2,v4)60第77页/共87页79对各最短路径按对各最短路径按对各最短路径按对各最短路径按路径长度递增路径长度递增路径长度递增路径长度递增排列排列排列排列v0(v0,v1

61、)10源点终点 最 短路 径路径长度(v0,v3,v2)(v0,v3)30 v1 v3 v2 v4(v0,v3,v2,v4)5060可证明从源点V0到某顶点Vk的最短路径，必定或是从V0到Vk的直接路径（仅含一条弧）；或是从V0经中间顶点顶点vivi到Vk的路径，其中中间顶点vi是指已求得的最短路径的顶点或顶点序列）。第78页/共87页80n n引入辅助数组引入辅助数组d。它的每一个分。它的每一个分量量di表示当前找到的从表示当前找到的从源点源点 v0到到终点终点 vi 的最短路径的长度。初的最短路径的长度。初始状态：始状态：n n 若从源点若从源点若从源点若从源点v v0 0到顶点到顶点到顶

62、点到顶点 v vi i 有边有边有边有边,则则则则didi为该边为该边为该边为该边上的权值；上的权值；上的权值；上的权值；n n 若从源点若从源点若从源点若从源点v v0 0到顶点到顶点到顶点到顶点 v vi i 无边无边无边无边,则则则则didi为为为为 。n 假设 S 是已求得的最短路径的终点的集合，则可证 明：下一条最短路径必然是从v0 出发，中间只经过 S 中的顶点便可到达的那些顶点vx(vxV-S)的路径 中的一条。n 每次求得一条最短路径后,其终点vk 加入集合S，然后对所有的vi V-S，修改其 di值。第79页/共87页8101234106010020503010终点 1 2

63、3 4 vj Si=1 10 30 100i=2i=3i=41 0,1 60 30 1003 0,1,3 50 902 0,1,3,2 604 0,1,3,2,4源点终点最短路径路径长度0110250330460第80页/共87页82DijkstraDijkstra算法算法算法算法 初始化：初始化：初始化：初始化：S vS v0 0;dj G.arcs0j,j=1,2,n-1;dj G.arcs0j,j=1,2,n-1;/n/n为图中顶点个数为图中顶点个数为图中顶点个数为图中顶点个数求出最短路径的长度：求出最短路径的长度：求出最短路径的长度：求出最短路径的长度：dk min d i,dk mi

64、n d i,i i V-SV-S;S S S S U U k k ;修改：修改：修改：修改：di min di,dk+G.arcski,di min di,dk+G.arcski,对于每一个对于每一个对于每一个对于每一个 i i V-SV-S;判断：若判断：若判断：若判断：若 S=V,S=V,则算法结束，否则转则算法结束，否则转则算法结束，否则转则算法结束，否则转 。除除除除d d 外，还要引入外，还要引入外，还要引入外，还要引入final final 和和和和P P 第81页/共87页83练习练习ABCD1220763第82页/共87页84二、每一对顶点之间的最短路径方法一：每次以一个顶点为

65、源点，重复执行Dijkstra算法n次 T(n)=O(n)方法二：弗洛伊德(Floyd)算法算法思想：逐个顶点试探法求最短路径步骤初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束第83页/共87页85n n算法实现定义一个n阶方阵序列D(-1),D(0),D(1),.,D(k),.,D(n-1),其中：其中：D(-1)ij=G.arcsij /初初始化始化D(k)ij=minD(k-1)ij,D(k-1)ik+D(k-1)kj 0kn-1第84页/共87页86例ACB2643110 4 116 0 23 0D(-1)=路径：AB ACBA BCCA0 4 66 0 23 7 0D(1)=路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0D(0)=路径：AB ACBA BCCA CAB0 4 65 0 23 7 0D(2)=路径：AB ABCBCA BCCA CAB求每一对顶点之间的最短路径的示例：第85页/共87页87练习练习ABCD1220763第86页/共87页