将邻接矩阵转换为链表

Question

>我有一个邻接矩阵，并尝试在节点之间进行一些计算。如何在循环中将邻接矩阵值分配给链表？我应该如何分配节点(是相同的分配 ArrayList 还是应该注意队列(？

for(int i=0; i<k; k++){
for(int j=0; j<l; l++){
//I need to iterate linkedlist here
}
}

Answer 1

您可以尝试使用链接列表的数组

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功能

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

输出

7 6 1 2 4 5
true

Answer 2

您的邻接矩阵n x n这意味着您有n顶点。所以你的邻接列表长度是n.

您只需要创建列表ArrayList。你不需要LinkedList.该LinkedList的get操作具有O(n)的复杂性，在构建邻接列表后将经常使用。对于ArrayList来说，这是O(1).

要构建邻接列表，您需要执行以下操作：

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