I tried the following but I'm not sure that it is correct.
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;
}
The array a is an adjacency matrix and the parameter v is the vertex of an undirected graph. If there is an edge between vertex v and j then we add the edge incident to vertex v.
CodePudding user response:
Method 1: Query Adjacency Matrix
Since you have already stored the edges in an adjacency matrix, you can simply query it. Set your i
to v (since you are not even using i
in the first place), and then check all vertices that are connected.
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;
}
Method 2: Generating an Adjacency List
If you get control of the input (i.e. before making the adjacency matrix), what you want is an adjacency list: Where each list[start]
points to an ArrayList<Integer>
(representing the connected vertices). I would avoid the use of ArrayList
since the number of vertices is already known. So I would instead use ArrayList<Integer>[] list
instead. This definitely makes it easier to code.
Here is an example of generating the adjacency list from an adjacency matrix
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];
}