北京师范大学数据结构教学资料北京师范大学数据结构教学资料 第第8章章图图图的基本概念图的基本概念n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的及顶点间的关系集合组成的一种数据结构：关系集合组成的一种数据结构： Graph( V, E ) 其中其中 V = x | x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合； E = (x, y) | x, y V 或或 E = | x, y V & Path (x, y) 是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集合。集合。Path (x, y)表示从表示从 x 到到 y 的一条的一条单向通路单向通路, 它是有方向的。它是有方向的。2 2 void removeEdge (int v1, int v2); /在图中删去边(v1,v2) bool IsEmpty(); /若图中没有顶点, 则返回true, 否则返回false T getWeight (int v1, int v2); /函数返回边 (v1,v2) 的权值 int getFirstNeighbor (int v); /给出顶点 v 第一个邻接顶点的位置 int getNextNeighbor (int v, int w); /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点;9 9图的存储表示图的存储表示n图的模板基类图的模板基类 在模板类定义中的数据类型在模板类定义中的数据类型参数表参数表 中，中，T是顶点数据的是顶点数据的类型，类型，E是边上所附数据的类型。是边上所附数据的类型。n这个模板基类是按照最复杂的情况（即带权这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要使用非带权图，无向图）来定义的，如果需要使用非带权图，可将数据类型参数表可将数据类型参数表 改为改为 。n如果使用的是有向图，也可以对程序做相应如果使用的是有向图，也可以对程序做相应的改动。的改动。 1010图的模板基类图的模板基类 const int maxWeight = ; /无穷大的值(= )const int DefaultVertices = 30; /最大顶点数(=n)template class Graph /图的类定义protected: int maxVertices; /图中最大顶点数 int numEdges; /当前边数 int numVertices; /当前顶点数 int getVertexPos (T vertex); /给出顶点vertex在图中位置public: 1111 Graph (int sz = DefaultVertices); /构造函数 Graph();/析构函数 bool GraphEmpty () const /判图空否 return numEdges = 0; int NumberOfVertices () return numVertices; /返回当前顶点数 int NumberOfEdges () return numEdges; /返回当前边数virtual T getValue (int i);/取顶点 i 的值 virtual E getWeight (int v1, int v2); /取边上权值 virtual int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点1212virtual int getNextNeighbor (int v, int w); /取邻接顶点 w 的下一邻接顶点 virtual bool insertVertex (const T vertex); /插入一个顶点vertex virtual bool insertEdge (int v1, int v2, E cost); /插入边(v1,v2), 权为cost virtual bool removeVertex (int v); /删去顶点 v 和所有与相关联边 virtual bool removeEdge (int v1, int v2); /在图中删去边(v1,v2);1313邻接矩阵邻接矩阵 (Adjacency Matrix)(Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶在图的邻接矩阵表示中，有一个记录各个顶点信息的点信息的顶点表顶点表，还有一个表示各个顶点之，还有一个表示各个顶点之间关系的间关系的邻接矩阵邻接矩阵。n设图设图 A = (V, E) 是一个有是一个有 n 个顶点的图个顶点的图, 图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn，定义：，定义：1414n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。01230121515n在有向图中在有向图中, 统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出度出度，统计第，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的的入入度度。n在无向图中在无向图中, 统计第统计第 i 行行 (列列) 1 的个数可得顶的个数可得顶点点i 的的度度。网络的邻接矩阵网络的邻接矩阵1616863129542031用邻接矩阵表示的图的类定义用邻接矩阵表示的图的类定义template class Graphmtx : public Graph friend istream& operator ( istream& in, Graphmtx& G);/输入1717friend ostream& operator (ostream& out, Graphmtx& G);/输出private: T *VerticesList; /顶点表 E *Edge;/邻接矩阵int getVertexPos (T vertex) /给出顶点vertex在图中的位置 for (int i = 0; i = 0 & i = numVertices ? VerticesListi : NULL; E getWeight (int v1, int v2) /取边(v1,v2)上权值 return v1 != -1 & v2 != -1 ? Edgev1v2 : 0; int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点1919 int getNextNeighbor (int v, int w); /取 v 的邻接顶点 w 的下一邻接顶点 bool insertVertex (const T vertex); /插入顶点vertex bool insertEdge (int v1, int v2, E cost); /插入边(v1, v2),权值为cost bool removeVertex (int v); /删去顶点 v 和所有与它相关联的边 bool removeEdge (int v1, int v2); /在图中删去边(v1,v2);2020template Graphmtx:Graphmtx (int sz) /构造函数 maxVertices = sz; numVertices = 0; numEdges = 0;int i, j;VerticesList = new TmaxVertices; /创建顶点表 Edge = (int *) new int *maxVertices;for (i = 0; i maxVertices; i+) Edgei = new intmaxVertices; /邻接矩阵 for (i = 0; i maxVertices; i+) /矩阵初始化 for (j = 0; j maxVertices; j+) Edgeij = (i = j) ？ 0 : maxWeight; 2121template int Graphmtx:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) for (int col = 0; col numVertices; col+) if (Edgevcol & Edgevcol maxWeight) return col; return -1;2222template int Graphmtx:getNextNeighbor (int v, int w) /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 & w != -1) for (int col = w+1; col numVertices; col+) if (Edgevcol & Edgevcol maxWeight) return col; return -1;2323n邻接表是邻接矩阵的改进形式。为此需要把邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。邻接矩阵的各行分别组织为一个单链表。n在邻接表中，同一个顶点发出的边链接在同在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标（边结点），结点中有另一顶点的下标 dest 和指针和指针 link。对于带权图，边结点中还要保。对于带权图，边结点中还要保存该边的权值存该边的权值cost。n顶点表的第顶点表的第 i 个顶点中保存该顶点的数据，以个顶点中保存该顶点的数据，以及它对应边链表的头指针及它对应边链表的头指针adj。 邻接表邻接表 (Adjacency List)(Adjacency List)2424ABCDdata adjABCD0123dest linkdest link 130210无向图的邻接表无向图的邻接表n统计某顶点对应边链表中结点个数，可得该顶统计某顶点对应边链表中结点个数，可得该顶点的度。点的度。n某条边某条边(vi, vj)在邻接表中有两个边结点，分别在邻接表中有两个边结点，分别在第在第 i 个顶点和第个顶点和第 j 个顶点对应的边链表中。个顶点对应的边链表中。2525data adjABC012dest linkdest link 邻接表邻接表 (出边表出边表)data adjABC012dest link逆邻接表逆邻接表 (入边表入边表)102 011有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABC2626BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络 ( (带权图带权图) ) 的邻接表的邻接表n统计出边表中结点个数，得到该顶点的出度；统计出边表中结点个数，得到该顶点的出度；n统计入边表中结点个数，得到该顶点的入度。统计入边表中结点个数，得到该顶点的入度。2727n在邻接表的边链表中，各个边结点的链入顺序在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。n设图中有设图中有 n 个顶点，个顶点，e 条边，则用邻接表表示条边，则用邻接表表示无向图时，需要无向图时，需要 n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用邻接表表示有向图时，若不考虑逆邻接表，用邻接表表示有向图时，若不考虑逆邻接表，只需只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。n当当 e 远远小于远远小于 n2 时，可以节省大量的存储空时，可以节省大量的存储空间。此外，把同一个顶点的所有边链接在一个间。此外，把同一个顶点的所有边链接在一个单链表中，也使得图的操作更为便捷。单链表中，也使得图的操作更为便捷。 2828用邻接表表示的图的类定义用邻接表表示的图的类定义 template struct Edge /边结点的定义 int dest; /边的另一顶点位置 E cost; /边上的权值 Edge *link; /下一条边链指针 Edge () /构造函数 Edge (int num, E cost) /构造函数 : dest (num), weight (cost), link (NULL) bool operator != (Edge& R) const return dest != R.dest; /判边等否;2929template struct Vertex /顶点的定义 T data; /顶点的名字Edge *adj; /边链表的头指针;template class Graphlnk : public Graph /图的类定义friend istream& operator (istream& in, Graphlnk& G); /输入friend ostream& operator (ostream& out, Graphlnk& G); /输出3030private: Vertex *NodeTable; /顶点表 (各边链表的头结点) int getVertexPos (const T vertx) /给出顶点vertex在图中的位置 for (int i = 0; i = 0 & i NumVertices) ? NodeTablei.data : 0; E getWeight (int v1, int v2); /取边(v1,v2)权值bool insertVertex (const T& vertex); bool removeVertex (int v); bool insertEdge (int v1, int v2, E cost);bool removeEdge (int v1, int v2); int getFirstNeighbor (int v); int getNextNeighbor (int v, int w);3232template Graphlnk:Graphlnk (int sz) /构造函数：建立一个空的邻接表 maxVertices = sz; numVertices = 0; numEdges = 0; NodeTable = new VertexmaxVertices;/创建顶点表数组 if (NodeTable = NULL) cerr 存储分配错！存储分配错！ endl; exit(1); for (int i = 0; i maxVertices; i+) NodeTablei.adj = NULL;3333template Graphlnk:Graphlnk() /析构函数：删除一个邻接表 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; /删除顶点表数组3434template int Graphlnk:getFirstNeighbor (int v) /给出顶点位置为 v 的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) /顶点顶点v存在存在 Edge *p = NodeTablev.adj;/对应边链表第一个边结点if (p != NULL) return p-dest;/存在, 返回第一个邻接顶点 return -1;/第一个邻接顶点不存在3535template int Graphlnk:getNextNeighbor (int v, int w) /给出顶点v的邻接顶点w的下一个邻接顶点的位置,/若没有下一个邻接顶点, 则函数返回-1 if (v != -1) /顶点v存在 Edge *p = NodeTablev.adj; while (p != NULL & p-dest != w) p = p-link; if (p != NULL & p-link != NULL) return p-link-dest; /返回下一个邻接顶点 return - -1; /下一邻接顶点不存在3636邻接多重表邻接多重表 (Adjacency (Adjacency Multilist)Multilist)n在邻接多重表中在邻接多重表中,每一条边只有一个边结点。为每一条边只有一个边结点。为有关边的处理提供了方便。有关边的处理提供了方便。n无向图的情形无向图的情形u边结点的结构边结点的结构n其中其中, mark 是记录是否处理过的标记是记录是否处理过的标记; vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域是链接指域是链接指针针, 指向下一条依附顶点指向下一条依附顶点vertex1的边；的边；path2 是是指向下一条依附顶点指向下一条依附顶点vertex2的边链接指针。的边链接指针。 mark vertex1 vertex2 path1 path23737n需要时还可设置一个存放与该边相关的权值的需要时还可设置一个存放与该边相关的权值的域域 cost。u顶点结点的结构顶点结点的结构n顶点信息的结点表以顺序表方式组织顶点信息的结点表以顺序表方式组织, 每一个顶每一个顶点结点有两个数据成员：其中，点结点有两个数据成员：其中，data 存放与该存放与该顶点相关的信息，顶点相关的信息，Firstout 是指示第一条依附该是指示第一条依附该顶点的边的指针。顶点的边的指针。n在邻接多重表中在邻接多重表中, 所有依附同一个顶点的边都所有依附同一个顶点的边都链接在同一个单链表中。链接在同一个单链表中。 data Firstout3838markvtx1vtx2path1path2 0 10 21 3e1e2e3data FoutABCD0123e1e2e3ABCDn从顶点从顶点 i 出发出发, 可以循链找到所有依附于该顶可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。邻接多重表的结构邻接多重表的结构3939n有向图的情形有向图的情形n在用邻接表表示有向图时在用邻接表表示有向图时, 有时需要同时使用有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表邻接表和逆邻接表。用有向图的邻接多重表(十字链表十字链表)可把两个表结合起来表示。可把两个表结合起来表示。u边结点的结构边结点的结构n其中，其中，mark是处理标记；是处理标记；vertex1和和vertex2指指明该有向边始顶点和终顶点的位置。明该有向边始顶点和终顶点的位置。path1是是指向指向始顶点与该边相同始顶点与该边相同的下一条边的指针；的下一条边的指针；path2是指向是指向终顶点与该边相同终顶点与该边相同的下一条边的的下一条边的指针。需要时还可有权值域指针。需要时还可有权值域cost。 mark vertex1 vertex2 path1 path24040u顶点结点的结构顶点结点的结构n每个顶点有一个结点，它相当于出边表和入边每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员表的表头结点：其中，数据成员data存放与该存放与该顶点相关的信息，指针顶点相关的信息，指针Firstout 指示以该顶点指示以该顶点为始顶点的出边表的第一条边，为始顶点的出边表的第一条边，Firstin 指示以指示以该顶点为终顶点的入边表的第一条边。该顶点为终顶点的入边表的第一条边。 data Firstin Firstout4141markvtx1vtx2path1path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE邻接多重表的结构邻接多重表的结构4242画画出出在在下下图图所所表表示示的的有有向向图图中中删删除除顶点顶点V3V3后的十字链表存储结构图后的十字链表存储结构图。4343图的遍历与连通性图的遍历与连通性n从已给的连通图中某一顶点出发，沿着一些边从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历一次，就叫做图的遍历 (Graph Traversal)。n图中可能存在回路，且图的任一顶点都可能与图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。沿着某些边又回到了曾经访问过的顶点。n为了避免重复访问，可设置一个标志顶点是否为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组被访问过的辅助数组 visited 。4444n辅助数组辅助数组visited 的初始状态为的初始状态为 0, 在图的遍在图的遍历过程中历过程中, 一旦某一个顶点一旦某一个顶点 i 被访问被访问, 就立即就立即让让visitedi为为 1, 防止它被多次访问。防止它被多次访问。n图的遍历的分类图的遍历的分类:u深度优先搜索深度优先搜索 DFS (Depth First Search)u广度优先搜索广度优先搜索 BFS (Breadth First Search)4545深深 度度 优优 先先 搜搜 索索 DFSDFS (Depth (Depth First First Search)Search)n深度优先搜索的示例深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树4646nDFS 在访问图中某一在访问图中某一起始顶点起始顶点 v 后后, 由由 v 出发出发, 访问它的任一访问它的任一邻接顶点邻接顶点 w1; 再从再从 w1 出发出发, 访问访问与与 w1邻邻 接接但还但还没有访问过的顶点没有访问过的顶点 w2; 然后再然后再从从 w2 出发出发, 进行类似的访问进行类似的访问, 如此进行下去如此进行下去, 直至到达所有的邻接顶点都被访问过的顶点直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。接着接着, 退回一步退回一步, 退到前一次刚访问过退到前一次刚访问过的顶点的顶点, 看是否还有其它没有被访问的邻接顶看是否还有其它没有被访问的邻接顶点。点。如果有如果有, 则访问此顶点则访问此顶点, 之后再从此顶点出之后再从此顶点出发发, 进行与前述类似的访问进行与前述类似的访问; 如果没有如果没有, 就再退就再退回一步进行搜索。重复上述过程回一步进行搜索。重复上述过程, 直到连通图直到连通图中所有顶点都被访问过为止。中所有顶点都被访问过为止。4747图的深度优先搜索算法图的深度优先搜索算法template void DFS (Graph& G, const T& v) /从顶点v出发对图G进行深度优先遍历的主过程 int i, loc, n = G.NumberOfVertices(); /顶点个数 bool *visited = new booln; /创建辅助数组 for (i = 0; i n; i+) visited i = false; /辅助数组visited初始化loc = G.getVertexPos(v); DFS (G, loc, visited); /从顶点0开始深度优先搜索 delete visited; /释放visited4848templatevoid DFS (Graph& G, int v, bool visited) cout G.getValue(v) ; /访问顶点v visitedv = true; /作访问标记 int w = G.getFirstNeighbor (v); /第一个邻接顶点 while (w != -1) /若邻接顶点w存在 if ( !visitedw ) DFS(G, w, visited); /若w未访问过, 递归访问顶点w w = G.getNextNeighbor (v, w); /下一个邻接顶点 4949广广度度优优先先搜搜索索BFSBFS (Breadth (Breadth First First Search)Search)n广度优先搜索的示例广度优先搜索的示例广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树ACDEGBFIHACDEGBFH123456789123456789I5050nBFS在访问了起始顶点在访问了起始顶点 v 之后之后, 由由 v 出发出发, 依次依次访问访问 v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1, w2, , wt, 然后再顺序访问然后再顺序访问 w1, w2, , wt 的所有还的所有还未被访问过的邻接顶点。再从这些访问过的未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过顶点出发，再访问它们的所有还未被访问过的邻接顶点，的邻接顶点， 如此做下去，直到图中所有如此做下去，直到图中所有顶点都被访问到为止。顶点都被访问到为止。n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程, 每向前每向前走一步可能访问一批顶点走一步可能访问一批顶点, 不像深度优先搜索不像深度优先搜索那样有往回退的情况。因此那样有往回退的情况。因此, 广度优先搜索不广度优先搜索不是一个递归的过程。是一个递归的过程。5151n为了实现逐层访问为了实现逐层访问, 算法中使用了一个队列算法中使用了一个队列, 以以记忆正在访问的这一层和上一层的顶点记忆正在访问的这一层和上一层的顶点, 以便以便于向下一层访问。于向下一层访问。n为避免重复访问为避免重复访问, 需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。，给被访问过的顶点加标记。template void BFS (Graph& G, const T& v) int i, w, n = G.NumberOfVertices(); /图中顶点个数图的广度优先搜索算法图的广度优先搜索算法5252 bool *visited = new booln; for (i = 0; i n; i+) visitedi = false; int loc = G.getVertexPos (v);/取顶点号 cout G.getValue (loc) ; /访问顶点v visitedloc = true; /做已访问标记 Queue Q; Q.EnQueue (loc); /顶点进队列, 实现分层访问 while (!Q.IsEmpty() ) /循环, 访问所有结点 Q.DeQueue (loc); w = G.getFirstNeighbor (loc); /第一个邻接顶点 while (w != -1) /若邻接顶点w存在 if (!visitedw) /若未访问过5353 cout G.getValue (w) ;/访问 visitedw = true; Q.EnQueue (w); /顶点w进队列 w = G.getNextNeighbor (loc, w); /找顶点loc的下一个邻接顶点 /外层循环，判队列空否 delete visited;5454连通分量连通分量 (Connected component)(Connected component)n当无向图为非连通图时，从图中某一顶点出当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访算法不可能遍历到图中的所有顶点，只能访问到该顶点所在最大连通子图问到该顶点所在最大连通子图（连通分量）（连通分量）的的所有顶点。所有顶点。n若从无向图每一连通分量中的一个顶点出发若从无向图每一连通分量中的一个顶点出发进行遍历进行遍历,可求得无向图的所有连通分量。可求得无向图的所有连通分量。n例如，对于非连通的无向图，所有连通分量例如，对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。的生成树组成了非连通图的生成森林。5555ACDEBFGOIHJNMLK非连通无向图AHKCDEIBFOGJNML非连通图的连通分量5656重连通分量重连通分量 (Biconnected Component)(Biconnected Component)n在无向连通图在无向连通图G中中, 当且仅当删去当且仅当删去G中的顶点中的顶点v及所有依附于及所有依附于v的所有边后的所有边后, 可将图分割成两个可将图分割成两个或两个以上的连通分量，则称顶点或两个以上的连通分量，则称顶点v为为关节点关节点。n没有没有关节点关节点的连通图叫做重连通图。的连通图叫做重连通图。n在重连通图上在重连通图上, 任何一对顶点之间至少存在有任何一对顶点之间至少存在有两条路径两条路径, 在删去某个顶点及与该顶点相关联在删去某个顶点及与该顶点相关联的边时的边时, 也不破坏图的连通性。也不破坏图的连通性。6363n一个连通图一个连通图G如果不是重连通图，那么它可以如果不是重连通图，那么它可以包括几个重连通分量。包括几个重连通分量。n在一个无向连通图在一个无向连通图G中中, 重连通分量可以利用重连通分量可以利用深度优先生成树找到。深度优先生成树找到。n在图中各在图中各顶点旁标明的深度优先数顶点旁标明的深度优先数, 给出进行给出进行深度优先搜索时各顶点访问的次序。深度优先搜索时各顶点访问的次序。n深度优先生成树的深度优先生成树的根是根是关节点关节点的充要条件是它的充要条件是它至少有两个子女至少有两个子女。n其它顶点其它顶点 u 是是关节点关节点的充要条件是它至少有一的充要条件是它至少有一个子女个子女 w, 从从 w 出发出发, 不能通过不能通过 w、w 的子孙及的子孙及一条回边所组成的路径到达一条回边所组成的路径到达 u 的祖先的祖先。6464ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有两根有两 个子女个子女关关关关节节节节点点点点关关关关节节节节点点点点关节点关节点关节点关节点6565最小生成树最小生成树 ( minimum cost spanning tree ( minimum cost spanning tree ) )n使用不同的遍历图的方法，可以得到不同的生使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的成树；从不同的顶点出发，也可能得到不同的生成树。生成树。n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1条边。条边。n构造最小生成树构造最小生成树 假设有一个网络，用以表示假设有一个网络，用以表示 n 个城市之间架设通信线路，边上的权值代表个城市之间架设通信线路，边上的权值代表架设通信线路的成本。如何架设才能使线路架架设通信线路的成本。如何架设才能使线路架设的成本达到最小？设的成本达到最小？6666n构造最小生成树的准则构造最小生成树的准则v必须使用且仅使用该网络中的必须使用且仅使用该网络中的 n-1 条边来条边来联结网络中的联结网络中的 n 个顶点；个顶点；v不能使用产生回路的边；不能使用产生回路的边；v各边上的权值的总和达到最小。各边上的权值的总和达到最小。北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉347641583124192538222219313944506767北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉76241922221931北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉347641583124192538222219313944506868克鲁斯卡尔克鲁斯卡尔 (Kruskal) (Kruskal) 算法算法n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N = V, E , 最初先构造一个只有最初先构造一个只有 n 个顶点个顶点, 没有边的非连没有边的非连通图通图 T = V, , 图中每个顶点自成一个连通图中每个顶点自成一个连通分量。当在分量。当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时, 若该边的两个顶点落在不同的连通分量上，则若该边的两个顶点落在不同的连通分量上，则将此边加入到将此边加入到 T 中中; 否则将此边舍去，重新选否则将此边舍去，重新选择一条权值最小的边。如此重复下去择一条权值最小的边。如此重复下去, 直到所直到所有顶点在同一个连通分量上为止。有顶点在同一个连通分量上为止。6969KruskalKruskal算法的伪代码描述算法的伪代码描述 T = ;/T是最小生成树的边集合是最小生成树的边集合 /E是带权无向图的边集合是带权无向图的边集合while ( T 包含的边少于包含的边少于n-1 & E不空不空) 从从 E 中选一条具有最小代价的边中选一条具有最小代价的边 (v, w); 从从 E 中删去中删去(v, w); 如果如果(v, w)加到加到 T 中后不会产生回路中后不会产生回路, 则将则将 (v, w)加入加入T; 否则放弃否则放弃(v, w);if ( T 中包含的边少于中包含的边少于n-1条条) cout 不是最小生成树不是最小生成树 endl;7070n算法的框架算法的框架 利用利用最小堆最小堆(MinHeap)和和并查集并查集(DisjointSets)来实现来实现克鲁斯卡尔算法克鲁斯卡尔算法。n首先首先, 利用利用最小堆最小堆来存放来存放E中的所有的边中的所有的边, 堆中堆中每个结点的格式为每个结点的格式为n在构造最小生成树过程中在构造最小生成树过程中, 利用利用并查集并查集的运算的运算检查依附一条边的两顶点检查依附一条边的两顶点tail、head 是否在同是否在同一连通分量一连通分量 (即即并查集的同一个子集合并查集的同一个子集合) 上上, 是是则舍去这条边；否则将此边加入则舍去这条边；否则将此边加入T, 同时将这同时将这两个顶点放在同一个连通分量上。两个顶点放在同一个连通分量上。边的两个顶点位置 边的权值 tail head cost 7171n随着各边逐步加入到最小生成树的边集合中随着各边逐步加入到最小生成树的边集合中,各连通分量也在逐步合并各连通分量也在逐步合并,直到形成一个连通直到形成一个连通分量为止。分量为止。10504613228102514242216181250461325046132原图 (a) (b)构造最小生成树的过程构造最小生成树的过程72721012504613228102514242216181250461325046132101412原图 (c) (d)504613210141612(e) (f) (g)5046132101422161250461210251422161237373最小生成树类定义最小生成树类定义const float maxValue = FLOAT_MAX /机器可表示的、问题中不可能出现的大数template struct MSTEdgeNode /树边结点的类定义 int tail, head;/两顶点位置 E cost;/边上的权值MSTEdgeNode() : tail(-1), head(-1), cost(0) /构造函数; template 7474class MinSpanTree /树的类定义protected: MSTEdgeNode *edgevalue; /边值数组 int maxSize, n;/最大元素个数和当前个数public: MinSpanTree (int sz = DefaultSize-1) : MaxSize (sz), n (0) edgevalue = new MSTEdgeNodesz; int Insert (MSTEdgeNode& item); ;7575n在求解最小生成树时，可以用邻接矩阵存储图，在求解最小生成树时，可以用邻接矩阵存储图，也可以用邻接表存储图。算法中使用图的抽象也可以用邻接表存储图。算法中使用图的抽象基类的操作，无需考虑图及其操作的具体实现。基类的操作，无需考虑图及其操作的具体实现。#include heap.h#include UFSets.htemplate void Kruskal (Graph& G, MinSpanTree& MST) KruskalKruskal算法的实现算法的实现 7676 MSTEdgeNode ed; /边结点辅助单元 int u, v, count; int n = G.NumberOfVertices(); /顶点数 int m = G.NumberOfEdges(); /边数 MinHeap MSTEdgeNode H(m); /最小堆 UFSets F(n); /并查集 for (u = 0; u n; u+) for (v = u+1; v n; v+) if (G.getWeight(u,v) != maxValue) ed.tail = u; ed.head = v;/插入堆 ed.cost = G.getWeight (u, v); H.Insert(ed); 7777 count = 1; /最小生成树边数计数 while (count n) /反复执行, 取n-1条边 H.Remove(ed); /退出具最小权值的边 u = F.Find(ed.tail); v = F.Find(ed.head); /取两顶点所在集合的根u与v if (u != v) /不是同一集合,不连通 F.Union(u, v); /合并,连通它们 MST.Insert(ed); /该边存入MST count+; 7878出堆顺序出堆顺序 (0,5,10) 选中选中 (2,3,12) 选中选中 (1,6,14) 选中选中 (1,2,16) 选中选中 (3,6,18) 舍弃舍弃 (3,4,22) 选中选中 (4,6,24) 舍弃舍弃 (4,5,25) 选中选中并查集原图-2-2-2-2-1 -1 -1 -1 -1 -1 -1-1 -1 -1 -1-102-1-1-10-2200000 1 2 3 4 5 6-21-11-2-1-421-2 -51211-711211F5046132281025142422161812(0,5,10)(2,3,12)(1,6,14)(1,2,16)(3,4,22)(4,5,25)7979普里姆普里姆(Prim)(Prim)算法算法n普里姆算法的基本思想：普里姆算法的基本思想： 从连通网络从连通网络 N = V, E中的某一顶点中的某一顶点 u0 出发出发, 选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边 (u0, v), 将将其顶点加入到其顶点加入到生成树顶点集合生成树顶点集合U中。中。以后每一步从一个顶点在集合以后每一步从一个顶点在集合U中中, 而另一个而另一个顶点不在集合顶点不在集合U中的各条边中选择权值最小的中的各条边中选择权值最小的边边(u, v), 把它的顶点加入到把它的顶点加入到集合集合U中。如此继中。如此继续下去续下去, 直到网络中的所有顶点都加入到生成直到网络中的所有顶点都加入到生成树顶点集合树顶点集合U中为止。中为止。8080普里姆普里姆(Prim)(Prim)的伪代码描述的伪代码描述选定构造最小生成树的出发顶点选定构造最小生成树的出发顶点u0; Vmst = u0，Emst = ; while (Vmst包含的顶点少于包含的顶点少于n & E不空不空) 从从E中选一条边中选一条边(u, v), u Vmstv V-Vmst, 且具有最小代价且具有最小代价(cost); 令令Vmst = Vmstv, Emst = Emst(u, v); 将新选出的边从将新选出的边从E中剔除：中剔除：E = E-(u, v); if (Vmst包含的顶点少于包含的顶点少于n) cout 不是最小生成树不是最小生成树 endl;8181252510504613228102514242216185046132504613210原图 (a) (b)504613210(c) (d) (e) (f)504613210221250461210251422161232522128282PrimPrim算法的实现算法的实现#include heap.htemplate void Prim (Graph& G, const T u0, MinSpanTree& MST) MSTEdgeNode ed; /边结点辅助单元 int i, u, v, count; int n = G.NumberOfVertices(); /顶点数 int m = G.NumberOfEdges(); /边数int u = G.getVertexPos(u0); /起始顶点号MinHeap MSTEdgeNode H(m); /最小堆8383 bool Vmst = new booln; /最小生成树顶点集合 for (i = 0; i n; i+) Vmsti = false; Vmstu = true; /u 加入生成树 count = 1; do /迭代 v = G.getFirstNeighbor(u); while (v != -1) /检测u所有邻接顶点 if (!Vmstv) /v不在mst中 ed.tail = u; ed.head = v; ed.cost = G.getWeight(u, v); H.Insert(ed); /(u,v)加入堆 /堆中存所有u在mst中, v不在mst中的边 v = G.getNextNeighbor(u, v); 8484 while (!H.IsEmpty() & count n) H.Remove(ed); /选堆中具最小权的边 if (!Vmsted.head) MST.Insert(ed); /加入最小生成树 u = ed.head; Vmstu = true; /u加入生成树顶点集合 count+; break; while (count n);8585n例子例子50461322810251424221618125046132281025142422161812H = (0,5,10), (0,1,28)ed = (0, 5, 10)Vmst = t, f, f, f, f, f, fVmst = t, f, f, f, f, t, f86865046132281025142422161812H = (5,4,25), (0,1,28)ed = (5, 4, 25)Vmst = t, f, f, f, f, t, fVmst = t, f, f, f, t, t, f5046132281025142422161812H = (4,3,22), (4,6,24), (0,1,28)ed = (4, 3, 22)Vmst = t, f, f, f, t, t, fVmst = t, f, f, t, t, t, f87875046132281025142422161812H = (3,2,12), (3,6,18), (4,6,24), (0,1,28)ed = (3, 2, 12)Vmst = t, f, f, t, t, t, fVmst = t, f, t, t, t, t, f5046132281025142422161812H = (2,1,16), (3,6,18), (4,6,24), (0,1,28)ed = (2, 1, 16)Vmst = t, f, t, t, t, t, fVmst = t, t, t, t, t, t, f88885046132281025142422161812H = (1,6,14), (3,6,18), (4,6,24), (0,1,28)ed = (1, 6, 14)Vmst = t, t, t, t, t, t, fVmst = t, t, t, t, t, t, tn最小生成树中边集合里存入的各条边为：最小生成树中边集合里存入的各条边为：(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)8989n注意：当各边有相同权值时，由于选择的随意注意：当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。性，产生的生成树可能不唯一。 9090最短路径最短路径 (Shortest Path)(Shortest Path)n最短路径问题：最短路径问题：如果从图中某一顶点（称为源如果从图中某一顶点（称为源点）另一顶点（称为终点）的路径可能不止一点）另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小的权值总和达到最小。n问题解法问题解法uu边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 Dijkstra算法算法 (仅讲此算法仅讲此算法)u 边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题 Bellman和和Ford算法算法 (不讲不讲)u所有顶点之间的最短路径所有顶点之间的最短路径 Floyd算法算法 (不讲不讲)9191边上权值非负情形的边上权值非负情形的单源最短路径问题单源最短路径问题n问题的提法：问题的提法：给定一个带权有向图给定一个带权有向图D与源点与源点 v，求从，求从v到到D中其他顶点的最短路径。中其他顶点的最短路径。限定各边上的权值大于或等于限定各边上的权值大于或等于0。n为求得这些最短路径为求得这些最短路径, Dijkstra提出提出按路径长度按路径长度的递增次序的递增次序, 逐步产生最短路径的算法逐步产生最短路径的算法。首先。首先求出长度最短的一条最短路径，再参照它求出求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从长度次短的一条最短路径，依次类推，直到从顶点顶点v到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。9292Dijkstra逐步求解的过程逐步求解的过程源点源点 终点终点 最短路径最短路径 路径长度路径长度v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2) ,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 104321010030502060109393n引入辅助数组引入辅助数组dist。它的每一个分量。它的每一个分量disti表示表示当前找到的从源点当前找到的从源点 v0 到终点到终点 vi 的最短路径的长的最短路径的长度。初始状态：度。初始状态：u若从若从v0到顶点到顶点vi有边有边, 则则disti为该边的权值；为该边的权值；u若从若从v0到顶点到顶点vi无边无边, 则则disti为为 。n假设假设S是是已求得的最短路径的终点已求得的最短路径的终点的集合，则可的集合，则可证明：下一条最短路径必然是证明：下一条最短路径必然是从从v0 出发，中间出发，中间只经过只经过S中的顶点便可到达的那些顶点中的顶点便可到达的那些顶点vx (vx V-S )的路径中的一条。的路径中的一条。n每次求得一条最短路径后每次求得一条最短路径后, 其终点其终点vk 加入集合加入集合S，然后对所有的，然后对所有的vi V-S，修改其，修改其 disti值。值。9494DijkstraDijkstra算法可描述如下：算法可描述如下： 初始化：初始化： Sv0; distjEdge0j, j = 1, 2, , n-1; / n为图中顶点个数为图中顶点个数 求出最短路径的长度：求出最短路径的长度： distkmin disti, i V-S ; SSk; 修改：修改： distimindisti, distk+Edgeki, 对于每一个对于每一个 i V-S ; 判断：若判断：若 S = V, 则算法结束，否则转则算法结束，否则转。9595计算从单个顶点到其他各顶点计算从单个顶点到其他各顶点最短路径的算法最短路径的算法void ShortestPath (Graph& G, T v, E dist, int path) /Graph是一个带权有向图。distj, 0jn, 是当前/求到的从顶点v到顶点j的最短路径长度, pathj,/0jn, 存放求到的最短路径。 int n = G.NumberOfVertices(); bool *S = new booln; /最短路径顶点集 int i, j, k; E w, min; for (i = 0; i n; i+) disti = G.getWeight(v, i); 9696 Si = false; if (i != v & disti maxValue) pathi = v; else pathi = -1; Sv = true; distv = 0; /顶点v加入顶点集合 for (i = 0; i n-1; i+) /求解各顶点最短路径 min = maxValue; int u = v; /选不在S中具有最短路径的顶点u for (j = 0; j n; j+) if (!Sj & distj min) u = j; min = distj; Su = true; /将顶点u加入集合S9797 for (k = 0; k n; k+) /修改 w = G.GetWeight(u, k); if (!Sk & w maxValue & distu+w distk) /顶点k未加入S distk = distu+w; pathk = u; /修改到k的最短路径 9898Dijkstra算法中各辅助数组的最终结果算法中各辅助数组的最终结果从表中读取源点从表中读取源点0到终点到终点v的最的最短路径的方法短路径的方法 : 举顶点举顶点4为例为例 path4 = 2 path2 = 3 path3 = 0，反过来排列，得，反过来排列，得到路径到路径 0, 3, 2, 4，这就是源点，这就是源点0到终点到终点4的最短路径。的最短路径。04123105010206030100序号序号 顶点顶点1 顶点顶点2 顶点顶点3 顶点顶点4 Dist 10 50 30 60 path 0 3 0 2 9999活动网络活动网络 (Activity Network)(Activity Network)n计划、施工过程、生产流程、程序流程等都是计划、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程。除了很小的工程外，一般都把工程分为若干个叫做分为若干个叫做“活动活动”的子工程。完成了这的子工程。完成了这些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可这样在有的课程之间有领先关系，有的课程可以并行地学习。以并行地学习。用顶点表示活动的网络用顶点表示活动的网络 (AOV(AOV网络网络) )114114 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1, C2 C4 数据结构数据结构 C3, C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5, C4 C7 操作系统操作系统 C4, C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 115115学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2116116n可以用可以用有向图有向图表示一个工程。在这种有向图表示一个工程。在这种有向图中，中，用顶点表示活动用顶点表示活动，用有向边用有向边表示表示活动活动Vi 必须先于活动必须先于活动Vj 进行进行。这种有向图叫。这种有向图叫做顶点表示活动的做顶点表示活动的AOV网络网络 (Activity On Vertices)。 n在在AOV网络中不能出现有向回路网络中不能出现有向回路, 即有向环。即有向环。如果出现了有向环，则意味着某项活动应以如果出现了有向环，则意味着某项活动应以自己作为先决条件。自己作为先决条件。n因此，对给定的因此，对给定的AOV网络，必须先判断它是网络，必须先判断它是否存在有向环。否存在有向环。117117n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它网络构造它的的拓扑有序序列拓扑有序序列。即将各个顶点。即将各个顶点 (代表各个活代表各个活动动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网网络中所有应存在的前驱和后继关系都能得到满络中所有应存在的前驱和后继关系都能得到满足。足。1234拓扑排序拓扑排序41234123偏序关系全序关系118118n这种这种构造构造AOV网络全部顶点的拓扑有序序列网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。的运算就叫做拓扑排序。n如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶点网络的所有顶点都排入一个拓扑有序的序列中都排入一个拓扑有序的序列中, 则该网络中必则该网络中必定不会出现有向环。定不会出现有向环。n如果如果AOV网络中存在有向环，此网络中存在有向环，此AOV网络所网络所代表的工程是不可行的。代表的工程是不可行的。n例如例如, 对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序, 得到得到的拓扑有序序列为的拓扑有序序列为119119 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2120120进行拓扑排序的方法进行拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。 在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点, 并输出之并输出之; 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出的有同时删去所有它发出的有向边向边; 重复以上重复以上 、步步, 直到直到u全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或拓扑排序完成；或u图中还有未输出的顶点图中还有未输出的顶点, 但已跳出处理循但已跳出处理循环。说明图中还剩下一些顶点环。说明图中还剩下一些顶点, 它们都有它们都有直接前驱。这时网络中必存在有向环。直接前驱。这时网络中必存在有向环。121121C0C1C2C3C4C5拓扑排序的过程拓扑排序的过程(a) 有向无环图有向无环图C2C5C1C0C3(b) 输出顶点输出顶点C4C1C2C5C3(c) 输出顶点输出顶点C0C4C0C2C5C1C3(d) 输出顶点输出顶点C3122122C1C2C5(e) 输出顶点输出顶点C2C5C1(f) 输出顶点输出顶点C1C5(g) 输出顶点输出顶点C5n最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如系，对于本来没有这种关系的顶点，如C4和和C2，也排出了先后次序关系。，也排出了先后次序关系。(h) 拓扑排序完成拓扑排序完成123123AOV网络及其网络及其邻接表表示邻接表表示C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0012345count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0124124n在在邻邻接接表表中中增增设设一一个个数数组组count，记记录录各各顶顶点入度。入度为零的顶点即无前驱顶点。点入度。入度为零的顶点即无前驱顶点。n在在输输入入数数据据前前, 顶顶点点表表NodeTable和和入入度度数数组组count全全部部初初始始化化。在在输输入入数数据据时时, 每每输输入入一一条条边边, 就就需需要要建建立立一一个个边边结结点点, 并并将将它它链链入入相相应边链表中应边链表中, 统计入度信息：统计入度信息： Edge * p = new Edge (k);/建立边结点建立边结点, dest 域赋为域赋为 k p-link = NodeTablej.adj; NodeTablej.adj = p; /链入顶点链入顶点j的边链表的前端的边链表的前端 countk+; /顶点顶点k入度加一入度加一 125125n在算法中在算法中,使用一个存放入度为零的顶点的链使用一个存放入度为零的顶点的链式栈式栈,供选择和输出无前驱的顶点。供选择和输出无前驱的顶点。n拓扑排序算法可描述如下：拓扑排序算法可描述如下：u建立入度为零的顶点栈建立入度为零的顶点栈;u当入度为零的顶点栈不空时当入度为零的顶点栈不空时,重复执行重复执行从顶点栈中退出一个顶点从顶点栈中退出一个顶点, 并输出之并输出之;从从AOV网络中删去这个顶点和它发出的网络中删去这个顶点和它发出的边边, 边的终顶点入度减一边的终顶点入度减一;如果边的终顶点入度减至如果边的终顶点入度减至0, 则该顶点进则该顶点进入度为零的顶点栈入度为零的顶点栈;u如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点个网络的顶点个数数, 则报告网络中存在有向环。则报告网络中存在有向环。126126n在算法实现时在算法实现时, 为了建立入度为零的顶点栈为了建立入度为零的顶点栈,可可以不另外分配存储空间以不另外分配存储空间, 直接利用入度为零的直接利用入度为零的顶点的顶点的count 数组元素。设立一个栈顶指针数组元素。设立一个栈顶指针top, 指示当前栈顶位置指示当前栈顶位置, 即某一个入度为零的即某一个入度为零的顶点。栈初始化时置顶点。栈初始化时置top = -1。n将将顶点顶点i 进栈时执行以下指针的修改：进栈时执行以下指针的修改： counti = top; top = i ; / top指向新栈顶指向新栈顶i, 原栈顶元素在原栈顶元素在counti中中n退栈操作可以写成：退栈操作可以写成： j = top; top = counttop; /位于栈顶的顶点记于位于栈顶的顶点记于 j, top退到次栈顶退到次栈顶127127拓扑排序时入度拓扑排序时入度为零的顶点栈在为零的顶点栈在count中的变化中的变化C0C1C2C3C4C513010313-112322-112221-1222012345012345012345012345toptoptoptop建栈建栈toptop顶点顶点4出栈出栈toptop顶点顶点0出栈出栈128128拓扑排序时入度拓扑排序时入度为零的顶点栈在为零的顶点栈在count中的变化中的变化C0C1C2C3C4C521-12222-1-12212-1-122-12-1-122-1012345012345012345012345toptoptoptoptop顶点顶点1出栈出栈top顶点顶点5出栈出栈顶点顶点3出栈出栈顶点顶点2出栈出栈129129拓扑排序的算法拓扑排序的算法template void TopologicalSort (Graph& G) int i, j, w, v; int top = -1; /入度为零顶点的栈初始化 int n = G.NumberOfVertices(); /网络中顶点个数 int *count = new intn; /入度数组兼入度为零顶点栈 for (i = 0; i i j; /输入一条边(i, j) while (i -1 & i -1 & j i j; for (i = 0; i n; i+) /检查网络所有顶点 if (counti = 0) /入度为零的顶点进栈 counti = top; top = i; for (i = 0; i n; i+) /期望输出n个顶点 if (top = -1) /中途栈空,转出 cout “网络中有回路！ endl; return; else /继续拓扑排序 v = top; top = counttop; /退栈v131131 cout G.getValue(v) endl; /输出 w = G.GetFirstNeighbor(v); while (w != -1) /扫描顶点v的出边表 countw-; /邻接顶点入度减一 if (!countw) /入度减至零,进栈 countw = top; top = w; w = G.GetNextNeighbor (v, w); /一个顶点输出后，调整其邻接顶点入度 /输出一个顶点，继续for循环132132n分分析析此此拓拓扑扑排排序序算算法法可可知知，如如果果AOV网网络络有有n个个顶顶点点，e条条边边，在在拓拓扑扑排排序序的的过过程程中中，搜搜索索入入度度为为零零的的顶顶点点，建建立立链链式式栈栈所所需需要要的的时时间间是是O(n)。在在正正常常的的情情况况下下，有有向向图图有有n个个顶顶点点，每每个个顶顶点点进进一一次次栈栈，出出一一次次栈栈，共共输输出出 n 次次。顶顶点点入入度度减减一一的的运运算算共共执执行行了了e次次。所所以以总总的的时间复杂度为时间复杂度为O(n+e)。133133用边表示活动的网络用边表示活动的网络(AOE(AOE网络网络) )n如果在如果在无有向环的带权有向图无有向环的带权有向图中中, 用有向边表用有向边表示一个工程中的示一个工程中的活动活动 (Activity), 用边上权值表用边上权值表示示活动持续时间活动持续时间 (Duration), 用顶点表示用顶点表示事件事件 (Event), 则这样的有向图叫做用边表示活动的则这样的有向图叫做用边表示活动的网络网络, 简称简称 AOE ( Activity On Edges ) 网络。网络。nAOE网络在某些工程估算方面非常有用。例如，网络在某些工程估算方面非常有用。例如，可以使人们了解：可以使人们了解：u完成整个工程至少需要多少时间完成整个工程至少需要多少时间(假设网络假设网络中没有环中没有环)? 134134u为缩短完成工程所需的时间为缩短完成工程所需的时间, 应当加快哪些应当加快哪些活动活动? n从源点到各个顶点从源点到各个顶点, 以至从源点到汇点的有向以至从源点到汇点的有向路径可能不止一条。路径可能不止一条。 这些路径的长度也可能这些路径的长度也可能不同。不同。 完成不同路径的活动所需的时间虽然完成不同路径的活动所需的时间虽然不同不同, 但只有各条路径上所有活动都完成了但只有各条路径上所有活动都完成了, 整整个工程才算完成。个工程才算完成。n因此因此, 完成整个工程所需的时间取决于从源点完成整个工程所需的时间取决于从源点到汇点的最长路径长度到汇点的最长路径长度, 即在这条路径上所有即在这条路径上所有活动的持续时间之和。活动的持续时间之和。这条路径长度最长的路这条路径长度最长的路径就叫做关键路径径就叫做关键路径(Critical Path)。135135a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10n要找出关键路径，必须找出关键活动要找出关键路径，必须找出关键活动, 即不按即不按期完成就会影响整个工程完成的活动。期完成就会影响整个工程完成的活动。n关键路径上的所有活动都是关键活动。因此关键路径上的所有活动都是关键活动。因此, 只要找到了关键活动只要找到了关键活动, 就可以找到关键路径。就可以找到关键路径。例如例如, 下图就是一个下图就是一个AOE网。网。136136定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量：1.事件事件Vi 的最早可能开始时间的最早可能开始时间Ve(i) 是从是从源点源点V0 到到顶点顶点Vi 的最长路径长度。的最长路径长度。2.事件事件Vi 的最迟允许开始时间的最迟允许开始时间Vli是是在在保保证证汇汇点点Vn-1 在在Ven-1 时时刻刻完完成成的的前前提提 下，事件下，事件Vi 的允许的最迟开始时间。的允许的最迟开始时间。3.活动活动ak 的最早可能开始时间的最早可能开始时间 Aek设设活活动动ak 在在边边上上, 则则Aek是是从从源源点点V0到到 顶点顶点Vi 的最长路径长度。因此的最长路径长度。因此, Aek = Vei。4.活动活动ak 的最迟允许开始时间的最迟允许开始时间 Alk 137137 Alk是在不会引起时间延误的前提下是在不会引起时间延误的前提下, 该活动该活动允许的最迟开始时间。允许的最迟开始时间。 Alk = Vlj-dur()。 其中其中, dur()是完成是完成 ak 所需的时间。所需的时间。5.时间余量时间余量 Alk-Aek 表示活动表示活动ak的最早可能开始时间和最迟允许的最早可能开始时间和最迟允许开始时间的时间余量。开始时间的时间余量。Alk = Aek表示活表示活动动 ak 是没有时间余量的关键活动。是没有时间余量的关键活动。n为找出关键活动为找出关键活动, 需要求各个活动的需要求各个活动的 Aek 与与 Alk，以判别是否，以判别是否 Alk = Aek。138138n为求得为求得Aek与与Alk, 需要先求得从源点需要先求得从源点V0到各到各个顶点个顶点Vi 的的Vei和和Vli。n求求Vei的递推公式的递推公式u 从从 Ve0 = 0 开始，向前递推开始，向前递推 S2, j = 1, 2, , n-1 S2 是所有指向是所有指向Vj 的有向边的有向边的集合。的集合。Ve = 6Ve = 12Ve = 9524Ve = 11? 14? 13? 已知求解139139n从从Vln-1 = Ven-1开始，反向递推开始，反向递推 S1, j = n-2, n-3, , 0S1是所有源自是所有源自Vj 的有向边的有向边的集合。的集合。n这两个递推公式的计算必须分别在这两个递推公式的计算必须分别在拓扑有序拓扑有序及及逆拓扑有序逆拓扑有序的前提下进行。的前提下进行。675Vl = 19Vl = 24Vl = 11Vl = 13? 17? 6? 已知求解140140n设设活动活动ak (k=1, 2, , e)在带权有向边在带权有向边上上, 其持续时间用其持续时间用dur ()表示表示, 则有则有 Aek = Vei； Alk = Vlj-dur()；k = 1, 2, , e。这样就得到计算关键路径的算法。这样就得到计算关键路径的算法。n为了简化算法为了简化算法, 假定在求关键路径之前已经对假定在求关键路径之前已经对各顶点实现了拓扑排序各顶点实现了拓扑排序, 并按拓扑有序的顺序并按拓扑有序的顺序对各顶点重新进行了编号。对各顶点重新进行了编号。1411411324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=1012345678Ve08122228404658Vl0812222840465812345678910Ae00812122222284046Al00812123222284046142142利用关键路径法求利用关键路径法求AOEAOE网的网的各关键活动各关键活动template void CriticalPath(graph& G) int i, j, k; E Ae, Al, dur; int n = G.NumberOfVertices(); E *Ve = new En; E *Vl = new En; for (i = 0; i n; i+) Vei = 0;for (i = 0; i Vej) Vej = Vei+dur; j = G.getNextNeighbor(i, j); Vln-1 = Ven-1; for (j = n-2; j 0; j-) /逆向计算Vl k = G.getFirstNrighbor (j); while (k != -1) dur = G.getWeight (j, k); if (Vlk-dur Vlj) Vlj = Vlk-dur; k = G.getNextNeighbor (j, k); 144144 for (i = 0; i n; i+) /求各活动的e, l j = G.getFirstNeighbor (i); while (j != -1) Ae = Vei; Al = Vlk-G.getWeight(i, j); if (Al = Ae) cout G.getValue(i) , G.getValue(j) ” 是关键活动 endl; j = G.getNextNeighbor (i, j); delete Ve; delete Vl; 145145注意注意n所有顶点按拓扑有序的次序编号。所有顶点按拓扑有序的次序编号。n仅计算仅计算 Vei 和和 Vli 是不够的，还须计算是不够的，还须计算 Aek 和和 Alk。n不是任一关键活动加速一定能使整个工程提前。不是任一关键活动加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所想使整个工程提前，要考虑各个关键路径上所有关键活动。有关键活动。n如果任一关键活动延迟，整个工程就要延迟。如果任一关键活动延迟，整个工程就要延迟。146146结束语结束语谢谢大家聆听！谢谢大家聆听！147