1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
// CSparse/Source/cs_tdfs: depth-first search of a tree
// CSparse, Copyright (c) 2006-2022, Timothy A. Davis. All Rights Reserved.
// SPDX-License-Identifier: LGPL-2.1+
#include "cs.h"
/* depth-first search and postorder of a tree rooted at node j */
csi cs_tdfs (csi j, csi k, csi *head, const csi *next, csi *post, csi *stack)
{
csi i, p, top = 0 ;
if (!head || !next || !post || !stack) return (-1) ; /* check inputs */
stack [0] = j ; /* place j on the stack */
while (top >= 0) /* while (stack is not empty) */
{
p = stack [top] ; /* p = top of stack */
i = head [p] ; /* i = youngest child of p */
if (i == -1)
{
top-- ; /* p has no unordered children left */
post [k++] = p ; /* node p is the kth postordered node */
}
else
{
head [p] = next [i] ; /* remove i from children of p */
stack [++top] = i ; /* start dfs on child node i */
}
}
return (k) ;
}
|
