我找到了几种算法来解释如何在有向图中找到强连通分量，但没有一个解释你为什么要这样做。强连接组件有哪些应用？
问问题
7106 次
3 回答
23
您应该在 Coursera 上查看 Tim Roughgarden 的算法简介课程。对于他介绍的每一种算法，他都会解释它的一些应用。很有用，让人看到学习算法的价值！
我记得他说的强连接组件的使用是人们可以用它来找到在大量数据中关系更密切的人群。想想 Facebook 以及他们如何推荐可能是你朋友的人......
这也可以用来查看人口的块。说，“哇，这个巨大的组件都有倒退的爱好，喜欢吃发霉的披萨！”它可以显示相关性。发霉披萨的广告商会使用这些数据来定位喜欢倒着走的人。谁知道！
于 2012-06-26T17:25:19.040 回答
10
一个例子是模型检查：
在模型检查中 - 我们有一个状态机，它代表我们的软件/硬件模型，我们尝试在其上证明时间逻辑1公式。
例如：公式的EG(p)意思是：图中有一条路径，其中对于每个状态 - 逻辑公式p产生true。
证明 EG(p) 在图（模型）上是否为真的算法是找到最大强连通分量（SCC），然后检查图中通向它的路径。
请注意，模型检查在行业中得到广泛应用——尤其是用于证明硬件组件的正确性。
(1)时序逻辑对计算机科学的重要性是巨大的，它的发明者Amir Pnueli因此获得了图灵奖！
于 2012-06-26T17:35:06.030 回答
6
另一个应用程序可以在车辆路线应用程序中找到。道路网络可以建模为有向图，顶点是交叉点，弧线是有向路段或单独的车道。如果图表不是强连接的，那么车辆可能会被困在图表的某个部分（即它们可以进入，但不能离开）。
在许多这样的车辆路线应用程序中，您希望为特定区域生成路线（例如城市内的路线问题）。在生成路线之前，您必须提取街道数据，例如从 Google 地图、Here 地图或 Open Street 地图中提取。这些地图不仅涵盖了您感兴趣的区域，而且涵盖了整个世界。因此，您最终会拍摄感兴趣区域的快照，例如通过计算地理坐标位于感兴趣区域内的所有交叉点的诱导子图。生成的子图不一定是强连接的（例如，您可以有一条进出该区域的道路，但不与该区域内的任何其他道路连接）。然后通过枚举所有强连接的组件来预处理子图，
于 2018-09-28T10:57:31.667 回答