正定微信公众号开发【正定网络推广】正定建站、正定网站维护、正定网页制作、正定微信小程序代运营公司

正定微信公众号开发【正定网络推广】正定建站、正定网站维护、正定网页制作、正定微信小程序代运营公司

正定县，河北省石家庄市辖县，位于太行山东麓的山前倾斜平原、山前冲积扇的中上部，因“真正安定”之意得名 [1-2]  ；正定县位于东经114°23′~114°43′，北纬38°6′~38°22′，总面积486平方千米，气候型为温带季风气候，四季分明，多年平均气温13.1℃，多年平均降水量550毫米 [3]  ；截至2020年10月，正定县下辖2个街道、3个镇和5个乡，境内设有中国（河北）自由贸易试验区正定片区和正定新区；截至2019年末，正定县常住人口为51.7万人 [1]  。

正定县前身为真定县，有1600多年的建城史，最初为鲜虞国都城，后为中山国都城，建县始于秦始皇统一中国后设立的东垣县，“真定”一名始于汉高祖十一年（前196年）改东垣县为真定县，最终于清雍正元年（1723年）改为现名 [2]  。正定县是京津冀城市群、石家庄都市圈的重要城镇，境内建有石家庄正定国际机场，有京广高速铁路过境 [4]  。正定县有“九楼四塔八大寺，二十四座金牌坊”，有“古建艺术宝库”美称 [1]  。

2020年上半年，正定县财政收入为35.7亿元，同比增长5.8%；一般公共预算收入为26.9亿元，同比增长10.1%；固定资产投资为116.2亿元，同比增长11%；服务业增加值为100.3亿元，同比增长11%；规模以上高新技术产业增加值达5.9亿元，同比增长18%；社会消费品零售总额达40.8亿元，同比增长10%；外贸进出口总额达91亿元，同比增长366%；城乡居民人均可支配收入分别为18146元和10260元，同比增长8.2%和8.7% [5]  。

9.7.5　可达性测试的运行时间

假设有向图G 含n 个节点与m 条弧。还假设G 是用9.6节中的GRAPH数据类型表示的。首先，假设我们想为某节点u 找到其可达集。将所有节点初始化为UNVISITED需要O(n)的时间。对dfs(u,G)的调用要花O(m)的时间，而且再次检查所有节点看哪些节点被访问过需要O(n)的时间。在检查节点之时，我们还可以创建由从节点u 可达的节点组成的表，这仍然只用花O(n)的时间。因此，为一个节点找到可达集要花O(m)的时间。

现在假设需要为所有n 个节点找出可达集。我们可以重复该算法n 次，为每个节点执行一次该算法。因此，总时间为O(mn)。

9.7.6　通过深度优先搜索寻找连通分支

在9.4节中，我们给出了为节点数为n 且节点数与边数较大值为m 的无向图寻找连通分支的算法，该算法的运行时间为O(m logn)。我们用于合并分支的树结构本身是很有意义的，例如，可以利用它帮助实现克鲁斯卡尔的最小生成树算法。不过，如果使用深度优先搜索，我们可以更高效地找到连通分支。正如接下来将要看到的，O(m)的时间就足够了。

思路就是把无向图当作边被两个方向上的弧替代后的有向图。如果用邻接表表示图，那么甚至不用对这种表示进行任何修改。现在为该有向图构建深度优先搜索森林，森林中的每棵树都是该无向图的一个连通分支。

传递闭包和自反传递闭包

设R 是集合S 上的二元关系。可达性问题就可以视作计算R 的自反传递闭包，通常将其表示为R *。关系R *是满足以下条件的有序对(u，v )的集合，在由R 表示的图中，从节点u 到节点v 存在长度为0或0以上的路径。

另一种非常类似的关系是R+，也就是R 的传递闭包，它是满足如下条件的有序对(u，v )的集合。在由R 表示的图中，从节点u 到节点v 存在长度为1或1以上的路径。R *和R+之间的区别在于，(u，u)对S 中的每个u 而言都在R *中，而当且仅当从u 到u 之间存在一条长度为1或1以上的环路时，(u，u)才在R+中。要从R *计算R+，只需要检查每个节点u 是否有来自其可达节点（包括它本身）的进入弧（enteringarc），如果没有，就将u 从它自己的可达集中删除。

