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. OK, I Understand
Top