问题标签 [adjacency-matrix]

我有一个 800 x 600 的图像。我想把它当作一个矩阵来获取相邻的元素

前任。

(0,0) (1,0) (2,0) (3,0)

(0,1) (1,1) (2,1) (3,1)

(0,2) (1,2) (2,2) (3,2)

(0,3) (1,3) (2,3) (3,3)

示例解决方案： (0,0) 与： (1,0) (0,1) (1,1) 相邻

(1,1) 与： (0,0) (1,0) (2,0) (2,1) (2,2) (1,2) (0,2) (0,1) 相邻

所以我写了一个结构数组，我会将这些点中的每一个存储到

所以我的第一个想法是实施一个 dfs，但这并没有真正奏效，所以我想获得外部意见，以使自己保持在正确的轨道上。谢谢

我的任务是从相邻节点列表中创建图形的邻接矩阵，存储在文件中（不需要权重）到 C++ 中的位集数组中。我成功地从文件中读取了相邻节点，但是当我尝试将其存储在 bitset 数组中时，结果不正确。我的功能如下：

结果如下（fi 代表第一个索引，si 代表第二个索引）：

sample.gr
fi: 0 si: 1
fi: 0 si: 2
fi: 1 si: 3
fi: 2 si: 4
fi: 3 si: 2
fi: 3 si: 5
fi: 4 si: 1
fi: 4 si: 5
fi: 4 si: 5

000000
000001
011000
001000
000000
000000

索引是正确的，我已经检查过了，但是矩阵应该如下（由于 bitset 的右侧定位而被镜像）：

000000
010001
001001
000010
000100
011000

我猜这个错误是在 bitset 元素访问周围的某个地方，但我无法找出究竟是什么错误。

我很感激任何帮助。谢谢。

在我的项目中，我正在尝试为图形构建邻接矩阵，并且出于空间和时间的考虑，我们应该使用稀疏矩阵，据我了解，使用哈希图最容易做到这一点。不幸的是，我们还必须实现一个邻接列表，我用所说的 hashmap 实现了它，并且由于我们的邻接矩阵在结构上必须不同，所以我不能对矩阵使用 hashmap。还有其他实现方式吗？

我为我的一个项目构建了一个邻接矩阵，我需要能够从该矩阵中构建一个最小生成树。通过阅读，Prim 的算法似乎最适合这种情况，但是我们不能假设该图是一个大的连接组件，因为我知道我们必须处理的至少一个图有大约几千个连接的组件。Prim 的算法在这里仍然可行吗？如果可行，我还需要做些什么吗？

我在这里用Java编码，我可以很好地构造邻接矩阵，只是我卡在这部分。

我正在尝试在 C 中实现一些图形算法，使用邻接矩阵作为支持数据结构。我需要实现一个加权图，权重由实数表示。

鉴于 0 和负数将是边缘的正确权重，我如何表示两个节点之间没有边缘？

我正在为我正在参加的算法课程编写一个小型图形库。

我已经实现了初始化图形、添加边、添加顶点等基本操作。

现在我应该实现顶点删除。起初它看起来很简单，但是当图形由邻接矩阵表示时，我找不到一个好的方法。

我的想法是有一个数组表示矩阵中的活动顶点并定期调整数组和矩阵的大小，所以我编写了这个示例程序：

这是个好主意吗？否则我还能做什么？谢谢

我想将下图放入邻接矩阵：

左图是一个 8 节点网络的节点链路表示。右边是同一网络的邻接矩阵表示。灰色单元的数量等于图中链接的数量。

所以我想制作一个静态分配的邻接矩阵。什么是最好的方法C language？

我在想类似的事情：

如果节点连接到其他节点，则分配 1，否则分配 0。我还想为节点拥有的邻居数量保留一个计数器，比如 A 有 2 个，B 有 3 个......

但是这一切我想要是静态的而不是动态的。

我的 Dijkstra 算法可以很好地找到路径。现在我想回去展示我走的路。我标记了一个访问过的顶点，并给它一个指向我来自“prev”的顶点的指针。不幸的是，当在 while 循环中循环时，这些指针会以某种方式被操纵，因此最后的顶点不知道它们来自哪里。你能帮助我吗？

可能这是我没有得到的指针问题。我有一个复制构造函数和一个 = 运算符。

我有一个 MySQL 表pedigree，将我所有的互连亲子数据存储为 2 个邻接列表：

谱系表

• 任何org_id人都可能有孩子，也可能没有孩子。儿童人数不限。
• org_id表中的每个pedigree都需要至少有一个 dam_id 或一个sire_id
• 如果一个org_id没有父母，它不会在血统表中列出，除非是父亲或母亲
• 一个org_id可能有dam_id==sire_id

样本数据

我想使用 R 的igraph包（除非有更合适的东西）来显示我的谱系的有向 DAG，其中祖先节点出现在子节点之上。我不清楚 igraph 到底需要做什么。我想我需要从我的邻接列表中生成一个邻接矩阵，但我不知道如何有效地做到这一点。

想法？

I'm preparing for a coding interview, and was refreshing my mind on graphs. I was wondering the following : in all places I've seen, it is assumed that adjacency lists are more memory efficient than adjacency matrices for large sparse graphs, and should thus be preferred in that case. In addition, computing the number of outgoing edges from a node requires O(N) in a matrix while it's O(1) in a list, as well as which are the adjacent nodes in O(num adjacent nodes) for the list instead of O(N) for the matrix.
Such places include Cormen et al.'s book, or StackOverFlow : Size of a graph using adjacency list versus adjacency matrix? or Wikipedia.

However, using a sparse matrix representation like with Compressed Row Storage representation, the memory requirement is just in O(number of non-zeros) = O(number of edges), which is the same as using lists. The number of outgoing edges from a node is O(1) (it is directly stored in CRS), and the adjacent nodes can be listed in O(num adjacent nodes).
Why isn't it discussed ? Should I assume that CSR is a kind of adjacency list representation of the graph represented by the matrix ? Or is the argument that matrices are memory intensive flawed because they don't consider sparse matrix representations ?

Thanks!