问题标签 [adjacency-matrix]

我只是想知道如何使用邻接矩阵来解决图形问题。

例如，对于我的程序，我有两个项目的汇率。

构建有向图的输入：6 件衬衫 15 件袜子 构建有向图的输入：2 件袜子 1 件内衣

有向图：

衬衫--(6/15)-- 袜子--(2/1)-- 内衣

所以从衬衫到袜子的边是 6，从袜子到衬衫的边是 15，袜子到内衣是 2，内衣到袜子是 1。

要比较的输入：袜子衬衫解决方案：15 袜子 6 衬衫

要比较的输入：衬衫内衣解决方案：12 件衬衫 15 件内衣

我的问题是如何用邻接矩阵来表示它并能够获得它的权重来解决问题。

对于上述问题，我正在考虑使用一个看起来像这样的邻接矩阵。

这是一个好的开始吗？我试图在代码之前获取逻辑。

只是在寻找更多关于如何使用更多项目和单独图表在更大范围内执行此操作的信息。

我正在使用邻接矩阵来表示我的加权单向大图的所有顶点。在该图中，没有边将顶点连接到自身。这使得我的邻接矩阵的所有对角元素null。由于我的图很大，所以在邻接矩阵中我不需要在左三角形中保存任何元素。下面是一个带有邻接矩阵的小样本图。

在单向图中，左三角形只是右三角形的镜像。即adjacency_matrix[i][j]，adjacency_matrix[j][i]相同。那么为什么要存储左三角形。对于大图，这个技巧可以节省很多内存。同时，对角元素也为零，因为没有边将顶点连接到自身。即adjacency_matrix[i][i]为零。但是我该如何实现呢？这里可以使用二维数组吗？

是否可以将此处定义的 1 和 0 的邻接矩阵转换为此处定义的距离矩阵， 其中每个链接的单位长度为 1？

'正在尝试检索第一个和最后一个节点之间的最短路径。问题是我的代码总是返回 0。我有一种感觉，这是因为它正在计算第一个节点和第一个节点之间的距离，它会变为零，但我不是 100%。为什么我的代码总是返回 0？

adj矩阵为[10][10]且所有节点都连通，g.network[][]为矩阵。

我正在完成一个课堂实验室，它采用邻接矩阵，并确定顶点之间的连通性。虽然我的代码运行，但它没有给出正确的结果。

我相信我的 while 循环中的第二个 if 语句存在问题。任何帮助是极大的赞赏。代码如下：

这是我收到的输出：

哪个明显缺少 0 和 2 之间的另一个连接是正确的？

我正在尝试在 numpy 中生成对称矩阵。具体来说，这些矩阵将具有随机位置条目，并且每个条目中的内容可以是随机的。沿着主对角线，我们不关心那里有什么实体，所以我也将它们随机化。

我采用的方法是首先生成一个 nxn 全零矩阵，然后简单地循环遍历矩阵的索引。但是，考虑到循环在 python 中相对昂贵，我想知道是否可以在不使用 python 的 for 循环的情况下实现相同的目标。

numpy 中是否有一些东西可以让我更有效地实现我的目标？

这是我当前的代码：

谁能告诉我如何通过邻接矩阵和列表使用向量表示图形。还有如何在 c & c++ 中表示树。如何在 C 中使用邻接矩阵和列表来表示图形。

我以多种方式问过这个问题，首先是：

当您有邻接列表时，顺序是否重要？假设我有邻接列表 {1, 2, 5} 是否等同于 {2, 1, 5}？或者顺序是否意味着什么，因此这两个列表不等价？

我收到了几个答案，包括仅在图形是定向的并且顺序表示与顺时针相邻节点排列有关的情况下才重要..？我也被认为没有关系，但是他更希望根据权重（如果使用）对其进行排序，例如互联网的排序方式 - 页面排名算法。尽管我认为我传达了要点，但我不认为要准确地解释这些回答中的任何一个。任何想法表示赞赏。

此外，我已经改进了我的问题，如果得到回答，我认为会给我我所追求的确切答案：

假设我有一个有向图的邻接矩阵：

0 0 1 0

0 0 1 1

1 1 0 1

0 1 1 0

我被告知等效的邻接列表如下，并假设我的老师故意以这种方式列出它，而不是一些任意的重新排序 - 特别是如最后一个列表所示：

{ 2 }

{ 2, 3 }

{ 0, 1, 3 }

{ 2, 1 }

最后一个列表是 { 2, 1 }！等效邻接矩阵中的什么提醒我它应该是 { 2, 1 } 而不是 { 1, 2 }？

我有一个 Edge 类，它存储：源（顶点）、目标（顶点）和权重。

我有一个 Vertex 类，它存储：名称、x 坐标、y 坐标和 Ed​​ge[] 相邻列表。

我还有一个 Graph 类，它存储两个 ArrayList：边和顶点。

当前，当绘制顶点/节点和边时，它会分别自动添加到顶点和边列表中。

现在我想使用这两个数组列表填充 Edge[] 相邻列表，但我不知道该怎么做。如果有人能给我指点或概述代码的外观，我将不胜感激。

谢谢你。

注意：我已经根据Keith Randall和Chiyou的有用反馈编辑了这个问题。

我有一个想法，使用 1D 数组在特定处理上下文中缓存最常用的 2D NxM 矩阵条目。问题是，是否已经有大量的工作可以从中获得洞察力，或者是否只有知道的人。我将首先概述腿部工作，然后再提出问题。作为补充说明，Chiyou已经提出了空间填充曲线，它在概念上看起来是我所追求的东西，但不会轻易回答我的具体问题（即我找不到可以做我所追求的曲线） .

腿部工作： 目前最常用的条目被定义为循环和特殊的组合pointer_array（见下面的代码），它们组合产生最常用矩阵元素的索引。pointer_array 包含范围 [0, max(N, M)]中的数字（参见上面定义为 NxM 的矩阵维度）。

代码的目的是产生一个合适的（在程序的上下文中）索引组合来处理一些矩阵条目。有可能N = M，即方阵。遍历矩阵的代码 (C++) 如下所示

一些值得单独注意的事情：

1. 为了使这种缓存有价值，我认为它应该是密集的。也就是说，可以随机访问并在内存中连续布局的东西。即没有空间“浪费”（除非有许多单独的块）并且复杂性在 O(1) 中。这意味着缓存不能是与 1D 行/​​列主要有序数组完全排序的相同 2D 矩阵。我觉得它应该适合长度为max(N, M)的数组（参见上面的矩阵维度定义）。

2. some_matrix在循环期间将忽略其中的许多条目。

3. pointer_array 排序记录了通过矩阵的路线，因此它也用于其他地方。

4. 我在各种场合都遇到过这种需求，但这次我编写了一个2-opt算法，我正在寻求改进它的内存访问模式。我知道还有其他方法可以编写算法（但请参阅我遇到的其他设置，现在想知道是否有通用解决方案）。

5. 跳出框框的想法是产生一种类似的索引组合，在概念上类似于访问 2D 矩阵，但更智能。一种选择是在循环期间缓存矩阵行/列。

6. 由于条目将被大量使用，因此pointer_array通过缓存 some_matrix 调用来替换间接会更理想，这样获取entry*循环中的值会更快，即从预加载的缓存而不是可能相当大的矩阵。这里的另一点是它会节省存储空间，这反过来意味着经常使用的值可以很好地适应更快的缓存。

问题：是否可以设计一种索引方案，使矩阵索引本质上变成

或者也许像下面这样的东西也可以