# Depth First Search in Mathematica

Published on 21 January 2023 (Updated: 21 January 2023)

Welcome to the Depth First Search in Mathematica page! Here, you'll find the source code for this program as well as a description of how the program works.

## Current Solution

``````(* Code *)

(* Depth-first search option depthFirstSearch1 is based on the built-in DepthFirstScan: *)

depthFirstSearch1 = Function[{ag, p, v},
Module[{found = False},
DepthFirstScan[
"PrevisitVertex" -> Function[{u}, If[u == v, found = True]]
];
found]];

(* If that is considered cheating, then option depthFirstSearch2 implements it directly: *)

depthFirstSearch2 = Function[{ag, p, v},
Module[{f},
f = Function[i,
p[[i]] == v \[Or] AnyTrue[
Select[Range[i, Length[ag]], Positive[ag][[i, #]] &],
f]];
f[1] (* start search at first node *) ]];

(* The outer function does the string parsing: *)

depthFirstSearchMain = Function[{am, vs, v},
Module[{e = "Usage: please provide a tree in an adjacency matrix form (\"0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, \
0\") together with a list of vertex values (\"1, 3, 5, 2, 4\") and the integer to find (\"4\")"},
Catch[
depthFirstSearch2 @@
Map[
(* convert string to integer, or throw *)
s \[Function] If[StringMatchQ[s, DigitCharacter ..],
FromDigits[s],
Throw[e]],
(* construct arguments to depth-first search *) {
If[Length[#] > 0, Partition[#, Sqrt[Length[#]]], Throw[e]] &[StringSplit[am, ", "]],
If[Length[#] > 0, #, Throw[e]] &[StringSplit[vs, ", "]],
If[StringLength[v] > 0, v, Throw[e]]},
{-1} (* at each leaf *)]]]];

(* Valid Tests *)

Print /@ Apply[depthFirstSearchMain] /@ {
{"0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0", "1, 3, 5, 2, 4", "1"},
{"0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0", "1, 3, 5, 2, 4", "4"},
{"0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0", "1, 3, 5, 2, 4", "5"},
{"0", "1", "1"},
{"0", "1", "6"},
{"0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0", "1, 3, 5, 2, 4", "7"}
};

(* Invalid Tests *)

depthFirstSearchMain["", "1, 3, 5, 2, 4", "4"]
depthFirstSearchMain["0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0", "", "1"]
depthFirstSearchMain["0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0", "1, 3, 5, 2, 4", ""]

``````

Depth First Search in Mathematica was written by:

• Ben Hekster

If you see anything you'd like to change or update, please consider contributing.

## How to Implement the Solution

No 'How to Implement the Solution' section available. Please consider contributing.

## How to Run the Solution

No 'How to Run the Solution' section available. Please consider contributing.