《数据结构 第七章 图.ppt》由会员分享，可在线阅读，更多相关《数据结构 第七章 图.ppt（100页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、v图的基本概念图的基本概念v图的存储结构图的存储结构v图的遍历图的遍历v图的连通性问题图的连通性问题 v最小生成树最小生成树v最短路径最短路径 v活动网络活动网络第七章第七章 图图1图的基本概念图的基本概念图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的关及顶点间的关系集合组成的一种数据结构：系集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E1=(x,y)|x,y V 或或 E2=|x,y V&Path(x,y)其中，其中，E1是顶点之间关系的有穷集合，也叫做是顶点之间关系的有穷集合，
2、也叫做边边(edge)集合，此时的图称为无向图。集合，此时的图称为无向图。E2 表示表示从从 x 到到 y 的一条弧，且称的一条弧，且称x为弧尾，为弧尾，y为弧头，这为弧头，这样的图称为有向图。样的图称为有向图。2n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无是无序的。序的。n完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,则此图为则此图为无向完全图无向完全图。有。有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边条边,则此图为则此图为有向完全图有向完全
3、图。000011112222654333 n邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点。互为邻接顶点。n子图子图 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为称之为权。这种带权图叫做网络。权。这种带权图叫做网络。0123子图子图01301230234n顶点的度顶点的度 一个顶点一个顶点v的度是与它相关联的的度是与它相关联的边的条数。记作边的条数。记作TD(v)。在有向图中在有
4、向图中,顶点顶点的度等于该顶点的入度与出度之和。的度等于该顶点的入度与出度之和。n顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条为终点的有向边的条数数,记作记作 ID(v);顶点顶点 v 的出度的出度是以是以 v 为始为始点的有向边的条数点的有向边的条数,记作记作 OD(v)。n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出出发发,沿一些边经过一些顶点沿一些边经过一些顶点 vp1,vp2,vpm，到达顶点到达顶点vj。则称顶点序列则称顶点序列(vi vp1 vp2.vpm vj)为从顶点为从顶点vi 到顶点到顶点 vj 的路径。的路径。它经过的边它经过的边(vi,
5、vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E的边。的边。5顶点的出度顶点的出度:以顶点以顶点v 为弧尾的弧的数目为弧尾的弧的数目;顶点的入度顶点的入度:以顶点以顶点v v为为弧头的弧的数目。弧头的弧的数目。ABECF有向图有向图顶点的度顶点的度(TD)=)=出度出度(OD)+)+入度入度(ID)TD(B)=OD(B)+ID(B)=3例如例如:6n路径长度路径长度 非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权的条数。带权图的路径长度是指路径上各边的权之和。之和。n简单路径简单路径 若路径上各顶点若路径上各顶点
6、v1,v2,.,vm 均不均不 互互相重复相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n简单回路简单回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。0123012301237ABECF如如:从从A A到到F F长度为长度为 3 的路径的路径A,B,C,F8n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从若从顶点顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是是连通的。如果图中任意一对顶点都是连通连通的。如果图中任意一对顶点都是连通的的,则称此图是连
7、通图。非连通图的则称此图是连通图。非连通图的极大极大连通子图连通子图叫做连通分量。叫做连通分量。n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中,若对于每一对顶点若对于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是强连通则称此图是强连通图。非强连通图的极大强连通子图叫做强图。非强连通图的极大强连通子图叫做强连通分量。连通分量。9无向图无向图,若图中任意两若图中任意两个顶点之间都有路径相个顶点之间都有路径相通，则称此图为通，则称此图为连通图连通图;若无向图为非连通图，若无向图为非连通图，则图中各个极大连通子则图中各个极大连
8、通子图称作此图的图称作此图的连通分量连通分量。BACDFEBACDFE10有向图有向图,若任意两个顶点之间都存在一条有向路若任意两个顶点之间都存在一条有向路径，则称此有向图为径，则称此有向图为强连通图强连通图。否则，其各个强连通子图称作它的否则，其各个强连通子图称作它的强连通分量强连通分量。ABECFABECF11生成树生成树:假设一个连通图有假设一个连通图有n个顶点和个顶点和e 条边，条边，其中其中n-1条边和条边和n个顶点构成一个个顶点构成一个极小连通子图极小连通子图，称该极小连通子图为此连通图的称该极小连通子图为此连通图的生成树生成树。在极极小连通子图中增加一条边，则一定有环。小连通子图
9、中增加一条边，则一定有环。在极小连通子图中去掉一条边，则成为非连通极小连通子图中去掉一条边，则成为非连通图。图。BACDFEBACDFE12有有n个个顶点，顶点，n-1条边的图必定是生成树吗？条边的图必定是生成树吗？对非连通图，则称由各个连通分量的生成对非连通图，则称由各个连通分量的生成树的集合为此非连通图的树的集合为此非连通图的生成森林生成森林。BACDFEBACDFE13图的存储结构图的存储结构n在图的邻接矩阵表示中，有一个记录各个在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。点之间关系的邻接矩阵。n设图设
10、图 A=(V,E)是一个有是一个有 n 个顶点的图个顶点的图,图图的邻接矩阵是一个二维数组的邻接矩阵是一个二维数组 A.edgenn，定义：定义：邻接矩阵邻接矩阵(Adjacency Matrix)14n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。012301215n在有向图中在有向图中,统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的出度，统计第的出度，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的入度。的入度。n在无向图中在无向图中,统计第统计第 i 行行(列列)1 的个数可得的个数可得顶点
11、顶点i 的度。的度。16186329542031网络的邻接矩阵网络的邻接矩阵17#define MaxValue Int_Maxconst int NumEdges=50;/边条数边条数const int NumVertices=10;/顶点个数顶点个数typedef char VertexData;/顶点数据类型顶点数据类型 typedef int EdgeData;/边上权值类型边上权值类型typedef struct VertexData vexListNumVertices;/顶点表顶点表 EdgeData EdgeNumVerticesNumVertices;/邻接矩阵邻接矩阵,可视
12、为边之间的关系可视为边之间的关系 int n,e;/图中当前的顶点个数与边数图中当前的顶点个数与边数 MTGraph;用邻接矩阵表示的结构定义用邻接矩阵表示的结构定义18邻接表邻接表(Adjacency List)邻接表邻接表:是图的一种链式存储结构。是图的一种链式存储结构。弧的结点结构弧的结点结构adjvex;/该弧所指向的顶点的位置该弧所指向的顶点的位置nextarc;/指向下一条弧指针指向下一条弧指针 info;/该弧相关信息的指针该弧相关信息的指针adjvex nextarc info顶点的结点结构顶点的结点结构 data firstarc data;/顶点信息顶点信息firstarc
13、;/指向第一条依附该顶点的弧指向第一条依附该顶点的弧19无向图的邻接表无向图的邻接表 同一个顶点发出的边链接在同一个边链表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边中，每一个链结点代表一条边(边结点边结点),结点中有另一顶点的下标结点中有另一顶点的下标 dest 和指针和指针 link。ABCDdata adjABCD0123dest linkdest link 13021020有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABCdata adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adjABC012dest link逆邻
14、接表逆邻接表(入边表入边表)102 01121n网络网络(带权图带权图)的邻接表的邻接表BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)22n带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 cost。n顶点顶点 i 的边链表的表头指针的边链表的表头指针 adj 在顶点表的在顶点表的下标为下标为 i 的顶点记录中，该记录还保存了该的顶点记录中，该记录还保存了该顶点的其它信息。顶点的其它信息。n在邻接表的边链表中，各个边结点的链入在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入
15、次序而定。顺序任意，视边结点输入次序而定。n设图中设图中有有 n 个顶点个顶点，e 条边，则用邻接表表条边，则用邻接表表示无向图时，需要示无向图时，需要 n 个顶点结点，个顶点结点，2e 个边个边结点；用邻接表表示有向图时，若不考虑结点；用邻接表表示有向图时，若不考虑逆邻接表，只需逆邻接表，只需 n 个顶点结点，个顶点结点，e 个边结点个边结点。23typedef char VertexData;/顶点数据类型顶点数据类型typedef int EdgeData;/边上权值类型边上权值类型typedef struct node /边结点边结点 int dest;/目标顶点下标目标顶点下标 Ed
16、geData cost;/边上的权值边上的权值 Struct node*link;/下一边链接指针下一边链接指针 EdgeNode;邻接表表示的图的定义（为算法）邻接表表示的图的定义（为算法）26typedef struct /顶点结点顶点结点 VertexData data;/顶点数据域顶点数据域 EdgeNode*firstAdj;/边链表头指针边链表头指针 VertexNode;typedef struct /图的邻接表图的邻接表 VertexNode VexList NumVertices;/邻接表邻接表 int n,e;/图中当前的顶点个数与边数图中当前的顶点个数与边数 AdjGra
17、ph;27邻接表的构造算法邻接表的构造算法(无向图无向图)void CreateGraph(AdjGraph G)cin G.n G.e;/输入顶点个数和边数输入顶点个数和边数 for(int i=0;i G.VexListi.data;/输入顶点信息输入顶点信息 G.VexListi.firstAdj=NULL;for(i=0;i tail head weight;EdgeNode*p=new EdgeNode;p-dest=head;p-cost=weight;28 /链入第链入第 tail 号链表的前端号链表的前端 p-link=G.VexListtail.firstAdj;G.VexL
18、isttail.firstAdj=p;p=new EdgeNode;p-dest=tail;p-cost=weight;/链入第链入第 head 号链表的前端号链表的前端 p-link=G.VexListhead.firstAdj;G.VexListhead.firstAdj=p;29图的遍历图的遍历n从图中某一顶点出发访遍图中所有的顶点，从图中某一顶点出发访遍图中所有的顶点，且使每个顶点仅被访问一次，这一过程就且使每个顶点仅被访问一次，这一过程就叫做图的遍历叫做图的遍历(Traversing Graph)。n图中可能存在回路，且图的任一顶点都可图中可能存在回路，且图的任一顶点都可能与其它顶点
19、相通，在访问完某个顶点之能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过后可能会沿着某些边又回到了曾经访问过的顶点。的顶点。n为了避免重复访问，可设置一个标志顶点为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组是否被访问过的辅助数组 visited 。30n辅助数组辅助数组 visited 的初始状态为的初始状态为 0,在图在图的遍历过程中的遍历过程中,一旦某一个顶点一旦某一个顶点 i 被访问被访问,就立即让就立即让 visited i 为为 1,防止它被多次访防止它被多次访问。问。n两种图的遍历方法两种图的遍历方法:u深度优先搜索深度优先搜索 DFS(Dep
20、th First Search)u广度优先搜索广度优先搜索 BFS(Breadth First Search)31深度优先搜索深度优先搜索DFS(Depth First Search)n深度优先搜索过程深度优先搜索过程67ACDEGBFIHACDEGBFIH1234589123456789前进回退深度优先生成树深度优先生成树32nDFS 在访问图中某一起始顶点在访问图中某一起始顶点 v 后后,由由 v 出出发发,访问它的任一邻接顶点访问它的任一邻接顶点 w1;再从再从 w1 出发出发,访问与访问与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2;然后再从然后再从 w2 出发出发,
21、进行类似的访问进行类似的访问,如此如此进行下去进行下去,直至到达所有的邻接顶点都被访直至到达所有的邻接顶点都被访问过的顶点问过的顶点 u 为止。接着为止。接着,退回一步退回一步,退到退到前一次刚访问过的顶点前一次刚访问过的顶点,看是否还有其它没看是否还有其它没有被访问的邻接顶点。如果有有被访问的邻接顶点。如果有,则访问此顶则访问此顶点点,之后再从此顶点出发之后再从此顶点出发,进行与前述类似进行与前述类似的访问的访问;如果没有如果没有,就再退回一步进行搜索。就再退回一步进行搜索。重复上述过程重复上述过程,直到连通图中所有顶点都被直到连通图中所有顶点都被访问过为止访问过为止。33 图的深度优先搜索
22、算法图的深度优先搜索算法void Graph_Traverse(AdjGraph G)int*visited=new int NumVertices;for(int i=0;i G.n;i+)visited i=0;/访问数组访问数组 visited 初始化初始化 for(int i=0;i G.n;i+)if(!visitedi)DFS(G,i,visited);/从顶点从顶点 i 出发开始搜索出发开始搜索 delete visited;/释放释放 visited 34void DFS(AdjGraph G,int v,int visited )cout GetValue(G,v);/访问顶
23、点访问顶点 v visitedv=1;/顶点顶点 v 作访问标记作访问标记 int w=GetFirstNeighbor(G,v);/取取 v 的第一个邻接顶点的第一个邻接顶点 w while(w!=-1)/若邻接顶点若邻接顶点 w 存在存在 if(!visitedw)DFS(G,w,visited);/若若顶点顶点 w 未访问过未访问过,递归访问顶点递归访问顶点 w w=GetNextNeighbor(G,v,w);/取顶点取顶点 v 排在排在 w 后的下一个邻接顶点后的下一个邻接顶点 35广度优先搜索广度优先搜索BFS(Breadth First Search)n广度优先搜索过程广度优先搜
24、索过程ACDEGBFIHACDEGBFH123456789123456789广度优先生成树广度优先生成树I36nBFS在访问了起始顶点在访问了起始顶点 v 之后之后,由由 v 出发出发,依依次访问次访问 v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1,w2,wt,然后再顺序访问然后再顺序访问 w1,w2,wt 的所有还未被访问过的邻接顶点。再从这些的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，被访问过的邻接顶点，如此做下去，直如此做下去，直到图中所有顶点都被访问到为止。到图中所有顶点都被访问
25、到为止。n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程,每向每向前走一步可能访问一批顶点前走一步可能访问一批顶点,不像深度优先不像深度优先搜索那样有往回退的情况。因此搜索那样有往回退的情况。因此,广度优先广度优先搜索不是一个递归的过程。搜索不是一个递归的过程。37n为了实现逐层访问为了实现逐层访问,算法中使用了一个队列算法中使用了一个队列,以记忆正在访问的这一层和下一层的顶点以记忆正在访问的这一层和下一层的顶点,以便于向下一层访问。以便于向下一层访问。n为避免重复访问为避免重复访问,需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。给被访问过的顶点
26、加标记。图的广度优先搜索算法图的广度优先搜索算法void Graph_Traverse(AdjGraph G)for(int i=0;i G.n;i+)if(!visitedi)BFS(G,i,visited);38void BFS(AdjGraph G,int v,int visited )cout GetValue(v);visitedv=1;Queue q;InitQueue(&q);EnQueue(&q,v);/进队列进队列 while(!QueueEmpty(&q)/队空搜索结束队空搜索结束 DeQueue(&q,v);int w=GetFirstNeighbor(G,v);whil
27、e(w!=-1)/若邻接顶点若邻接顶点 w 存在存在 if(!visitedw)/未访问过未访问过 cout GetValue(w);39 visitedw=1;EnQueue(&q,w);w=GetNextNeighbor(G,v,w);/重复检测重复检测 v 的所有邻接顶点的所有邻接顶点 /外层循环，判队列空否外层循环，判队列空否 delete visited;40 连通分量连通分量(Connected component)n当无向图为非连通图时当无向图为非连通图时,从图中某一顶点出从图中某一顶点出发发,利用深度优先搜索算法或广度优先搜索利用深度优先搜索算法或广度优先搜索算法不可能遍历到图
28、中的所有顶点算法不可能遍历到图中的所有顶点,只能访只能访问到该顶点所在的最大连通子图问到该顶点所在的最大连通子图(连通分量连通分量)的所有顶点。的所有顶点。n若从无向图的每一个连通分量中的一个顶若从无向图的每一个连通分量中的一个顶点出发进行遍历点出发进行遍历,可求得无向图的所有连可求得无向图的所有连通分量。通分量。图的连通性问题图的连通性问题41n求连通分量的算法求连通分量的算法需要对图的每一个顶点需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求
29、得被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。图的另一个连通分量。n对于非连通的无向图，所有连通分量的生对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。成树组成了非连通图的生成森林。42ACDEIBFOGHJNMLK非连通无向图的三个连通分量非连通无向图的三个连通分量AHKCDEIBFOGJNML非连通图的连通分量的极小连通子图非连通图的连通分量的极小连通子图43重连通分量重连通分量(Biconnected Component)n在无向连通图在无向连通图G中中,当且仅当删去当且仅当删去G中的顶中的顶点点v及所有依附于及所有依附于v的所有边后的所有边后,可将图分割可
30、将图分割成两个或两个以上的连通分量，则称顶点成两个或两个以上的连通分量，则称顶点v为关节点。为关节点。n没有关节点的连通图叫做重连通图。没有关节点的连通图叫做重连通图。n在重连通图上在重连通图上,任何一对顶点之间至少存在任何一对顶点之间至少存在有两条路径有两条路径,在删去某个顶点及与该顶点相在删去某个顶点及与该顶点相关联的边时关联的边时,也不破坏图的连通性。也不破坏图的连通性。n一个连通图一个连通图G如果不是重连通图，那么它可如果不是重连通图，那么它可以包括几个重连通分量。以包括几个重连通分量。44n在一个无向连通图在一个无向连通图G中中,重连通分量可以利用深度重连通分量可以利用深度优先生成树
31、找到。优先生成树找到。n在图中各在图中各顶点旁标明的深度优先数顶点旁标明的深度优先数,给出进行深度给出进行深度优先搜索时各顶点访问的次序。优先搜索时各顶点访问的次序。n深度优先生成树的根是关节点的充要条件是它至深度优先生成树的根是关节点的充要条件是它至少有两个子女。少有两个子女。n其它顶点其它顶点 u 是关节点的充要条件是它至少有一个是关节点的充要条件是它至少有一个子女子女 w,从从 w 出发出发,不能通过不能通过 w、w 的子孙及一条的子孙及一条回边所组成的路径到达回边所组成的路径到达 u 的祖先。的祖先。45ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910
32、根有两根有两 个子女个子女关关关关节节节节点点点点关关关关节节节节点点点点关节点关节点关节点关节点46最小生成树最小生成树(minimum cost spanning tree)n使用不同的遍历图的方法，可以得到不同使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得的生成树；从不同的顶点出发，也可能得到不同的生成树。到不同的生成树。n按照生成树的定义按照生成树的定义，n 个顶点的连通网络个顶点的连通网络的生成树有的生成树有 n 个顶点、个顶点、n-1 条边。条边。n构造最小生成树的准则构造最小生成树的准则n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n-1 条边条
33、边来联结网络中的来联结网络中的 n 个顶点；个顶点；n不能使用产生回路的边；不能使用产生回路的边；n各边上的权值的总和达到最小。各边上的权值的总和达到最小。48普里姆普里姆(Prim)算法算法n普里姆算法的普里姆算法的基本思想基本思想：从连通网络从连通网络 N=V,E 中的某一顶点中的某一顶点 u0 出出发发,选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合将其顶点加入到生成树顶点集合U中。中。以后每一步从一个顶点在以后每一步从一个顶点在 U 中中,而另一个而另一个顶点不在顶点不在 U 中的各条边中选择权值最小的中的各条边中选择权值最小的边
34、边(u,v),把它的顶点加入到集合把它的顶点加入到集合 U 中。如中。如此继续下去此继续下去,直到网络中的所有顶点都加入直到网络中的所有顶点都加入到生成树顶点集合到生成树顶点集合 U 中为止。中为止。n采用邻接矩阵作为图的存储表示采用邻接矩阵作为图的存储表示。49252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)5046132102212504612102514221612325221250n在构造过程中，还设置了两个辅助数组：在构造过程中，还设置了两个辅助数组：u lowcost 存存放放生生
35、成成树树顶顶点点集集合合内内顶顶点点到到生成树外各顶点的各边上的当前最小权值；生成树外各顶点的各边上的当前最小权值；u nearvex 记记录录生生成成树树顶顶点点集集合合外外各各顶顶点距离集合内哪个顶点最近点距离集合内哪个顶点最近(即权值最小即权值最小)。n例子例子504613228102514242216181251n若选择从顶点若选择从顶点0出发，即出发，即u0=0，则两个辅助则两个辅助数组的初始状态为：数组的初始状态为：n然后反复做以下工作：然后反复做以下工作：u 在在 lowcost 中选择中选择 nearvexi -1&lowcosti最小的边最小的边,用用 v 标记它。则选中标记
36、它。则选中的权值最小的边为的权值最小的边为(nearvexv,v),相应相应的的权值为权值为 lowcostv。0 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 652u将将 nearvexv 改为改为-1,表示它已加入生表示它已加入生成树顶点集合。成树顶点集合。u将边将边(nearvexv,v,lowcostv)加入加入生成树的边集合。生成树的边集合。u取取 lowcosti=min lowcosti,Edgevi，即用生成树顶点集合外各即用生成树顶点集合外各顶点顶点 i 到刚加入该集合的新顶点到刚加入该集合的新顶点 v 的距的距离离 Edge
37、vi 与原来它们到生成树顶点与原来它们到生成树顶点集合中顶点的最短距离集合中顶点的最短距离lowcosti 做比较做比较,取距离近的作为这些集合外顶点到生成取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。树顶点集合内顶点的最短距离。53uu 如果生成树顶点集合外顶点如果生成树顶点集合外顶点 i 到刚加入到刚加入该集合的新顶点该集合的新顶点 v 的距离比原来它到生的距离比原来它到生成树顶点集合中顶点的最短距离还要近，成树顶点集合中顶点的最短距离还要近，则修改则修改nearvexi:nearvexi=v。表示表示生成树外顶点生成树外顶点i到生成树内顶点到生成树内顶点v当前距离当前距离
38、最近。最近。0 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6选选 v=5选边选边(0,5)54顶点顶点v=5加入生成树顶点集合：加入生成树顶点集合：0 28 25 10 -1 0 0 0 5 -1 0 lowcostnearvex0 1 2 3 4 5 6选选 v=4选边选边(5,4)50461322810251424221618原图 边(0,5,10)加入生成树1204613210255550 1 2 3 4 5 6顶点顶点v=4加入生成树顶点集合：加入生成树顶点集合：0 28 22 25 10 24-1 0 0 4 -1 -1 4 low
39、costnearvex选选 v=3选边选边(4,3)50461322810251424221618原图 边(5,4,25)加入生成树12504613210252256顶点顶点v=3加入生成树顶点集合：加入生成树顶点集合：0 28 12 22 25 10 18-1 0 3 -1 -1 -1 3 lowcostnearvex0 1 2 3 4 5 6选选 v=2选边选边(3,2)50461322810251424221618原图 边(4,3,22)加入生成树1250461321025221257lowcostnearvex0 1 2 3 4 5 6顶点顶点v=2加入生成树顶点集合：加入生成树顶点集
40、合：0 16 12 22 25 10 18-1 2 -1 -1 -1 -1 3 选选 v=1选边选边(2,1)50461322810251424221618原图 边(3,2,12)加入生成树12504132102522161258顶点顶点v=1加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 14-1-1 -1 -1 -1 -1 1 lowcostnearvex0 1 2 3 4 5 6选选 v=6选边选边(1,6)50461322810251424221618原图 边(2,1,16)加入生成树12504613210251422161259lowcostnearvex0
41、 1 2 3 4 5 6顶点顶点v=6加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 14-1-1 -1 -1 -1 -1 -1 50461322810251424221618原图 边(1,6,14)加入生成树12504613210251422161260最后生成树中边集合里存入得各条边为：最后生成树中边集合里存入得各条边为：(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14)利用普里姆算法建立最小生成树利用普里姆算法建立最小生成树void Prim(Graph G,MST&T,int u)float*lowcos
42、t=new floatNumVertices;int*nearvex=new intNumVertices;for(int i=0;i NumVertices;i+)lowcosti=G.Edgeui;/Vu到各点代价到各点代价 nearvexi=u;/及最短带权路径及最短带权路径 61 nearvexu=-1;/加到生成树顶点集合加到生成树顶点集合 int k=0;/存放最小生成树结点的变量存放最小生成树结点的变量 for(i=0;i G.n;i+)if(i!=u)/循环循环n-1次次,加入加入n-1条边条边 EdgeData min=MaxValue;int v=0;for(int j=0
43、;j NumVertices;j+)if(nearvexj!=-1&/=-1不参选不参选 lowcostj min)v=j;min=lowcostj;/求生成树外顶点到生成树内顶点具有最求生成树外顶点到生成树内顶点具有最 /小权值的边小权值的边,v是是当前具最小权值的边当前具最小权值的边 62 if(v)/v=0表示再也找不到要求顶点表示再也找不到要求顶点 Tk.tail=nearvexv;/选边加入生成树选边加入生成树 Tk.head=v;Tk+.cost=lowcostv;nearvexv=-1;/该边加入生成树标记该边加入生成树标记 for(j=0;j G.n;j+)if(nearvex
44、j!=-1&G.Edgevj lowcostj)lowcostj=G.Edgevj;/修改修改 nearvexj=v;63 /循环循环n-1次次,加入加入n-1条边条边n分析以上算法分析以上算法,设连通网络有设连通网络有 n 个顶点个顶点,则则该算法的时间复杂度为该算法的时间复杂度为 O(n2),它适用于边它适用于边稠密的网络。稠密的网络。n注意：当各边有相同权值时，由于选择的随注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。当各边的意性，产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一权值不相同时，产生的生成树是唯一的。的。64活动网络活动网络(Activ
45、ity Network)n计划、施工过程、生产流程、程序流程等都计划、施工过程、生产流程、程序流程等都是是“工程工程”。除了很小的工程外，一般都把。除了很小的工程外，一般都把工程分为若干个叫做工程分为若干个叫做“活动活动”的子工程。完的子工程。完成了这些活动，这个工程就可以完成了。成了这些活动，这个工程就可以完成了。n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程这
46、样在有的课程之间有领先关系，有的课程可以并行地学习。可以并行地学习。用顶点表示活动的网络用顶点表示活动的网络(AOV网络网络)65 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 课程代号课程代号 课程名称课程名称 先修课程先修课程66学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C267n可以用有向图表示一个工程
47、。在这种有向可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边图中，用顶点表示活动，用有向边表示活动表示活动Vi 必须先于活动必须先于活动Vj 进行。这种有进行。这种有向图叫做向图叫做顶点表示活动顶点表示活动的的AOV网络网络(Activity On Vertices)。n在在AOV网络中不能出现有向回路网络中不能出现有向回路,即有向即有向环。如果出现了有向环，则意味着某项活环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。动应以自己作为先决条件。n因此，因此，对给定的对给定的AOV网络，必须先判断它网络，必须先判断它是否存在有向环。是否存在有向环。68n检测有向环的
48、一种方法是对检测有向环的一种方法是对AOV网络构造网络构造它的拓扑有序序列。即将各个顶点它的拓扑有序序列。即将各个顶点(代表各代表各个活动个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系网络中所有应存在的前驱和后继关系都能得到满足。都能得到满足。n这种构造这种构造AOV网络全部顶点的拓扑有序序网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。列的运算就叫做拓扑排序。n如果通过拓扑排序能如果通过拓扑排序能将将AOV网络的所有顶网络的所有顶点都排入一个拓扑有序的序列中点都排入一个拓扑有序的序列中,则该网络则该网络中必定不会出现有向环。中必定不
49、会出现有向环。69n如果如果AOV网络中存在有向网络中存在有向环，此环，此AOV网络网络所代表的工程是不可行的。所代表的工程是不可行的。n例如例如,对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序,得得到的拓扑有序序列为到的拓扑有序序列为 C1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C270拓扑排序的方法拓扑排序的方法 输入输入AOV网络网络。令。令 n 为顶点个数。为顶点个数。在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点,并输出之并输出之;从图中删去该顶点从图中
50、删去该顶点,同时删去所有它发出同时删去所有它发出的有向边的有向边;重复以上重复以上、步步,直到直到 全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或拓扑排序完成；或 图中还有未输出的顶点图中还有未输出的顶点,但已跳出处理但已跳出处理循环。说明图中还剩下一些顶点循环。说明图中还剩下一些顶点,它们都它们都有直接前驱。这时网络中必存在有向环。有直接前驱。这时网络中必存在有向环。71C0C1C2C3C4C5拓扑排序的过程拓扑排序的过程(a)有向无环图有向无环图C2C5C1C0C3(b)输出顶点输出顶点C4C1C2C5C3(c)输出顶点输出顶点C0C4C0C2C5