Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 2)拓扑排序 3)关键路径 4)最短路径 要掌握图的基本概念:顶点,弧,边,无向图,有向图,邻接点,度,出度,入度。 完全图:有n(n-1)2条边的无向图称为完全图 有向完全图:具有n(n-l)条弧的有向图称为有向完全图 连通图:如果对于图中任意两个顶点都是连通的,则称为连通图 连通分量:无向图中的极大连通子图 强连通图:在有向图G中,如果对于每一对ⅵi,yi,ⅵi∞vj。从ⅵ到v和从v到ⅵ 都存在路径,则称G为强连通图。 强连通分量:有向图中的极大强连通子图称为有向图的强连通分量 生成树:一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以 构成一棵树的n-1条边。一棵n个顶点的生成树有且仅有n-1条边 如果一个图有n个顶点和小于n-1条边,则是非连通图。如果它多于n-1 条边,则一定有环。但是,有n-1条边的图不一定是生成树 要掌握图的存储结构:1)数组表示法,邻接矩阵 2)邻接表及逆邻接表 尤其要会画邻接表,逆邻接表,会由邻接表读出某顶点的度,出度,入度。 无向图的邻接矩阵为对称矩阵,有向图的邻接矩阵则不一定对称 要掌握图的遍历的算法 1)深度优先,类似于二叉树的先序遍历 2)广度优先,类似于树的层次遍历 图的应用: 1)最小生成树(各边权值不同,则最小生成树唯一) 要掌握两种典型算法:普里姆算法,克鲁斯卡尔算法。会画出最小生成树。 2)拓扑排序 AOV网,活动优先关系网,其中不能有有向环 拓扑排序方法:在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶 点和所有以它为尾的弧。重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前 驱的顶点为止。后一种情况则说明有向图中存在环 3)关键路径 AOE网是一个带权的有向无环图,其中顶点表示事件,弧表示活动,权表示 活动持续的时间,AOE网可用来估算工程的完成时间。网中只有一个入度为零的点(称为 源点)和一个出度为零的点(叫做汇点)。 AOE网中路径长度最长的路径叫做关键路径 4)最短路径:掌握一道必会的习题 习题: )可判断一个网是否有环的方法:拓扑排序,深度优先搜索,求关键路径。但广度优先搜 索不可以Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 2）拓扑排序 3）关键路径 4）最短路径 要掌握图的基本概念：顶点，弧，边，无向图，有向图，邻接点，度，出度，入度。 完全图：有 n (n-1)/2 条边的无向图称为完全图。 有向完全图：具有 n (n-1)条弧的有向图称为有向完全图。 连通图：如果对于图中任意两个顶点都是连通的，则称为连通图。 连通分量：无向图中的极大连通子图。 强连通图：在有向图 G 中，如果对于每一对 vi，vj，vi<>vj。从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 为强连通图。 强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。 生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以 构成一棵树的 n-1 条边。一棵 n 个顶点的生成树有且仅有 n-1 条边。 如果一个图有 n 个顶点和小于 n-1 条边，则是非连通图。如果它多于 n-1 条边，则一定有环。但是，有 n-1 条边的图不一定是生成树 要掌握图的存储结构：1）数组表示法，邻接矩阵 2）邻接表及逆邻接表 尤其要会画邻接表，逆邻接表，会由邻接表读出某顶点的度，出度，入度。 无向图的邻接矩阵为对称矩阵，有向图的邻接矩阵则不一定对称。 要掌握图的遍历的算法： 1）深度优先，类似于二叉树的先序遍历 2）广度优先，类似于树的层次遍历 图的应用 ： 1） 最小生成树（各边权值不同，则最小生成树唯一） 要掌握两种典型算法：普里姆算法，克鲁斯卡尔算法。会画出最小生成树。 2）拓扑排序 AOV 网，活动优先关系网，其中不能有有向环。 拓扑排序方法：在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶 点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前 驱的顶点为止。后一种情况则说明有向图中存在环。 3）关键路径 AOE 网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示 活动持续的时间，AOE 网可用来估算工程的完成时间。网中只有一个入度为零的点（称为 源点）和一个出度为零的点（叫做汇点）。 AOE 网中路径长度最长的路径叫做关键路径。 4）最短路径：掌握一道必会的习题。 习题： 1）可判断一个网是否有环的方法：拓扑排序，深度优先搜索，求关键路径。但广度优先搜 索不可以