要知道原因，首先要注意到有向图中的弧u→v 的出现表示存在边{u，v }。因此，树中的所有节点都是连通的。

现在我们必须证明反向的命题，也就是如果两个节点是连通的，那么它们在同一棵树中。假设在无向图中存在连通不同树中两个节点u 和v 的路径。假如u 的树是首先构建起来的。那么在有向图中存在从u 到v 的路径，这表明v 和该路径上的所有节点都应该已经被添加到含u 的树中。因此，当且仅当无向图中的节点在同一棵树中时，它们才是连通的，也就是说，这些树都是连通分支。

示例 9.24

再次考虑图9-4中的无向图。图9-38展示了我们可以为该图构建的一种可能的深度优先搜索森林。要注意这3棵深度优先搜索树是如何与3个连通分支对应的。

图 9-38　深度优先搜索森林将无向图分为连通分支

9.7.7　习题

1. 为图9-37所示的图找出所有拓扑次序。

2. * 假设R 是定义域D 上偏序关系。我们可以用R 的图来表示R，其中节点是D 中的元素，而且只要uRv 且u≠v 就存在弧u→v。设(v1，v2，…，vn)是R 的图的拓扑次序。设关系T 是这样定义的，只要i≤j，就有viTvj 。证明下列命题。

(a) T 是全序关系。

(b) R 中的有序对是T 中有序对的子集，也就是，T 是包含了偏序关系R 的全序关系。

3. 对图9-21所示的图（在将其转换为对称的有向图之后）应用深度优先搜索，找出其连通分支。

4. 考虑含有弧a→c，b→a，b→c，d→a 和e→c 的图。

(a) 对该图进行环路测试。

(b) 为该图找出所有的拓扑次序。

(c) 为每个节点找出可达集。

5. * 在9.8节中，我们会考虑找到从源节点s出发的最短路径的一般问题。也就是说，如果从s 到各个节点u 的最短路径存在，我们希望弄清这些最短路径的长度。如果是有向无环图，这个问题就要简单一些。给出算法，计算有向无环图G 中从节点s 到各节点u 的最短路径的长度，如果这样的路径不存在则是无限长。大家设计的算法应花费O(m)的时间，其中m 是图G 中节点数和弧数的较大者。证明自己的算法具有该运行时间。提示：首先对G 进行拓扑排序，依次访问每个节点。在访问节点u 时，根据已经计算出的s 到u 的前导的最短距离来计算从s 到u 的最短距离。

6. * 为有向无环图G 给出计算以下几项内容的算法。大家给出的算法应该有O(m)的运行时间，其中m 是G 中节点数和弧数的较大者，而且大家应该证明这一运行时间就是自己设计的算法所需要的。提示：对习题(5)中的思路加以改造。

(a) 对每个节点u，找到从u 到任意节点的最长路径的长度。

(b) 对每个节点u，找到从任意节点到u 的最长路径的长度。

(c) 对给定的源节点s 和G 的所有节点u，找到从s 到u 的最长路径的长度。

(d) 对给定的源节点s 和G 的所有节点u，找到从u 到s 的最长路径的长度。

(e) 对每个节点u，找到经过u 的最长路径的长度。

9.8　用于寻找最短路径的迪杰斯特拉算法

假设有一幅图，它既可能是有向图也可能是无向图，它的弧（或边）都带有表示弧（或边）的“长度”的标号。图9-4就是个例子，它展示了夏威夷群岛的特定公路的距离。想知道两个节点间的最小距离是特别平常的事，例如，地图上通常会带有行车距离的表格，从而指示出人们一天中可以开多远，或是有助于确定经过不同的中间城市的两条路线中哪条更短。类似的问题会给每条弧关联上沿着该弧行进所花的时间，或者可能关联上经过该弧的开销。那么两个节点间的最小“距离”就分别对应着出行的时间或费用。

一般而言，路径的距离是该路径上所有弧（或边的）标号之和。而从节点u 到节点v 的最小距离是从u 到v 的任意路径的距离中最小的那个。

正定微信公众号开发【正定网络推广】正定建站、正定网站维护、正定网页制作、正定微信小程序代运营公司