Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 DFS(graph, visited, start, target, parent)
- visited(1, start) = 1;
- //mprintf("%d ", start);
- if start == target then
- disp("Path found!")
- backtrack(parent, start, target);
- return;
- end
- for i=1:nodes
- if graph(start, i) == 1 & visited(1, i) == 0 then
- parent(1, i) = start;
- DFS(graph, visited, i, target, parent);
- end
- end
- endfunction
- function [from, to]=split(data)
- splitted = evstr(strsplit(data, " "));
- from = splitted(1, 1);
- to = splitted(2, 1);
- endfunction
- disp("Note : Please enter nodes by number (from 1 to n)");
- 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;
- visited = zeros(1, nodes);
- DFS(graph, visited, startNode, targetNode, parent);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement