DFS 算法超出内存限制

Question

我实现了这段代码。

但不幸的是变成了“超时”。

从第一个A[0][0]到最后一个A[n][n]二维数组求路径的算法

我使用了“DFS”算法。

import javax.jnlp.IntegrationService;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class prj{
static boolean[] dfs(byte[][]A,boolean[]v,int num,int start){
    v[start]=true;
    if(start==num-1){
        return v;
    }
    for (int i = 0; i < num; i++) {
        if (A[start][i]==1&&v[i]==false){
            dfs(A,v,num,i);
        }
    }
    return v;
}
public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int n=scanner.nextInt();
    int m=scanner.nextInt();
    byte[][] A=new byte[n][n];
    for (int i = 0; i <m ; i++) {
        int v=scanner.nextInt();
        int u=scanner.nextInt();
        A[v-1][u-1]=1;
    }
   
    boolean visited[]=new boolean[n];
    
    if(A[0][n-1]==1){
        System.out.println("YES");
    }else {
        visited = dfs(A, visited, n, 0);
        boolean b = true;
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                System.out.println("NO Path");
                b = false;
                break;
            }
        }
        if (b == true) {
            System.out.println("YES ,Path  exists ");
        }
     }
  }
}

Answer 1

你要弄清楚n和m的边界是什么
但是我猜想在这个问题中 m 会比 n * n 小得多。
如果是这种情况，您可以定义一个包含 m 个元素的散列 table，而不是创建 n * n 数组，每个元素都有一对 (v, u) 作为键，“是否访问过”作为布尔值.

Map<Pair<Integer, Integer>, Boolean> nodes = new Hashtable<>();
for (int i = 0; i <m ; i++) {
    int v=scanner.nextInt();
    int u=scanner.nextInt();
    nodes.put(new Pair(v, u), false);
}

因为在散列中读写table具有恒定的时间复杂度，它与定义一个n * n数组的时间复杂度没有区别，但内存效率更高。

DFS 算法超出内存限制

Memory limit exceeded in DFS algorithm

algorithm

graph-algorithm

depth-first-search

recursive-backtracking