问题标签 [adjacency-matrix]

我正在编写代码来从边列表中创建一个矩阵。

然而，当我运行上述代码时，我得到了一个不在输入数据中的“幻影边缘”，这继续搞砸了我的程序的其余部分。边是矩阵中的 9,2，或元素代码形式的 8,1。

矩阵中的所有元素都预先初始化为 0。

这是与矩阵有关的输入数据：

以下是处理输入的函数：

*不应该存在的条目，不在输入数据中

如何将一棵树分解为森林，使每棵树包含偶数个顶点？我需要随机分解树并检查每个森林吗？我已经创建了邻接矩阵，但无论如何都没有帮助我！
实现相同目标的正确方法应该是什么？

在几年前的算法课程中，我遇到了一个有趣的图形表示。它基本上是一个路径矩阵，但有额外的信息。每个单元格都包含（可能为空的）与您可以通过到达Aij的顶点相邻的列表。ij

例如，有向图非正式地表示为：

(Z → X) (Z → Y) (X → W) (Y → W)

得到以下矩阵：

当维护这样的矩阵时，您不仅可以知道是否存在从i到的路径j，还可以知道所有可能的路径是什么。

但我终其一生都无法在网络上找到对这种表示的任何参考。它叫什么？

我对 Java 很陌生，我才研究了几个星期，这个项目让我很困惑。说明是创建一个雷区游戏，该游戏生成一个随机起点、一个随机终点和两个地雷。用户必须在不撞到地雷的情况下从头到尾导航。我的目标是测试用户是否进行了有效的移动，然后更改他单击的按钮的颜色。因此，从头到尾制作了一条路径。当他点击检查按钮时，它会告诉他他是否点击了一个隐藏的矿井，以及他是赢还是输。

这是我到目前为止所拥有的。

任何有关方法的帮助，或有关如何提高效率的建议将不胜感激。

}

您好，我了解邻接列表和矩阵的概念，但我对如何在 Python 中实现它们感到困惑：

实现以下两个示例的算法可以实现，但从一开始就不知道输入，因为他们在示例中对其进行了硬编码：

对于邻接列表：

对于邻接矩阵：

再次任何帮助将不胜感激，谢谢！

我目前的问题如下。我有一个有向 1-mode 边缘列表，表示在某一年参与联合项目的演员对，可能看起来像：

现在我只需要一个特定年份的子集。并非所有参与者都在这一年活跃，因此子集的维度不同。对于后续的网络分析，我需要一个加权的有向邻接矩阵，所以我使用 [network package] 的选项来创建它。我首先将其加载为网络对象，然后将其转换为邻接矩阵。

结果矩阵看起来有点像

到目前为止，一切都很好。我现在的问题是：对于我计划做的进一步分析，我需要一个具有相同维度和顺序的每一年的邻接矩阵。这意味着来自初始数据集的所有参与者都必须是相应年份的矩阵的行名和列名，但矩阵应该只包含这一特定年份的观察对。我希望我的问题很清楚。我很欣赏任何建设性的解决方案。

我的想法 ATM 如下：我创建了一个初始数据集和缩减数据集的矩阵。然后我将那里的所有矩阵值设置为零。然后我以某种方式将它与缩减矩阵匹配，并在正确的行和列中填充正确的值。不幸的是，我不知道这怎么可能。

有人知道如何解决这个问题吗？

我正在尝试确定两个元素之间的传递关系。我正在用 c 编码。

例如：a->b 由第 1 行第 2 列的邻接矩阵中的“1”表示。

所以如果 a->b 和 b-> c 和 c->d

我想确定是否 a->d。无需更新邻接矩阵。

我采用的方法：检查与 a 对应的行中的所有 1。假设第二列中有一个 1，即 b。[(a->b)] ，现在检查 b->d 是否继续检查 B 行中的所有 1 并继续到第 26 行。

我并不真正关心复杂性。我只是希望实现这一点。

我开发了一个小程序，它在图形之间随机生成多个连接（计数的值也可以是随机的，但是为了测试目的我已经定义了const value，它可以随时重新定义为随机值）。

代码是 C#：http: //ideone.com/FDCtT0

（结果：成功时间：0.04s 内存：36968 kB 返回值：0）

如果您不知道什么是邻接矩阵，请访问此处：http ://en.wikipedia.org/wiki/Adjacency_matrix

我认为，我的代码版本没有经过优化。如果我要使用大小为：10k x 10k的大型矩阵。

1. 您有什么建议，在此任务中如何更好地并行计算？我是否应该使用信号量等一些储物柜模型来对大型矩阵进行多线程计算。

2. 您对重新设计程序架构有什么建议。我应该如何为大型矩阵做准备？

3. 如您所见，在ideone上，我展示了时间执行参数并在 RAM 中分配了内存。我的程序执行的渐近值是多少？是O(n^2)吗？

所以我想听听你的建议如何增加渐近标记，使用信号量进行并行计算（或者更好的线程锁定模型）。

谢谢！

PS：SO不允许在没有格式化代码的情况下发布主题，所以我在最后发布（完整程序）：

我正在编写一个 C 程序来查找传递性。在二维数组中，如果 adj[0][1] = 1 和adj[1][2] = 1，我也想标记adj[0][2]为1。这应该适用于矩阵中的任何传递关系。

请为此提供一些代码。

我在 Java 中有一个字符串数据类型邻接矩阵：

我想将我的邻接矩阵 A 读入 MySQL 表。问题是我永远不知道我需要多少行/列（我也不想创建所有列）。我认为解决这个问题的诀窍是动态创建列。如何“即时”添加列？

一旦我可以动态添加列，我就可以逐行读取矩阵。

1. 我希望能够将数据视为矩阵。

非常感谢所有帮助！