问题标签 [graph-theory]

设 G 为图。所以 G 是一组节点和一组链接。我需要找到一种快速划分图形的方法。我现在正在处理的图表只有 120*160 个节点，但我可能很快就会在另一个上下文（不是医学，而是网站开发）中处理一个具有数百万个节点的等效问题。

所以，我所做的是将所有链接存储到一个图形矩阵中：

现在，如果节点 s 连接到节点 t，则 M 在位置 s,t 中保持 1。我确保 M 是对称的 M[s,t]=M[t,s] 并且每个节点都链接到自身 M[s,s]=1。

如果我记得很清楚，如果我将 M 与 M 相乘，结果是一个矩阵，它表示连接通过两个步骤到达的顶点的图。

所以我继续将 M 与自身相乘，直到矩阵中零的数量不再减少。现在我有了连接组件的列表。现在我需要对这个矩阵进行聚类。

到目前为止，我对算法非常满意。我认为它简单、优雅且相当快。我在这部分遇到了麻烦。

本质上，我需要将此图拆分为其连接的组件。

我可以遍历所有节点，看看它们连接到什么。

但是如何对矩阵进行排序以重新排序行。但我不知道是否有可能做到这一点。

以下是到目前为止的代码：

编辑：

有人建议我使用 SVD 分解。这是 5x5 图上的问题的简单示例。我们将使用它，因为在 19200x19200 方阵中不容易看到簇。

这里基本上有 4 个集群：(0),(1,3),(2),(4) 但我仍然看不到 svn 在这种情况下如何提供帮助。

并不是说我有时间适当地讨论这个以得出结论并调整我的代码，因为学校项目的第一阶段（第三阶段）是在 24 小时内，但至少我需要知道我是否做出了正确的决定。

我正在使用链表，这是我的结构：

基本上，我有很多城市，这些城市都连接在一起，就像一个图表。例如，A、B、C、D 和 E 它们按此顺序插入到结构City中。然后，我将 A 连接到 B，C 和 D，B 连接到 C，D，E，C 连接到 D，E 和 D 连接到 E。

现在，假设我需要去E市。这是链表中的最后一个，并且需要时间遍历链表。也许不是在这个有 5 个城市的例子中，但在真正的应用程序中，我应该至少支持 10,000 个城市。但是最短的路线是从A（这是起点）从C到E（或者可以是ADE或ABE，没关系）。

我的结构是否允许我找到从 A 到 E 的最短路径，而无需一一遍历整个链表？如果没有，我做错了什么？

如果是，我该怎么做？我不知道我怎么能找到这样的路径......

遍历图的函数是否同样适用于遍历树？

我有一组学生（为了概括起见，在标题中称为项目）。在这些学生中，有些人以粗暴着称。我们被告知一组“我讨厌 j”形式的仇恨关系。“我讨厌 j”并不意味着“j 讨厌我”。我们应该将学生排成一排（最前面的一排编号为 1），如果“我讨厌 j”，那么我应该排在编号严格小于 j 的排中（换句话说：在j 行前面的某行），这样我就不会向 j 扔任何东西（不允许转身）。找到所需的最小行数（每行不必有相同数量的学生）的有效算法是什么？

我们将做出以下假设：

1）如果我们将其建模为有向图，则图中没有环。最基本的循环是：如果“我讨厌 j”为真，“j 讨厌我”为假。因为否则，我认为订购将变得不可能。

2）小组中的每个学生至少被另一个学生讨厌或至少讨厌另一个学生。当然，也会有学生既被一些学生讨厌，又反过来讨厌其他学生。这意味着没有不属于图表一部分的流浪学生。

更新：我已经考虑过用 i --> j if 'i hats j 构建有向图并进行拓扑排序。但是，如果我必须将所有学生排成一行，则一般拓扑排序会更适合。由于这里的行有所不同，我试图弄清楚如何将变化因素考虑到拓扑排序中，这样它就给了我想要的东西。

当您回答时，请说明您的解决方案的复杂性。如果有人提供代码并且您不介意该语言，那么我更喜欢 Java，但当然任何其他语言都一样好。

JFYI 这不适用于任何类型的作业（顺便说一句，我不是学生：））。

在通过 XAML 进行了长时间的学习循环之后，我回到了 HTML 和 javascript，并意识到声明性代码的概念——就转换规则而言——是一个非常强大的概念。

尽管语法过多，XML 的 XSLT 处理是声明式转换编程的基石。然而，我总是发现很难理解 XSLT 将如何用于日常任务（使用 XML）。

除了生成 HTML 之外，还有哪些 XSLT 优雅地解决编程问题的好例子？

我猜它擅长图形转换和数据再处理......

编辑：我希望有一些实际的例子——让我完全不了解 xslt 的一件事是代码的视觉复杂性。

图的传递闭包在此处定义，例如：http: //mathworld.wolfram.com/TransitiveClosure.html

在 O(n^3) 中很容易实现，其中 n 是顶点数。我想知道它是否可以在 O(n^2) 时间内完成。

在阅读了 Stevey Yegge 的在 Google 获得那份工作的文章后，我发现这句话很有趣：

每当有人给你一个问题时，想想图表。它们是表示任何类型关系的最基本和最灵活的方式，因此任何有趣的设计问题都需要一个 50 到 50 个镜头，其中包含一个图表。在转向其他解决方案类型之前，请绝对确保您想不出使用图表来解决它的方法。这个提示很重要！

图数据结构/算法最能代表和/或解决的问题有哪些示例？

我能想到的一个例子：导航单元（ala Garmin，TomTom），提供从您当前位置到另一个位置的道路方向，利用图表和高级路径算法。

还有一些是什么？

给定一个在坐标平面上相互连接的 n 个节点的图，找到包含 m 个节点的最小距离子树的最佳方法是什么？

我发现这个问题的唯一解决方案是生成要连接的节点的所有组合，并尝试通过 Kruskal 或 Prim 算法连接这些节点，同时忽略其余的，然后比较所有创建的树并找到最小的树，但是这个当涉及到较大的树木时，效率并不高。

有没有更快、更有效的算法/方法？

假设我有按以下方式连接的节点，我如何得出给定点之间存在的路径数量以及路径详细信息？

找到从 1 到 7 的路径：

答案：找到 2 条路径，它们是

在这里找到的实现很好，我将使用相同的

这是python中上述链接的片段

使用带有捆绑属性的 boost::graph。我希望能够使用各种不同的可能边缘加权方案来运行搜索。如果可能的话，我不想为捆绑的属性创建一个额外的类，并根据搜索类型传递不同的权重图，而无需创建新图表或修改图表中的所有现有属性。

我可以为 edge_weight_t 手动构建 property_map 吗？这是我到目前为止所得到的：

我只想能够做到

并将距离[e]分配给适当的值——

还是我只需要分解并为捆绑的属性组成一个新结构——我一直试图避免的事情——并从中创建权重图？boost::graph 的新功能；不要假设我在这里没有做完全愚蠢的事情。