1

我有一个大型稀疏图，我将其表示为邻接矩阵（100k x 100k 或更大），存储为边数组。具有（非稀疏）4 x 4 矩阵的示例：

0 7
4 0

example_array = [ [7,1,2], [4,2,1] ]

例如 [4,1,2] 表示从节点 1 到节点 2 有一条有向边，其值/权重为 4。在矩阵术语中，这本质上是 [值、行、列]。

此外，这个“边数组”将按第一个元素排序。在上面的例子中，经过排序，数组变成了，

example_array = [ [4,2,1], [7,1,2] ]

问题

对于某个值i，需要在这个排序的“边数组”中找到第二个值等于 的所有元素i。即找到j这样的example_array[j][1] = i。

我对此的初步实现是简单地迭代数组中的所有元素，将每个元素的第二个值与i. 这在计算上是昂贵的，因为可能仍然有很多（例如 500k）元素需要循环。

问题

有没有更有效的方法来做到这一点？我不介意使用矩阵/图形的不同表示。我正在用 C 写这个。

附加信息

这本质上是找到一个节点的所有邻居i，以及它们的边权重。即从边列表中查找i到另一个节点的所有有向边。

4

3 回答 3

1

为此，您可能应该使用稀疏压缩行存储。简而言之，您逐行存储矩阵，因此您不需要保留两个（行，列）索引。相反，您保留一个行指针，即一个数组，它告诉您给定行在内存中的起始位置。然后你保留列向量 (col_ind)，它告诉你非零列在该行中的位置，并存储相应的值 (val)。这减少了存储需求，但也加快了矩阵搜索，因为每一行的 col_ind 都是排序的。因此，您可以直接访问每个矩阵行，并且可以使用二分法或您选择的任何其他排序列表搜索快速定位每行中的条目。

CRS 矩阵可以通过插入排序列表来快速创建，例如，如果您已明确构造每个矩阵条目的 (i,j) 坐标，则可以使用桶排序。在 MATLAB 中，您可以使用“稀疏”函数来执行此操作。如果您不想自己编写代码并需要一个库，请查看Tim Davis 的 SuiteSparse。

有关 CRS 格式的简要说明，请查看此处，但还有数以千计的其他来源。

编辑您可以使用修改后的 CRS 存储轻松完成您需要的操作。首先，您需要通过按值而不是按列索引对每行中的列进行排序来创建矩阵，这通常是这样做的。这意味着每行的最小值存储为每行中的第一个条目。然后，为了找到全局最小值，您搜索所有行的第一个条目（O(n) 复杂度）。知道通过读取包含最小值的行中的第一列索引，您可以在恒定时间内获得相应的列索引。您可以做到所有这些，因为您可以通过行指针知道行在内存中的起始位置。

你可以看看这段代码。它是一组用 C 实现的 matlab 的 mex 文件。您感兴趣的是 sparse_create_mex.c。它通过将 (i, j, value) 迭代添加到排序列表中来创建稀疏矩阵结构。您需要稍微修改排序列表 - 现在它们是为整数列索引和双精度值实现的。由于排序列表是作为宏模板实现的，因此您只需要声明一个新的排序列表类型（参见 sorted_list.h 和 sorted_list_templates.h）。

于 2012-09-26T08:01:46.107 回答
0

如果您不介意更改表示，那么如果您按第二个元素排序，那么计算密集度会降低，因为这样您就可以逐步完成，一旦您发现一个大于 i 的元素，您就可以完成。在最坏的情况下，最好的算法是 O(n)，但如果你按第二个元素排序，那么预计这将在 n/2 时间内运行。

于 2012-09-25T22:14:35.140 回答
0

使用指针有什么问题？

// A list of edges emanating from one node.
typedef struct {
    int weight;    
    int nodeId;    // The target node
    Edge *next;    // Next edge in the list
} Edge;

typedef struct {
    int nodeId;
    Edge *edges;   // This node's edge list
} Node;

// Now just store all your nodes in an array
Node *example_array[MAX_NODES];

edges当你在一个节点上插入一条边时，你会按重量在它的列表上进行有序插入。现在，要回答有关查找从某个节点开始的所有边的问题，您只需在数组中查找该节点并遍历其边列表。好处是您可以按排序顺序访问其边缘，而无需搜索图表的任何其他部分。

于 2012-09-25T22:39:24.573 回答