fdh*_*fdh 16 algorithm computer-science graph-theory
我找到了几种解释如何在有向图中找到强连通组件的算法,但没有一种解释为什么你想要这样做.强连接组件的一些应用是什么？
twm*_*wmb 18
你应该查看Tim Roughgarden在Coursera上的算法入门课程.对于他过去的每个算法,他解释了它的一些应用.非常有用,让人看到学习算法的价值!
我记得他所说的强连接组件的使用是可以用它来查找在大量数据中更密切相关的人群.想想facebook以及他们如何推荐可能是你朋友的人......
这也可用于查看人口的大块.说,"哇,这个巨大的组件都有倒退的爱好,喜欢吃发霉的披萨!"它可能显示出相关性.发霉的披萨广告商会使用这些数据来定位喜欢倒退的人.谁知道!
一个例子是模型检查:
在模型检查中 - 我们有一个状态机,它代表我们的软件/硬件的模型,我们试图在其上证明时间逻辑1公式.
例如:公式EG(p)表示:图中有一个路径,每个状态 - 逻辑公式p产生的路径true.
的用于证明如果EG(p)为在图上真正算法(模型)是寻找最大强连通分量(SCC),然后检查路径导致它在曲线图.
请注意,模型检查广泛应用于行业 - 特别是为了证明硬件组件的正确性.
(1)时间逻辑对计算机科学的重要性很大,其发明者Amir Pnueli获得了图灵奖!
另一个应用程序可以在车辆路由应用程序中找到。道路网络可以建模为有向图，顶点是交叉点，弧线是有向路段或单独的车道。如果图形不是强连通的，那么车辆可能会被困在图形的某个部分（即它们可以进入，但不能离开）。
在许多这些车辆路径选择应用程序中，您希望为特定区域生成路径（例如城市内的路径问题）。在生成路线之前，您必须提取街道数据，例如从 Google Maps、Here 地图或 Open Street 地图中提取。这些地图不仅涵盖您感兴趣的区域，而且涵盖整个世界。因此，您最终会拍摄感兴趣区域的快照，例如通过计算地理坐标位于感兴趣区域内的所有交叉点的诱导子图。生成的子图不一定是强连通的（例如，您可以有一条道路进入和离开该区域，但不与该区域内的任何其他道路连接）。然后通过枚举所有强连通分量对子图进行预处理，