• API
• FAQ
• Tools
• Archive
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.
Top