How to calculate the space complexity of the given code

Question

I have written the code for checking whether a path exists between 2 vertices of a undirected, connected graph or not. I have stored my graph in an adjacency matrix. I am mentioning only my function and main function here. I have used BFS approach to solve the problem.

public static boolean hasPath1(int[][] adjMatrix, int v1, int v2, boolean visited[])
{
    int n = adjMatrix.length;
    if (v1 >= n || v2 >= n) 
    {
        return false;
    }

    if (adjMatrix[v1][v2] == 1) 
    {
        return true;
    }
    Queue<Integer> queue = new LinkedList<>();

    queue.add(v1);

    visited[v1] = true;

    while(queue.size()!=0)
    {
        int vertex = queue.poll();

        if(adjMatrix[vertex][v2]==1)
        {
            return true;
        }

        for(int i=0;i<n;i++)
        {
            if(adjMatrix[vertex][i]==1 && !visited[i])
            {
                queue.add(i);
                visited[i] = true;
            }
        }
    }

    return false;
}
    public static void main(String[] args) throws NumberFormatException, IOException 
{
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int e = sc.nextInt();

    int[][] adjMatrix = new int[n][n];

    for(int i=0;i<e;i++)
    {
        int v1= sc.nextInt();
        int v2 =sc.nextInt();

        adjMatrix[v1][v2] = 1;
        adjMatrix[v2][v1] = 1;
    }

    int vertex1 = sc.nextInt();
    int vertex2 = sc.nextInt();
    
    boolean visited[] = new boolean[n];
    boolean bool1 = hasPath1(adjMatrix,vertex1,vertex2,visited);
    System.out.println(bool1);
}

I am confused whether the space complexity should be O(v) or O(v^2). In my opinion the space complexity should be O(v) as we are only making a queue inside our function but in the solution it is mentioned as O(v^2).

Answer 1

Auxiliary Space: The extra space that is taken by an algorithm temporarily to finish its work

Space Complexity: Space complexity is the total space taken by the algorithm with respect to the input size plus the auxiliary space that the algorithm uses.

Quoted from here

i.e., space complexity also includes the space used by the input values as well.

Space Complexity = Auxiliary space + Space used up by input values

Representing graph using adjacency matrix itself takes O(V^2) - this is the input fed to the BFS algorithm in this case.

So the total space complexity of the given code will be O(V^2).

However, if asked for the space complexity of the BFS implementation alone, it will be O(V) - as the queue can hold all the vertices in worst case. When computing the space for only BFS, the representation of the graph i.e. adjacency list or matrix is disregarded.