I have an adjacency matrix and try to make some calculations between nodes. How can I assign adjacency matrix values to the LinkedList in a loop? How should I assign nodes (is it the same assigning ArrayList or should I keep attention the queue)?
for(int i=0; i<k; k++){
for(int j=0; j<l; l++){
//I need to iterate linkedlist here
}
}
You can try to use an array of a LinkedList
static class BreadthFirstPaths {
private static BreadthFirstPaths dfs;
private boolean[] marked;
private int[] edgeTo;
private int[] distTo;
public synchronized static boolean checkPaths(LinkedList<Integer>[] graph, int source, int dest, int vertex) {
if (dfs == null) {
dfs = new BreadthFirstPaths(graph, source);
}
Deque<Integer> pathTo = dfs.pathTo(dest);
return pathTo.contains(vertex);
}
public BreadthFirstPaths(LinkedList<Integer>[] graph, int source) {
marked = new boolean[graph.length];
distTo = new int[graph.length];
edgeTo = new int[graph.length];
for (int v = 0; v < graph.length; v++) {
distTo[v] = Integer.MAX_VALUE;
}
bfs(graph, source);
}
private void bfs(LinkedList<Integer>[] graph, int source) {
ArrayDeque<Integer> q = new ArrayDeque<>();
distTo[source] = 0;
marked[source] = true;
q.add(source);
while (!q.isEmpty()) {
int v = q.poll();
for (int w : graph[v]) {
if (!marked[w]) {
edgeTo[w] = v;
distTo[w] = distTo[v] + 1;
marked[w] = true;
q.add(w);
}
}
}
}
public Deque<Integer> pathTo(int v) {
Deque<Integer> stack = new ArrayDeque<>();
int n;
for (n = v; distTo[n] != 0; n = edgeTo[n])
stack.add(n);
stack.add(n);
return stack;
}
public boolean hasPathTo(int v) {
return marked[v];
}
public int distTo(int v) {
return distTo[v];
}
}
, main function
public static void main(String[] args) {
int n = 5;
int m = 10;
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(matrix[i], -1);
}
matrix[0][0] = 1;
matrix[1][0] = 0;
matrix[1][1] = 2;
matrix[1][2] = 6;
matrix[2][0] = 1;
matrix[2][1] = 3;
matrix[2][2] = 4;
matrix[2][3] = 9;
matrix[3][0] = 2;
matrix[4][0] = 2;
matrix[4][1] = 5;
matrix[5][0] = 4;
matrix[6][0] = 1;
matrix[6][1] = 7;
matrix[6][2] = 8;
matrix[7][0] = 6;
matrix[8][0] = 6;
matrix[9][0] = 2;
LinkedList<Integer>[] graph = new LinkedList[m];
for (int i = 0; i < matrix.length; i++) {
graph[i] = new LinkedList<>();
for (int j = 0; j < n; j++) {
if (matrix[i][j] != -1)
graph[i].add(matrix[i][j]);
}
}
BreadthFirstPaths dfs = new BreadthFirstPaths(graph, 5);
Deque<Integer> stack = dfs.pathTo(7);
// System.out.println(stack.contains(3)); Another way to check if vertex in path from source 5 and dest 7
System.out.println(BreadthFirstPaths.checkPaths(graph, 5, 7, 2));
}
, output
7 6 1 2 4 5
true
Your adjacency matrix is n x n that means you have n vertices. So your length of adjacency list is n.
You just need to create an ArrayList of lists. You don't need a LinkedList. The LinkedList has a complexity of O(n) for its get operation which will be used quite often later after you build the adjacency list. For ArrayList it is O(1).
To build an adjacency list you need to do as below:
List<List<Integer>> adjList = new ArrayList<>();
for ( int i = 0; i < n; i++ ) //add a list to each vertex
adjList.add( new ArrayList<>() );
for ( int i = 0; i < n; i++ ) {
for ( int j = 0; j < n; j++ ) {
if (adj_matrix[i][j] == 1 ) { //if the value is 1 then only an edge exists.
adjList.get(i).add(j);
}
}
}
