用HashMap [Int，Vector [Int]]（Scala）表示图形（邻接列表）？ [英] Representing a graph (adjacency list) with HashMap[Int, Vector[Int]] (Scala)?

问题描述

我想知道如何（如果可能）通过 HashMap [Int，Vector [Int]] 来制作（可变）图的邻接表表示。 HashMap 当然是可变的。

目前我将它设置为 HashMap [Int ，ArrayBuffer [Int]] ，但是我可以更改ArrayBuffer中每个单元格的事实让我感到不舒服，即使我确信我没有这样做。我会使用一个 ListBuffer [Int] ，但我想快速随机访问邻居，因为我需要在图上进行快速随机漫步。一个 Vector [Int] 可以解决这个问题，但是无论如何要做到这一点？

据我所知尝试这在REPL中），这是行不通的：

  scala> val x = new mutable.HashMap [Int，Vector [Int]] 
 x：scala.collection.mutable.HashMap [Int，Vector [Int]] = Map（）
 
 scala> x（3）=向量（1）
 
 scala> x（3）+ = 4 //不工作
  

我需要能够追加到它在任何时候也随机访问其中的任何元素（给定索引）。这可能吗？

谢谢！
-kstruct

解决方案

使用向量：

  x + = 3  - > （x（3）：+ 4）//x.type = Map（3-> Vector（1,4））
  

您可能会注意到，如果没有现有的按键，这会失败，因此您可能希望将地图设置为

  val x = new mutable.HashMap [Int，Vector [Int]] withDefaultValue Vector.empty 
  

I was wondering how (if possible) I can go about making an adjacency list representation of a (mutable) graph via HashMap[Int, Vector[Int]]. HashMap would be mutable of course.

Currently I have it set as HashMap[Int, ArrayBuffer[Int]], but the fact that I can change each cell in the ArrayBuffer makes me uncomfortable, even though I'm fairly certain I'm not doing that. I would use a ListBuffer[Int] but I would like fast random access to neighbors due to my need to do fast random walks on the graphs. A Vector[Int] would solve this problem, but is there anyway to do this?

To my knowledge (tried this in the REPL), this won't work:

scala> val x = new mutable.HashMap[Int, Vector[Int]]
x: scala.collection.mutable.HashMap[Int,Vector[Int]] = Map()

scala> x(3) = Vector(1)

scala> x(3) += 4 // DOES NOT WORK

I need to be able to both append to it at any time and also access any element within it randomly (given the index). Is this possible?

Thanks! -kstruct

解决方案

Using the Vector:

x += 3 -> (x(3) :+ 4)  //x.type = Map(3 -> Vector(1, 4))

You might notice that this will fail if there's no existing key, so you might like to set up your map as

val x = new mutable.HashMap[Int, Vector[Int]] withDefaultValue Vector.empty

这篇关于用HashMap [Int，Vector [Int]]（Scala）表示图形（邻接列表）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！