SHARE
TWEET

BFS V1.1

Infernale Oct 26th, 2019 146 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 BFS(graph, start, target, parent)
  15.     visited = zeros(1, nodes);
  16.     queue = list();
  17.     queue($+1) = start;
  18.     visited(1, start) = 1;
  19.     while(size(queue) ~= 0)
  20.         node = queue(1);
  21.         if node == target
  22.             disp("Path found!")
  23.             backtrack(parent, node, target);
  24.             return;
  25.         end
  26.         //mprintf("%d ", node);
  27.         queue(1) = null();
  28.         for i=1:nodes
  29.             if graph(node, i) == 1 & visited(1, i) == 0 then
  30.                parent(1, i) = node;
  31.                queue($+1) = i;
  32.                visited(1, i) = 1;
  33.             end
  34.         end
  35.     end
  36. endfunction
  37.  
  38. function [from, to]=split(data)
  39.     splitted = evstr(strsplit(data, " "));
  40.     from = splitted(1, 1);
  41.     to = splitted(2, 1);
  42. endfunction
  43.  
  44. nodes = input("How many nodes ? ");
  45. graph = zeros(nodes, nodes);
  46. edges = input("How many edges ? ");
  47. disp("Enter " + string(edges) + " edges (from-to) separated by a white space:");
  48. for i=1:edges
  49.     in = input("", "string");
  50.     [from, to] = split(in);
  51.     graph(from, to) = 1;
  52.     graph(to, from) = 1;  
  53. end
  54.    
  55. startNode = input("Enter initial node : ");
  56. targetNode = input("Enter target node : ");
  57.  
  58. parent = zeros(1, nodes);
  59. parent(1, startNode) = -1;
  60.  
  61. BFS(graph, 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