如何找到入射到特定顶点的边列表

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

方法一：查询邻接矩阵

由于您已经将边存储在邻接矩阵中，因此您可以简单地对其进行查询。将 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：生成邻接表

如果你控制了输入（即在制作邻接矩阵之前），你想要的是一个 adjacency list：其中每个 list[start] 指向一个 ArrayList<Integer>（代表连接的顶点）。我会避免使用 ArrayList 因为顶点的数量是已知的。所以我会改用 ArrayList<Integer>[] 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];
}

如何找到入射到特定顶点的边列表

How to find the list of edges incident to a particular vertex

java

algorithm

graph-theory

depth-first-search

adjacency-matrix

方法一：查询邻接矩阵

方法 2：生成邻接表