Depth-first search that starts from the right side of the loop

1 次查看（过去 30 天）
Trung Ngo
Trung Ngo 2019-7-31
回答： Prabhan Purwar 2019-8-7
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]

请先登录，再回答此问题。

回答（1 个）

Prabhan Purwar
Prabhan Purwar 2019-8-7
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.

类别

在 Help Center 和 File Exchange 中查找有关 Matrix Indexing 的更多信息

标签

产品


版本

R2019a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by