• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# DFS V1.1 Infernale  Oct 26th, 2019 (edited) 140 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. global nodes;
2.
3. function backtrack(parent, start, target)
4.     path = list();
5.     path(\$+1) = target;
6.     while parent(1, path(\$)) ~= -1
7.         path(\$+1) = parent(1, path(\$));
8.     end
9.     for i=size(path):-1:1
10.         mprintf("%d ", path(i));
11.     end
12. endfunction
13.
14. function DFS(graph, visited, start, target, parent)
15.     visited(1, start) = 1;
16.     //mprintf("%d ", start);
17.     if start == target then
18.         disp("Path found!")
19.         backtrack(parent, start, target);
20.         return;
21.     end
22.     for i=1:nodes
23.         if graph(start, i) == 1 & visited(1, i) == 0 then
24.             parent(1, i) = start;
25.             DFS(graph, visited, i, target, parent);
26.         end
27.     end
28. endfunction
29.
30. function [from, to]=split(data)
31.     splitted = evstr(strsplit(data, " "));
32.     from = splitted(1, 1);
33.     to = splitted(2, 1);
34. endfunction
35.
36. disp("Note : Please enter nodes by number (from 1 to n)");
37.
38. nodes = input("How many nodes ? ");
39. graph = zeros(nodes, nodes);
40. edges = input("How many edges ? ");
41. disp("Enter " + string(edges) + " edges (from-to) separated by a white space:");
42. for i=1:edges
43.     in = input("", "string");
44.     [from, to] = split(in);
45.     graph(from, to) = 1;
46.     graph(to, from) = 1;
47. end
48.
49. startNode = input("Enter initial node : ");
50. targetNode = input("Enter target node : ");
51.
52. parent = zeros(1, nodes);
53. parent(1, startNode) = -1;
54.
55. visited = zeros(1, nodes);
56. DFS(graph, visited, startNode, targetNode, parent);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top