global nodes;

function backtrack(parent, start, target)
    path = list();
    path($+1) = target;
    while parent(1, path($)) ~= -1
        path($+1) = parent(1, path($));
    end
    for i=size(path):-1:1
        mprintf("%d ", path(i));
    end
endfunction

function BFS(graph, start, target, parent)
    visited = zeros(1, nodes);
    queue = list();
    queue($+1) = start;
    visited(1, start) = 1;
    while(size(queue) ~= 0)
        node = queue(1);
        if node == target
            disp("Path found!")
            backtrack(parent, node, target);
            return;
        end
        //mprintf("%d ", node);
        queue(1) = null();
        for i=1:nodes
            if graph(node, i) == 1 & visited(1, i) == 0 then
               parent(1, i) = node;
               queue($+1) = i;
               visited(1, i) = 1; 
            end
        end
    end
endfunction

function [from, to]=split(data)
    splitted = evstr(strsplit(data, " "));
    from = splitted(1, 1);
    to = splitted(2, 1);
endfunction
 
nodes = input("How many nodes ? ");
graph = zeros(nodes, nodes);
edges = input("How many edges ? ");
disp("Enter " + string(edges) + " edges (from-to) separated by a white space:");
for i=1:edges
    in = input("", "string");
    [from, to] = split(in);
    graph(from, to) = 1;
    graph(to, from) = 1;  
end
   
startNode = input("Enter initial node : ");
targetNode = input("Enter target node : ");

parent = zeros(1, nodes);
parent(1, startNode) = -1;

BFS(graph, startNode, targetNode, parent);