问题标签 [graph-theory]

我需要能够在 python 中操作一个大的（10^7 个节点）图。每个节点/边对应的数据是最少的，比如说，少量的字符串。就内存和速度而言，最有效的方法是什么？

dict 的 dict 更灵活、更易于实现，但我直观地希望列表列表更快。list 选项还要求我将数据与结构分开，而 dicts 将允许以下内容：

你有什么建议？

是的，我应该更清楚我所说的效率是什么意思。在这种特殊情况下，我的意思是随机访问检索。

将数据加载到内存中并不是一个大问题。这是一劳永逸的。耗时的部分是访问节点，以便我可以提取信息并测量我感兴趣的指标。

我没有考虑将每个节点都设为一个类（所有节点的属性都相同），但似乎这会增加额外的开销层？我希望有人对他们可以分享的类似案例有一些直接的经验。毕竟，图是 CS 中最常见的抽象之一。

这两种数据结构可以解决的最常见问题是什么？

对我来说，对以下书籍也有建议会很好：

• 实施结构
• 实施并解释使用它们的算法的推理

平面文件和关系数据库为我们提供了一种序列化结构化数据的机制。XML 非常适合序列化非结构化的树状数据。

但是很多问题最好用图表来表示。例如，热模拟程序将使用通过电阻边缘相互连接的温度节点。

那么序列化图结构的最佳方法是什么？我知道 XML 在某种程度上可以做到这一点——就像关系数据库可以序列化复杂的对象网络一样：它通常可以工作，但很容易变得丑陋。

我知道 graphviz 程序使用的点语言，但我不确定这是最好的方法。这个问题可能是学术界可能正在研究的问题，我很想参考任何讨论这个问题的论文。

我正在寻找具有一些不寻常属性的图形算法。

图中的每条边要么是“上”边，要么是“下”边。

一条有效的路径可以经过不定数量的“up”，然后是不定数量的“down”，反之亦然。但是，它不能多次改变方向。

例如，有效路径可能是 A “up” B “up” C “down” E “down” F 无效路径可能是 A “up” B “down” C “up” D

什么是找到两个节点之间最短有效路径的好算法？如何找到所有等长的最短路径？

寻找一种很好的方法来跟踪两个节点之间的广度优先遍历，而无需对图一无所知。与深度优先（如果路径不成功，您可以丢弃路径）相比，您在遍历过程中可能有很多“开放”的可能性。

我正在尝试确定完成下述任务的最佳时间效率算法。

我有一组记录。对于这组记录，我有连接数据，指示该组中的记录对如何相互连接。这基本上表示一个无向图，记录是顶点，连接数据是边。

集合中的所有记录都具有连接信息（即不存在孤立记录；集合中的每条记录都连接到集合中的一个或多个其他记录）。

我想从集合中选择任意两条记录，并能够显示所选记录之间的所有简单路径。“简单路径”是指路径中没有重复记录的路径（即仅限有限路径）。

注意：两个选择的记录总是不同的（即开始和结束顶点永远不会相同；没有循环）。

例如：

如果我选择 B 作为我的开始记录，E 作为我的结束记录，我希望找到所有通过记录连接的简单路径，这些路径将记录 B 连接到记录 E。

这是一个例子，实际上我可能有包含数十万条记录的集合。

我正在尝试在 ASP 网页上绘制图表。我希望 API 能有所帮助，但到目前为止我还没有找到。

该图包含标记的节点和未标记的方向边。理想的输出是这样的。

任何人都知道任何预先构建的东西可以提供帮助吗？

我真的很喜欢 Yahoo Pipes 的界面（http://pipes.yahoo.com/pipes/），并且想为不同的问题创建一个类似的界面。是否有任何库可以让我创建具有相同基本外观的界面？

我特别喜欢管道的行为方式以及它们不仅仅是直线的方式。

编辑：该应用程序将是基于网络的。我愿意使用 Flash 或 Javascript。

所以我正在从麻省理工学院的 OpenCourseWare 学习离散数学课程，我想知道......我看到了关系和图形之间的联系，但还不足以“拥有”它。我也在 SQL 中实现了一个简单的状态机，所以我很好地理解了图表，只是没有更严格地研究关系和集合是如何应用的。我是否应该遵循 Yegge 的思路，只浏览那些我不喜欢摸索的东西，等我学到更多东西后再回来？我希望能够更好地分析我每天创建的图形结构（听起来很有趣），并且我想确保我现在没有传递有价值的信息。

（编辑：我想更好地了解不同的集合和关系属性如何与图论等事物相关，以及基本图论如何与集合/关系相关。）

有什么好的资源可以让我了解更多信息吗？我正在使用 Rosen 的第 5 版离散数学及其应用，以防万一。

谢谢！

我在我的一本 AI 书籍中读到，在模拟或游戏中用于寻路的流行算法（A-Star、Dijkstra）也用于解决著名的“15 谜题”。

谁能给我一些关于如何将 15 谜题简化为节点和边图的指示，以便我可以应用其中一种算法？

如果我将图中的每个节点都视为游戏状态，那么那棵树不会变得很大吗？或者这只是这样做的方法吗？