如何找到事件的边缘列表到特定顶点

Question

我尝试了以下内容，但我不确定它是否正确。

ArrayList<ArrayList<Integer>> list = new ArrayList<>();
public static ArrayList<ArrayList<Integer>> incidentEdges(int v) {
   for(int i = 0; i < a.length; i++) {
      for(int j = 0; j < a[i].length; j++) {
         if(a[v][j] == 1) {
            list.get(v).get(new Edge(start, destination));
            list.get(j).get(new Edge(start, destination);
         }
      }
   }
   return list;
}

阵列 a 是邻接矩阵，参数 v 是无向图的顶点。如果顶点 v 和 j 之间有边缘，则我们将边缘入射添加到顶点 v 。

Answer 1

方法1：查询邻接矩阵，

由于您已经将边缘存储在邻接矩阵中，因此您可以简单地查询它。将您的i设置为V（因为您甚至首先都不使用i），然后检查所有连接的顶点。

public static ArrayList<Integer> incidentEdges(int v) {
   ArrayList<Integer> result = new ArrayList<>();
   for(int i = 0; i < a[v].length; i++) {
     if(a[v][i] == 1) {
        result.add(a[v].get(i));
     }
   }
   return result;
}

方法2：生成邻接列表

，如果您可以控制输入（即制作邻接矩阵之前），则想要的是相邻列表：其中每个list [start]指向arraylist＆lt; integer＆gt;（表示连接的角度）。我会避免使用arrayList，因为顶点的数量已经知道。因此，我将使用arrayList＆lt; integer＆gt; [] list。这绝对可以使编码更容易。

这是从邻接矩阵生成邻接列表的示例

static ArrayList<Integer>[] list;

public static ArrayList<Integer>[] generateAl(int v) {
   list = new ArrayList[a.length];
   for(int i = 0; i < a.length; i++) {
      list[i] = new ArrayList<>();
      for(int j = 0; j < a[i].length; j++) {
         if(a[i][j] == 1) {
            list[i].add(j);
         }
      }
   }
   return list;
}

public static ArrayList<Integer> incidentEdges(int v) {
   return list[v];
}