Java 中的邻接列表

Question

我有邻接关系 table。见上：

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个点，是邻居。我想像这样列出每个点的所有邻居。但是我也得到了假邻接，我在上面的列表中得到了比 table.

中表示的更多的邻接

    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;
        }
    }
}

大小是顶点的个数，aList应该存储邻接关系。

Answer 1

我认为正确的方法是定义一个 class 点而不是使用原始整数：

 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; 
}

Java 中的邻接列表

Adjacency lists in Java

java

adjacency-list