Depth-first search that starts from the right side of the loop
3 views (last 30 days)
Show older comments
Dear all,
Currently, I have a function that list all the branch from level to level in the leftest side. I want to list all the branch in the rightest side but not sure how to list them.
My code is as follow:
adj=SparseGraph;
next = cell(n,1);
for i = 1:n
next{i} = find(adj(i,:));
end
Thank you for your time,
Original output is
[2,3,4,5,6,7,8]
[9,10]
[9,10,11]
[10,11,12]
[11,12,13]
[12,13,14]
[13,14,15]
[14,15]
Desire output is
[8,7,6,5,4,3,2]
[15,14]
[15,14,13]
[14,13,12]
[13,12,11]
[12,11,10]
[11,10,9]
[10,9]
Answers (1)
Prabhan Purwar
on 7 Aug 2019
Hello,
Please refer to the following pseudo-code for generating the desired output,
Initialization: Create a global flag array visited to mark visited values of the nodes with status as 0,1 and 2 for unvisited, global queue and fully visited respectively.
n= 1;
for i=1:8 (Iteration till 8th node in order)
arr=find (adj (n ,: ));
% Push every value of array arr into a stack and make use of an array to print output while popping
% Start popping and pushing of nodes in queue, while pushing check for visited nodes (Status 1).
n= deque(queue);
end
Pseudo run:
Step 0: Initialization of visited with 1 for index 1 and other 0, empty queue and empty stack.
n=1;
Status after 1st iteration
: visited [1 1 1 1 1 1 1] for index 1, 8, 7, 6, 5, 4, 3, 2 others are 0
: stack [8 7 6 5 4 3 2]
: queue [8 7 6 5 4 3 2] (in order of popping the nodes from stack)
: stack empty
: out [8 7 6 5 4 3 2]
8 dequeued
Status after 2nd iteration
: visited [1 2 1 1 1 1 1 1 1 1] for index 1, 8, 7, 6, 5, 4, 3, 2, 15, 14 (now 8 will not be counted in stack occurrence, thus marked with 2)
n= 8;
:stack = [15 14];
: queue [7 6 5 4 3 2 15 14] (enqueue 15 and 14 in same order as pooping from stack)
: stack empty
: out [15 14]
7 dequeued
And keep on running the code till desired no of nodes is reached.
0 Comments
See Also
Categories
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!