DFS algorithm recursion and function stack

Hi everyone, I'm currently trying to implement the DFS (Depth First Search) Algorithm to in fine find if there is a cycle in my graph. This is my code

function [ val ] = dfs(colonne,matrice_adjacence,marque,wanted,stop)

    fils = [ find(matrice_adjacence(:,colonne))' find(matrice_adjacence(colonne,:)) ];
pere = (fils==colonne);

 for i = 1:length(fils)
    if(pere(i))
        fils(i) = 0;
    end
 end

    for i = fils 
        marque = [marque colonne];
        presence=sum(ismember(marque,i));
        if(presence==0 && stop==0)

            dfs(i,matrice_adjacence,marque,wanted,stop);
        else
            stop=1;
        end
    end

To do that I store the number of every vertex I encounter along the path and if it happens that it's already in there i want to stop the program. But I ve noticed during the return that the variable where I store my vertex IDs changes! And I don't know why.. Can someone please explain me what am i doing wrong?

Answer 1

[Jaynik]

Hi @Nolaan Nolaan,

The issue encountered is likely due to the marque and stop variables. In MATLAB, variables are passed by value and not by reference. This means that any modification to the variables within the recursive calls of dfs does not affect its value in the calling function unless explicitly returned.

You can modify the function as follows to return the correct output:

function [stop] = dfs(node, matrice_adjacence, marque, stop)
    marque = [marque, node];
    fils = find(matrice_adjacence(node, :));
    
    for i = fils
        if stop == 1
            return;
        end
        
        if ~ismember(i, marque)
            % Recursive call with the updated path
            stop = dfs(i, matrice_adjacence, marque, stop);
        else
            stop = 1;
            return;
        end
    end
end

The main differences between the original code and the modified code are:

• The fils array could include zeros, which might cause issues during iteration. Modified code only considers outgoing edges from the current node (node), which simplifies the logic and avoids unnecessary checks.
• The path is updated before entering the loop, ensuring that each recursive call correctly tracks the path.
• We directly check the membership and update stop correctly and return immediately when a cycle is detected, which ensures that the cycle detection is propagated back through the recursive calls.

Hope this helps!