java - Java 中的邻接表

Question

已关闭。此问题需要 debugging details 。目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem 。这将有助于其他人回答问题。

已关闭 8 年前。

Improve this question

我有一个邻接表。见上文:

e1.p1.x     e1.p1.y     e1.p2.x     e1.p2.y
x1 46       y1 280      x2 346      y2 339
x1 331      y1 229      x2 46       y2 280
x1 1        y1 74       x2 207      y2 325
x1 388      y1 29       x2 1        y2 74
x1 237      y1 72       x2 46       y2 280
x1 346      y1 339      x2 331      y2 229
x1 46       y1 280      x2 331      y2 229
x1 207      y1 325      x2 101      y2 152
x1 132      y1 55       x2 46       y2 280
x1 101      y1 152      x2 1        y2 74
x1 331      y1 229      x2 346      y2 339
x1 346      y1 339      x2 101      y2 152
x1 101      y1 152      x2 132      y2 55
x1 346      y1 339      x2 1        y2 74
x1 237      y1 72       x2 132      y2 55
x1 331      y1 229      x2 207      y2 325

每行有 2 个点，它们是邻居。我想制作这样的列表，其中包含每个点的所有邻居。但我也得到了假邻接，我在上面的列表中得到了比表中表示的更多的邻接。

    Output:
    [207, 325, 0, 1, 74, 0, 101, 152, 0, 331, 229, 0]
    [331, 229, 0, 46, 280, 0, 346, 339, 0, 207, 325, 0]
    [46, 280, 0, 346, 339, 0, 331, 229, 0, 237, 72, 0, 132, 55, 0]
    [346, 339, 0, 46, 280, 0, 331, 229, 0, 101, 152, 0, 1, 74, 0]
    [101, 152, 0, 207, 325, 0, 1, 74, 0, 346, 339, 0, 132, 55, 0]
    [132, 55, 0, 46, 280, 0, 101, 152, 0, 237, 72, 0]
    [237, 72, 0, 46, 280, 0, 132, 55, 0]
    [1, 74, 0, 207, 325, 0, 388, 29, 0, 101, 152, 0, 346, 339, 0]
    [388, 29, 0, 1, 74, 0]

这是Java代码:

for (j = 0; j < size; j++) {
    ArrayList < Integer > aList = adjLists.get(j);
    for (Edge e: edges) {
        if ((points[j][0] == e.p1.x && points[j][1] == e.p1.y)) {
            aList.add(e.p1.x);
            aList.add(e.p1.y);
            aList.add(0);

            for (Edge e1: edges) {
                if (e1.p1.x == e.p1.x && e1.p1.y == e.p1.y && !aList.contains(e1.p2.x) && !aList.contains(e1.p2.y)) {
                    aList.add(e1.p2.x);
                    aList.add(e1.p2.y);
                    aList.add(0);

                }
            }
            break;
        }

        if ((points[j][0] == e.p2.x && points[j][1] == e.p2.y)) {

            aList.add(e.p2.x);
            aList.add(e.p2.y);
            aList.add(0);
            for (Edge e1: edges) {
                if (e1.p2.x == e.p1.x && e1.p2.y == e.p1.y && !aList.contains(e1.p1.x) && !aList.contains(e1.p1.y)) {
                    aList.add(e1.p1.x);
                    aList.add(e1.p1.y);
                    aList.add(0);
                }
            }
            break;
        }
    }
}

Size是顶点的数量，aList应该存储邻接关系。

Answer 1

我认为正确的方法是定义一个类 Point 而不是使用原始整数:

 class Point {
   private final int x;
   private final int y;
   Point(int x, int y) {this.x = x; this.y = y;}
   int getX() {return x;}
   int getY() {return y;}
 }

那么邻接表是:

Map<Point, Set<Point>> adjacencies;

然后要使用它，您只需编写即可；

for (/* rows */) {
  Point pt1 = new Point(x1, y1); // Extract from the table.
  Point pt2 = new Point(x2, y2); // Extract from the table.
  Set<Point> adjs = adjacencies.find(pt1);
  if (adjs == null) {
    adjs = new HashSet<Point>();
    adjacencies.put(pt1, adjs);
  }
  adjs.put(pt2);
  // Same for pt2
}

这样你就可以得到一个点的邻接关系，如下所示:

Set<Point> adjs = asjacencies.get(point);

比搜索数组数组并将每两个解析为一个点要容易得多。

如果其他模块需要数组数组形式的数据，您可以执行以下操作:

List<List<Integer>> toLists(Map<Set<Point>> adjacencies) {
  List<List<Integer>> result = new ArrayList<List<Integer>>();
  for (Point pt : adjacencies.getKeys()) {
    List<Integer> adjs = new ArrayList<Integer>();
    adjs.add(pt.getX());
    adjs.add(pt.getY());
    adjs.add(0);
    for (Point adjPt : adjacencies.get(pt)) {
      adjs.add(adjPt.getX());
      adjs.add(adjPt.getY());
      adjs.add(0);
    }
    result.add(adjs);
  }
  return result; 
}