《空调维修案例.ppt》由会员分享，可在线阅读，更多相关《空调维修案例.ppt（89页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、n n图的基本概念图的基本概念n n图的存储表示图的存储表示n n图的遍历与连通性图的遍历与连通性 n n最小生成树最小生成树n n最短路径最短路径 n n活动网络活动网络7.1 图的基本概念图的基本概念n n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点及顶点间的关系集合组成的一种数据结构间的关系集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E=(x,y)|x,y V 或或 E=|x,y V&Path(x,y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edg
2、e)集合。集合。Path(x,y)表示从表示从 x 到到 y 的的一条单向通路一条单向通路,它是有方向的。它是有方向的。n n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无序的。是无序的。n n完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点个顶点的有向图有的有向图有n(n-1)条边条边,则此图为完全有向则此图为完全有向图。图。00001111222265433 n n邻接顶点邻接顶点 如果如果(u,v)是
3、是 E(G)中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点互为邻接顶点。n n子图子图 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。n n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为称之为权。这种带权图叫做网络。权。这种带权图叫做网络。0123子图子图0130123023n n顶点的度顶点的度 一个顶点一个顶点v的度是与它相关联的的度是与它相关联的边的条数。记作边的条数。记作TD(v)。在有向图中在有向图中,顶点顶点的度等于该顶点的入度与出度之和。的度等于该顶点的入度与出度
4、之和。n n顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度的出度是以是以 v 为始点的为始点的有向边的条数有向边的条数,记作记作 OD(v)。n n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿一些边经过一些顶点沿一些边经过一些顶点 vp1,vp2,vpm，到到达顶点达顶点vj。则称顶点序列则称顶点序列(vi vp1 vp2.vpm vj)为从顶点为从顶点vi 到顶点到顶点 vj 的路径的路径。它经过的。它经过的边边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是应是属于属于
5、E的边。的边。n n路径长度路径长度 非带权图的路径长度是指此路径非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上边的条数。带权图的路径长度是指路径上各边的权之和。上各边的权之和。n n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均均不不 互相重复互相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个与最后一个顶点顶点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。012301230123n n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从
6、顶点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通是连通的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通则称此图是连通图。非连通图的极大连通子图叫做连通分量。子图叫做连通分量。n n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中,若对若对于每一对顶点于每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和和从从vj到到vi的路径的路径,则称此图是强连通图。非则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分强连通图的极大强连通子图叫做强连通分量。量。n n生成树生成树 一个连
7、通图的生成树是其极小连通一个连通图的生成树是其极小连通子图，子图，在在n个顶点的情形下，个顶点的情形下，有有n-1条边。条边。图的抽象数据类型图的抽象数据类型class Graph public:Graph();void InsertVertex(Type&vertex);void InsertEdge(int v1,int v2,int weight);void RemoveVertex(int v);void RemoveEdge(int v1,int v2);int IsEmpty();Type GetWeight(int v1,int v2);int GetFirstNeighbor(
8、int v);int GetNextNeighbor(int v1,int v2);7.2 图的存储表示图的存储表示n n在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个记录各个顶记录各个顶点信息点信息的的顶点表顶点表，还有一个还有一个表示各个顶点之表示各个顶点之间关系间关系的的邻接矩阵邻接矩阵。n n设图设图 A=(V,E)是一个有是一个有 n 个顶点的图个顶点的图,图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn，定定义：义：1邻接矩阵邻接矩阵(Adjacency Matrix)n n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n n有向图的邻接矩阵可能
9、是不对称的。有向图的邻接矩阵可能是不对称的。0123012n n在有向图中在有向图中,统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出度出度，统计第，统计第 j 行行 1 的个数可得顶点的个数可得顶点 j 的的入度入度。n n在无向图中在无向图中,统计第统计第 i 行行(列列)1 的个数可得的个数可得顶点顶点i 的的度度。网络的邻接矩阵网络的邻接矩阵863129542031用邻接矩阵表示的图的类的定义用邻接矩阵表示的图的类的定义const int MaxEdges=50;const int MaxVertices=10;template class Graph privat
10、e:SeqList VerticesList(MaxVertices);float EdgeMaxVerticesMaxVertices;int numberEdges;int numberVertices;int GetVertexPos(int vertex);public:Graph(int sz=MaxEdges);int GraphEmpty()const return VerticesList.IsEmpty();int GraphFull()const return VerticesList.IsFull()|CurrentEdges=MaxEdges;int NumberOfV
11、ertices()return VerticesList.last+1;int NumberOfEdges()return CurrentEdges;Type GetValue(int i)return i=0&i=VerticesList.last?VerticesList.datai:NULL;DistType GetWeight(int v1,int v2);int GetFirstNeighbor(int v);int GetNextNeighbor(int v1,int v2);void InsertVertex(const Type vertex);void InsertEdge
12、(int v1,int v2,float weight);void RemoveVertex(int v);void RemoveEdge(int v1,int v2);邻接矩阵实现的部分图操作邻接矩阵实现的部分图操作template Graph :Graph(int sz)/构造函数 for(int i=0;i sz;i+)for(int j=0;j sz;j+)Edgeij=0;CurrentEdges=0;template folat Graph:GetWeight(int v1,int v2)/给出以顶点 v1 和 v2 为两端点的边上的权值 if(v1!=-1&v2!=-1)retu
13、rn Edgev1v2;else return 0;template int Graph:GetFirstNeighbor(const int v)/给出顶点位置为 v 的第一个邻接顶点的位置 if(v!=-1)for(int col=0;col 0&Edgevcol MaxValue)return col;else return-1;template int Graph:GetNextNeighbor(int v,int w)/给出顶点v的某邻接顶点w的下一个邻接顶点 int col;if(v!=-1&w!=-1)for(col=w+1;col 0&Edgevcol MaxValue)ret
14、urn col;return-1;2.邻接表邻接表(Adjacency List)n n无向图的邻接表无向图的邻接表 同一个顶点发出的边链接在同一个边链表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边中，每一个链结点代表一条边(边结点边结点),结点中有另一顶点的下标结点中有另一顶点的下标 dest 和指针和指针 link。ABCDdata adjABCD0123dest linkdest link 130210n n有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABCdata adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adj
15、ABC012dest link逆邻接表逆邻接表(入边表入边表)102 011n n网络网络(带权图带权图)的邻接表的邻接表BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)n n带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 cost。n n顶点顶点 i 的边链表的表头指针的边链表的表头指针 adj 在顶点表的在顶点表的下标为下标为 i 的顶点记录中，该记录还保存了该的顶点记录中，该记录还保存了该顶点的其它信息。顶点的其它信息。n n在邻接表的边链表中，在邻接表的边链表中，各个边结点的
16、链入各个边结点的链入顺序任意，视边结点输入次序而定。顺序任意，视边结点输入次序而定。n n设图中有设图中有 n 个顶点，个顶点，e 条边，则条边，则用邻接表表用邻接表表示无向图时示无向图时，需要，需要 n 个顶点结点，个顶点结点，2e 个边个边结点；用结点；用邻接表表示有向图时邻接表表示有向图时，若不考虑，若不考虑逆邻接表，只需逆邻接表，只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。邻接表表示的图的类定义邻接表表示的图的类定义#define DefaultSize 10template class Graph;template struct Edge /边结点friend clas
17、s Graph;int dest;/目标顶点下标 float cost;/边上的权值 Edge*link;/下一边链接指针 Edge()/构造函数 Edge(int D,Type C):dest(D),cost(C),link(NULL)int operator!=(Edge&E)const return dest!=E.dest;template struct Vertex /顶点friend class Graph;NemeType data;/顶点数据 Edge*adj;/边链表头指针template class Graph /图类private:Vertex*NodeTable;/顶点
18、表 int NumVertices;/当前顶点个数 int MaxVertices;/最大顶点个数 int NumEdges;/当前边数 int GetVertexPos(const Type vertex);public:Graph(int sz);Graph();int GraphEmpty()const return NumVertices=0;int GraphFull()const return NumVertices=MaxVertices;NameType GetValue(int i)return i=0&i NumVertices?NodeTablei.data:NULL;i
19、nt NumberOfVertices()return NumVertices;int NumberOfEdges()return NumEdges;void InsertVertex(Type vertex);void RemoveVertex(int v);void InsertEdge(int v1,int v2,float weight);void RemoveEdge(int v1,int v2);float GetWeight(int v1,int v2);int GetFirstNeighbor(int v);int GetNextNeighbor(int v,int w);邻接
20、表的构造函数和析构函数邻接表的构造函数和析构函数template Graph :Graph(int sz=DefaultSize):NumVertices(0),MaxVertices(sz),NumEdges(0)int n,e,k,j;Type name,tail,head;float weight;NodeTable=/创建顶点表 new VertexMaxVertices;cin n;/输入顶点个数 for(int i=0;i name;InsertVertex(name);cin e;/输入边条数 for(i=0;i tail head weight;k=GetVertexPos(t
21、ail);j=GetVertexPos(head);InsertEdge(k,j,weight);/插入边 template Graph :Graph()for(int i=0;i NumVertices;i+)Edge*p=NodeTablei.adj;while(p!=NULL)/逐条边释放 NodeTablei.adj=p-link;delete p;p=NodeTablei.adj;delete NodeTable;/释放顶点表邻接表部分成员函数的实现邻接表部分成员函数的实现template int Graph :GetVertexPos(const Type vertex)/根据顶点
22、名vertex查找它在邻接表中位置 for(int i=0;i NumVertices;i+)if(NodeTablei.data=vertex)return i;return-1;template int Graph :GetFirstNeighbor(int v)/查找顶点 v 第一个邻接顶点在邻接表中位置 if(v!=-1)/若顶点存在 Edge*p=NodeTablev.adj;if(p!=NULL)return p-dest;return-1;/若顶点不存在template int Graph :GetNextNeighbor(int v,int w)/查找顶点 v 在邻接顶点 w
23、后下一个邻接顶点 if(v!=-1)Edge*p=NodeTablev.adj;while(p!=NULL)if(p-dest=w&p-link!=NULL)return p-link-dest;/返回下一个邻接顶点在邻接表中位置 else p=p-link;return-1;/没有查到下一个邻接顶点template float Graph :GetWeight(int v1,int v2)/取两端点为 v1 和 v2 的边上的权值 if(v1!=-1&v2!=-1)Edge*p=NodeTablev1.adj;while(p!=NULL)if(p-dest=v2)return p-cost;
24、else p=p-link;return 0;7.3 图的遍历与连通性图的遍历与连通性n n从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一 些边访遍图中所有的顶点，且使每个顶点些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历仅被访问一次，就叫做图的遍历(Graph Traversal)。n n图中可能存在回路，且图的任一顶点都可图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过后可能会沿着某些边又回到了曾经访问过的顶点。的顶点。n n为了避免重复访问，可设置一
25、个标志顶点为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组是否被访问过的辅助数组 visited 。n n辅助数组辅助数组 visited 的初始状态为的初始状态为 0,在图在图的遍历过程中的遍历过程中,一旦某一个顶点一旦某一个顶点 i 被访问被访问,就立即让就立即让 visited i 为为 1,防止它被多次访防止它被多次访问。问。n n图的遍历的分类图的遍历的分类:uu深度优先遍历深度优先遍历 DFS(Depth First Search)uu广度优先遍历广度优先遍历 BFS(Breadth First Search)1.深度优先遍历深度优先遍历DFS(Depth First S
26、earch)n n深度优先遍历的示例深度优先遍历的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先遍历过程深度优先遍历过程 深度优先生成树深度优先生成树 图的深度优先遍历算法图的深度优先遍历算法template void Graph :DFS()int*visited=new int NumVertices;for(int i=0;i NumVertices;i+)visited i=0;/访问数组 visited 初始化 DFS(0,visited);/从顶点0出发开始遍历 delete visited;/释放 visited template v
27、oid Graph :DFS(const int v,int visited )cout GetValue(v);/访问顶点 v visitedv=1;/顶点 v 作访问标记 int w=GetFirstNeighbor(v);/取 v 的第一个邻接顶点 w while(w!=-1)/若邻接顶点 w 存在 if(!visitedw)DFS(w,visited);/若顶点 w 未访问过,递归访问顶点 w w=GetNextNeighbor(v,w);/取顶点 v 排在 w 后的下一个邻接顶点 广度优先遍历广度优先遍历BFS(Breadth First Search)n n广度优先遍历的示例广度优
28、先遍历的示例ACDEGBFIHACDEGBFH123456789123456789广度优先遍历过程广度优先遍历过程 广度优先生成树广度优先生成树I 图的广度优先遍历算法图的广度优先遍历算法template void Graph :BFS(int v)int*visited=new intNumVertices;for(int i=0;i NumVertices;i+)visitedi=0;/visited初始化 cout GetValue(v);visitedv=1;Queue q;q.EnQueue(v);/进队列 while(!q.IsEmpty()/队空遍历结束 v=q.GetFront
29、();q.DeQueue();int w=GetFirstNeighbor(v);while(w!=-1)/若邻接顶点 w 存在 if(!visitedw)/未访问过 cout GetValue(w);visitedw=1;q.EnQueue(w);w=GetNextNeighbor(v,w);delete visited;连通分量连通分量(Connected component)n n当无向图为非连通图时当无向图为非连通图时,从图中某一顶点出从图中某一顶点出发发,利用深度优先遍历算法或广度优先遍历利用深度优先遍历算法或广度优先遍历算法算法不可能遍历到图中的所有顶点不可能遍历到图中的所有顶点,
30、只能访只能访问到该顶点所在的最大连通子图问到该顶点所在的最大连通子图(连通分量连通分量)的所有顶点的所有顶点。n n若从无向图的每一个连通分量中的一个顶若从无向图的每一个连通分量中的一个顶点出发进行遍历点出发进行遍历,可求得无向图的所有连可求得无向图的所有连通分量。通分量。n n在算法中在算法中,需要对图的每一个顶点进行检需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一则从该顶点出发遍历图，可求得图的另一个连通分量。个连通分量。7.4
31、最小生成树最小生成树(minimum cost spanning tree)n n使用不同的遍历图的方法，可以得到不同使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得的生成树；从不同的顶点出发，也可能得到不同的生成树。到不同的生成树。n n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络个顶点的连通网络的生成树有的生成树有 n 个顶点、个顶点、n-1 条边。条边。n n构造最小生成树的准则构造最小生成树的准则n n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n-1 条边条边来联结网络中的来联结网络中的 n 个顶点；个顶点；n n不能使用产生回路的边；不能
32、使用产生回路的边；n n各边上的权值的总和达到最小。各边上的权值的总和达到最小。克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法n n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N=V,E,最初先构造一个只有最初先构造一个只有 n 个顶点个顶点,没有边没有边的非连通图的非连通图 T=V,图中每个顶点自图中每个顶点自成一个连通分量。当在成一个连通分量。当在 E 中选到一条具有中选到一条具有最小权值的边时最小权值的边时,若该边的两个顶点落在不若该边的两个顶点落在不同的连通分量上，则将此边加入到同的连通分量上，则将此边加入到 T 中中
33、;否否则将此边舍去，重新选择一条权值最小的则将此边舍去，重新选择一条权值最小的边。边。如此重复下去如此重复下去,直到所有顶点在同一个直到所有顶点在同一个连通分量上为止。连通分量上为止。10应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程504613228102514242216181250461325046132原图 (a)(b)1012504613228102514242216181250461325046132101412原图 (c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123普里
34、姆普里姆(Prim)算法算法n n普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络 N=V,E 中的某一顶点中的某一顶点 u0 出出发发,选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边(u0,v),将其顶点加入到将其顶点加入到生成树顶点集合生成树顶点集合U中。中。以后每一步从以后每一步从一个顶点在一个顶点在 U 中中,而而另一个另一个顶点不在顶点不在 U 中中的各条边中选择的各条边中选择权值最小的权值最小的边边(u,v),把它的顶点加入到把它的顶点加入到集合集合 U 中。如中。如此继续下去此继续下去,直到网络中的所有顶点都加入直到网络中的所有顶点都加入到生成树顶点
35、集合到生成树顶点集合 U 中为止。中为止。n n采用邻接矩阵作为图的存储表示采用邻接矩阵作为图的存储表示。252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)504613210221250461210251422161232522127.5最短路径最短路径(Shortest Path)n n最短路径问题：最短路径问题：如果从图中某一顶点如果从图中某一顶点(称为称为源点源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能的路径可能不止一条，如何找到一条路径使得沿此路不止一条，如何找到一条路径
36、使得沿此路径上各边上的权值总和达到最小。径上各边上的权值总和达到最小。n n问题解法问题解法uu 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 Dijkstra算法算法uu所有顶点之间的最短路径所有顶点之间的最短路径 Floyd算法算法边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题n n问题的提法：问题的提法：给定一个带权有向图给定一个带权有向图D与源与源点点 v，求从求从 v 到到D中其它顶点的最短路径。中其它顶点的最短路径。限定各边上的权值大于或等于限定各边上的权值大于或等于0。n n为求得这些最短路径为求得这些最短路径,Dijkstra提出按
37、路径提出按路径长度的递增次序长度的递增次序,逐步产生最短路径的算逐步产生最短路径的算法。首先求出长度最短的一条最短路径，法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点依次类推，直到从顶点v到其它各顶点的最到其它各顶点的最短路径全部求出为止。短路径全部求出为止。n n举例说明举例说明Dijkstra逐步求解的过程逐步求解的过程10432101003050206010源点源点 终点终点 最短路径最短路径 路径长度路径长度v0 v1 (v0,v1)10 v2 (v0,v1,v2)(v0,v3,v2),60,50 v3
38、(v0,v3)30 v4 (v0,v4)(v0,v3,v4)(v0,v3,v2,v4)100,90,60 n n引入辅助数组引入辅助数组dist。它的每一个分量它的每一个分量disti表表示当前找到的从示当前找到的从源点源点 v0到到终点终点 vi 的最短路径的最短路径的长度。初始状态：的长度。初始状态：n n 若从源点若从源点v0到顶点到顶点 vi 有边有边,则则disti为该边为该边上的权值；上的权值；n n 若从源若从源点点v0到顶点到顶点 vi 无边无边,则则disti为为 。n n假设假设 S 是已求得的最短路径的终点的集合，是已求得的最短路径的终点的集合，则可证明：则可证明：下一条
39、最短路径必然是从下一条最短路径必然是从v0 出发，出发，中间只经过中间只经过 S 中的顶点便可到达的那些顶点中的顶点便可到达的那些顶点vx(vx V-S)的路径中的一条。的路径中的一条。n n每次求得一条最短路径后每次求得一条最短路径后,其终点其终点vk 加入集合加入集合S，然后然后对所有的对所有的vi V-S，修改其修改其 disti值值。Dijkstra算法可描述如下：算法可描述如下：初始化：初始化：S v0;distj Edge0j,j=1,2,n-1;/n为图中顶点个数为图中顶点个数 求出最短路径的长度：求出最短路径的长度：distk min disti,i V-S;S S U k;修
40、改：修改：disti min disti,distk+Edgeki,对于每一个对于每一个 i V-S;判断：若判断：若 S=V,则算法结束，否则转则算法结束，否则转。用于计算最短路径的图邻接矩阵类用于计算最短路径的图邻接矩阵类const int NumVertices=6;/图最大顶点个数class Graph /图的类定义 private:float EdgeNumVerticesNumVertices;float distNumVertices;/最短路径长度数组 int pathNumVertices;/最短路径数组 int SNumVertices;/最短路径顶点集public:voi
41、d ShortestPath(int,int);int choose(int);计算从单个顶点到其它各顶点最短路径计算从单个顶点到其它各顶点最短路径void Graph:ShortestPath(int n,int v)/Graph是一个具有 n 个顶点的带权有向图,各/边上的权值由Edgeij给出。本算法建立起/一个数组:distj,0 jn,是当前求到的从顶/点 v 到顶点 j 的最短路径长度,同时用数组/pathj,0 jn,存放求到的最短路径。for(int i=0;i n;i+)disti=Edgevi;/dist数组初始化 Si=0;if(i!=v&disti MAXNUM)pat
42、hi=v;else pathi=-1;/path数组初始化 Sv=1;distv=0;/顶点v加入顶点集合 /选当前不在集合S中具有最短路径的顶点u for(i=0;i n-1;i+)float min=MAXNUM;int u=v;for(int j=0;j n;j+)if(!Sj&distj min)u=j;min=distj;Su=1;/将顶点u加入集合S for(int w=0;w n;w+)/修改 if(!Sw&Edgeuw MAXNUM&distu+Edgeuw distw)/顶点w未加入S,且绕过u可以缩短路径 distw=distu+Edgeuw;pathw=u;/修改到w的最
43、短路径 Dijkstra算法中各辅助数组的最终结果算法中各辅助数组的最终结果从表中读取源点从表中读取源点0到终点到终点v的最的最短路径的方法短路径的方法:举顶点举顶点4为例为例 path4=2 path2=3 path3=0，反过来排列，得反过来排列，得到路径到路径 0,3,2,4，这就是源点这就是源点0到终点到终点4的最短路径的最短路径。041231050102060301007.6活动网络活动网络(Activity Network)n n计划、施工过程、生产流程、程序流程等都计划、施工过程、生产流程、程序流程等都是是“工程工程”。除了很小的工程外，一般都把。除了很小的工程外，一般都把工程分
44、为若干个叫做工程分为若干个叫做“活动活动”的子工程。完的子工程。完成了这些活动，这个工程就可以完成了。成了这些活动，这个工程就可以完成了。n n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程这样在有的课程之间有领先关系，有的课程可以并行地学习。可以并行地学习。用顶点表示活动的网络用顶点表示活动的网络(AOV网络网络)C1 高等数学高等数学 C2 程序设计基础程序设计
45、基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2n n可以用可以用有向图有向图表示一个工程。在这种有向表示一个工程。在这种有向图中，图中，用顶点表示活动用顶点表示活动，用有向边用有向边表示表示活动活动Vi 必须先于活动必须先于活动Vj 进行进行。这种有。这种有向图叫做顶点表示活动的向图叫做顶点表示活动的AOV网络网
46、络(Activity On Vertices)。n n在在AOV网络中不能出现有向回路网络中不能出现有向回路,即有向即有向环。如果出现了有向环，则意味着某项活环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。动应以自己作为先决条件。n n因此，对给定的因此，对给定的AOV网络，必须先判断它网络，必须先判断它是否存在有向环。是否存在有向环。n n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造网络构造它的拓扑有序序列。即将各个顶点它的拓扑有序序列。即将各个顶点(代表各代表各个活动个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网络中所有应存在的前
47、驱和后继关系网络中所有应存在的前驱和后继关系都能得到满足。都能得到满足。n n这种这种构造构造AOV网络全部顶点的拓扑有序序网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。列的运算就叫做拓扑排序。n n如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶网络的所有顶点都排入一个拓扑有序的序列中点都排入一个拓扑有序的序列中,则该网络则该网络中必定不会出现有向环。中必定不会出现有向环。n n如果如果AOV网络中存在有向环，此网络中存在有向环，此AOV网络网络所代表的工程是不可行的。所代表的工程是不可行的。n n例如例如,对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序,得得到的拓扑有
48、序序列为到的拓扑有序序列为 C1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2进行拓扑排序的方法进行拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。在在AOV网络中选一个网络中选一个没有直接前驱没有直接前驱的顶点的顶点,并输出之并输出之;从图中删去该顶点从图中删去该顶点,同时删去所有它发出同时删去所有它发出的有向边的有向边;重复以上重复以上、步步,直到直到F 全部顶点均已输出全部顶点均已输出，拓扑有序序列形成，拓扑有序序列形成，拓扑排序完成；或拓扑排序完成；或F 图中还有
49、未输出的顶点图中还有未输出的顶点,但已跳出处理但已跳出处理循环循环。说明图中还剩下一些顶点。说明图中还剩下一些顶点,它们都它们都有直接前驱。这时网络中必存在有向环有直接前驱。这时网络中必存在有向环。C0C1C2C3C4C5拓扑排序的过程拓扑排序的过程(a)有向无环图有向无环图C2C5C1C0C3(b)输出顶点输出顶点C4C1C2C5C3(c)输出顶点输出顶点C0C4C0C2C5C1C3(d)输出顶点输出顶点C3C1C2C5(e)输出顶点输出顶点C2C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5 最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C4,C0,C3,C2,C1,C
50、5。它满足图中给出的所有前驱和后继关它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如系，对于本来没有这种关系的顶点，如C4和和C2，也排出了先后次序关系。也排出了先后次序关系。(h)拓扑排序完成拓扑排序完成AOV网络及其邻接表表示网络及其邻接表表示C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0012345count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0n n在在邻邻接接表表中中增增设设一一个个数数组组count，记记录录各各顶点入度。入度为零的顶点即无前驱顶点。顶点入度。入度为零的顶点即无前驱顶点