0

如何将稀疏矩阵划分为最少数量的连接组件,以便每个组件在整个组件中都有一个共同的行或列。我应该使用什么数据结构在最短的时间内完成这项任务。我认为这样做我必须最大化每个组件中的元素数量,因此在获取输入时我存储了每行和每列中的元素数量。我对列表进行排序,然后使用 max(min(行中的元素,列中的元素)) 对行或列进行排序,即

   row 5-1   column 4-2
   row 4-1   column 3-2
   row 3-2   column 2-3
   row 2-2   column 1-3
   row 1-10

对于矩阵:

 x
 x
x x
x  x
xxxxxxxxxx 

(x代表非零位置)(这个矩阵的最终输出应该是4)

左下角是 1,1

然后我将首先删除第 1 列。然后我将不得不更新占用大量时间的剩余数组,并且为每行和每列存储列表也不可行,因为它使用大量内存。我只需要告诉最小分区数,而不是实际对矩阵进行分区。在给定的矩阵中,可以通过将 (row1,row2,row3,colum2-(1,2)) 作为分区来对其进行分区。

编辑:或者等效地,我们可以将其视为一组元素,该元素具有与它们相关联的两个数字,并且我们输出了最小数量的分区,使得每个分区都具有两个数字中的一个。

4

1 回答 1

0

我相信您会发现这些讲座幻灯片相关:http ://www.cs.indiana.edu/classes/b673/notes/GraphPartitioning.pdf

于 2013-10-04T18:39:02.293 回答