问题标签 [graph-theory]

我正在尝试在 java 中制作一个具有不同节点的图形。有些节点会连接到其他节点，有些则不会。如果它们已连接，则该节点的某个布尔值将为真，另一个变量将保存它所连接的节点的值。

...关于你们认为最好的解决方法有什么建议吗？

我遇到了一个问题，我在图中给出了 N 个节点，这些节点相互连接，然后给出一个矩阵，其中列出了一个节点连接到另一个节点（如果是，则为 1，如果不是，则为 0）。我想知道如何最好地解决这个问题。我认为这些是邻接矩阵？但是我将如何实现...

基本上，我试图摆脱这些的是找出特定节点是否连接到给定集合“S”中的所有其他节点。以及所选项目是否为集团...

我会很感激任何提示。

我担心这可能正在解决 NP-Complete 问题。我希望有人可以给我一个关于它是否存在的答案。我正在寻找更多的答案，而不仅仅是是或否。我想知道为什么。如果你可以说，“这基本上是这个问题'x'，它是/不是NP-Complete。（维基百科链接）”

（不，这不是作业）

有没有办法确定两个点是否连接在任意无向图上。例如，以下

点 A 到 M（没有“I”）是可以打开或关闭的控制点（如天然气管道中的阀门）。'+' 是节点（如管道 T），我猜 Well 和 House 也是节点。

我想知道我是否关闭了任意控制点（例如C），井和房子是否仍然连接（其他控制点也可能关闭）。例如，如果 B、K 和 D 关闭，我们仍然有一条通过 AEJFCGLM 的路径，关闭 C 将断开 Well 和 House。当然; 如果只是 D 被关闭，则仅关闭 C 不会断开 House。

另一种说法是，C 是桥/切边/地峡吗？

我可以将每个控制点视为图表上的权重（0 表示打开或 1 表示关闭）；然后找到 Well 和 House 之间的最短路径（结果 >= 1 表示它们已断开连接。我也可以通过多种方法短路算法以找到最短路径（例如，一旦到达 1 就丢弃路径，停止搜索一旦我们有任何连接井和房子的路径等）。当然，我也可以人为地限制在放弃之前要检查多少跳。

以前一定有人分类过这种问题，我只是漏掉了名字。

给定一个无向图 G = (V, E) 和两个顶点 s, t ∈ V。我们考虑 s 和 t 之间的简单路径。如果每个顶点最多访问一次，则路径很简单。

以下是 P 或 NP 完全的吗？

以下是否存在有效的算法多项式时间？

“n”表示图“V”中的顶点数

1. 是否有一条从 s 到 t 长度最多为 n/100 的简单路径？
2. 是否有一条从 s 到 t 长度至少为 n/100 的简单路径？
3. 是否有一条从 s 到 t 长度正好为 n/100 的简单路径？
4. 从 s 到 t 是否有两条边不相交的路径？（如果两条路径不共享边，则称它们是边不相交的。）

我的想法（如果我错了，请纠正我）感谢您的意见。

1. 我想我可以运行 Dijkstra 算法以在多项式时间内找到 S 和 T 之间的最短路径。所以问题 1 在 P 中。
2. 我认为有必要列举从 s 到 t 的所有简单路径。我不知道它的运行时间是多少，但我认为它会比多项式更糟糕。
3. 类似于上面的2。没有多项式算法。
4. 我不知道。我不知道有什么有效的（多时间算法）可以在两个节点之间找到多条路径，但这并不意味着它们不存在。

我可以轻松地为有向图的节点定义数据类型。

我可以使用 show 函数将图形保存到文件中，然后使用 read 恢复它。但是，show 无法应对循环。有没有一种简单的方法来保存和恢复图表？

有一个有向图（不一定连接），其中一个或多个节点被区分为源。从任何一个来源可访问的任何节点都被视为“点亮”。现在假设其中一条边被删除。问题是要确定以前点亮和不再点亮的节点。

我想可以考虑像城市电力系统这样的类比。

我一直在这里和那里阅读有关使用“蚁群”模型作为优化各种类型算法的启发式方法的内容。但是，我还没有找到一篇文章或书籍以介绍性的方式讨论蚁群优化，甚至是非常详细的讨论。谁能指出我可以了解更多关于这个想法的一些资源？

我有图，不知何故我需要在图中找到不包含图的任何其他边的所有闭合轮廓。

我在搜索谷歌，但只给了我图表:)

是否有任何库，或者您是否知道此类算法的名称。

谢谢

我需要某种节点图编辑器，希望它可以在 Mac 和其他平台上运行，以生成用户创建的具有属性的节点集合。然后，图形数据将用于我正在开发的数据驱动的应用程序中，如果应用程序可以以某种易于处理的格式保存图形，则值得称赞。到目前为止，我使用 XML 和树编辑器，但由于图形可以根据要求循环，树编辑器不再剪切它。

其他应用程序的插件也可以！

我喜欢关于面向对象设计的 Head First 系列书。这是对该主题的非常温和而有趣的介绍。我目前正在学习数据结构课程，发现我们使用的文本（Kruse/Ryba 数据结构和 C++ 中的程序设计）非常枯燥且难以理解。这主要是由于我认为我自己在数学领域的局限性。

有谁知道以更轻松的风格编写的数据结构文本，带有幽默感，仍然涵盖所有基础知识，如二叉树、B 树和图形？