0

我正在解决一个图形问题。它是一个无向图。假设有 4 个顶点 (1,2,3,4)，顶点链接如下。

1,2
1,3
1,4
2,1
3,1
4,1

G(i,j) 和 G(j,i) 都存在如上（G-图，i-源顶点，j-目的顶点）。现在，我需要从中删除所有 G(j,i)。这可能是有效的方式。

我尝试将所有 i 顶点插入一个数组，将 j 顶点插入另一个数组。就像是

a[0] = 1 and b[0] = 2
a[1] = 1 and b[1] = 3
so on..

但是我很难删除 G(j,i) 条目。我有 3 个问题。

  1. 是否有任何有效的算法可以删除重复项（这里重复我说，bcoz G(i,j) = G(j,i).

  2. 除了使用数组之外，是否有任何数据结构可以更轻松地执行此操作。

  3. 哪种数据结构通常用于图问题。

4

1 回答 1

1

图通常以邻接矩阵形式或邻接列表表示。

设 n = 节点数，m = 边数，节点 ID 是标记为 0 - (n-1) 的整数

在邻接矩阵中，您基本上有一个大小为 nx n 的二维数组。如果节点和[i][j] 之间没有边，则index 处的值为 0 ，否则为非零。如果您的图未加权，则矩阵通常是二进制的（0 表示无边，1 表示有边），您可以使用布尔值矩阵来节省空间。如果您的图是无向图，请注意矩阵将是对称的，因为在 处的边表示在 处的边。ij[i][j][j][i]

但是，如果空间效率是一个问题，并且您的图形在边方面是稀疏的，那么将有大量空间浪费，因为无论边数如何，数据结构都将占用 O(n^2)。

另一种方法是邻接表，它占用 O(n + m) 空间。这里我们可以有一个一维数组，其中数组的每个元素都是一个容器（比如链表或哈希集）。数组的第ith 个容器保存连接到该ith节点的节点的 ID。

为了解决以您拥有的“edgelist”格式删除重复项的问题，您似乎需要一个无向图，这意味着从 to 的边意味着从to的i边。在邻接矩阵中，这可以简单地通过设置来完成。在邻接列表中，最好使用容器来保证没有重复的边缘。因此，当您在边缘列表中看到从to的边缘时，您只需索引到第th 单元格并添加 in ，然后索引到第th 单元格并添加 in 。稍后当您看到to时，您将执行相同的操作，但将重复值添加到哈希集中将无济于事。jji[i][j] = [j][i] = truesetsetijijjiji

于 2013-02-22T07:12:29.310 回答