7
$\begingroup$

I'm trying to implementa recursive depth first search. It works and the result is below:

e = 
  {1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 
   2 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 5, 
   3 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 5, 
   4 \[UndirectedEdge] 6, 5 \[UndirectedEdge] 6};
nG = Graph[e, VertexLabels -> Automatic];

Clear[DFS, getVisited];
getVisited[am_?MatrixQ] := 
  Module[{length = Length[am[[1]]]},
    visited = ConstantArray[False, length];
    visited];
DFS[am_?MatrixQ, n_?IntegerQ] := 
  Module[{i, l = Length[visited]},
    visited[[n]] = True;
    Print["Visited: " , n];
    For[i = 1, i <= l, ++i,
    If[am[[n, i]] == 1 && visited[[i]] == False, DFS[am, i]]]];

visited = getVisited[AdjacencyMatrix[nG]];
DFS[AdjacencyMatrix[nG], 4]

4, 2, 1, 3, 5, 6

The problem is in the implementation. As the list of visited vertices should be global, I need to call the function getVisited before calling my main function to firstly get the global array. This operation seems like a redundant one and I'm looking for another more neat approach. If you have some ideas it would be great.

$\endgroup$
  • $\begingroup$ What about just using visited = ConstantArray[False, VertexCount[nG]] instead? $\endgroup$ – Henrik Schumacher Dec 22 '19 at 12:09
  • $\begingroup$ Btw. you might want to let the For loop run only over the is in am["AdjacencyLists"][[n]]. And better use a Do loop instead. $\endgroup$ – Henrik Schumacher Dec 22 '19 at 12:17
  • $\begingroup$ Also the recursive approach has many shortcomings. One hits the $RecursionLimit quite quickly for larger graphs. $\endgroup$ – Henrik Schumacher Dec 22 '19 at 12:22
8
$\begingroup$

Depth-first search is already implemented in the built-in function DepthFirstScan, but I assume you don't just want to use it but learn how to implement this algorithm in Mathematica. I would do it as follows:

It is convenient to use an adjacency list representation of the graph. I will use IGAdjacencyList from IGraph/M, which works reliably for all sort of graphs. For simple undirected graphs, you may use AssociationThread[VertexList[g], AdjacencyList[g]] as an alternative that does not require IGraph/M.

The implementation:

dfs[g_?GraphQ, v0_, f_] := 
 Module[{visited, rec, al = IGAdjacencyList[g]},
  If[Not@VertexQ[g, v0], Return[$Failed]]; (* check that the input is valid *)
  visited[_] := False;
  rec[v_?visited] := Null;
  rec[v_] := (visited[v] = True; f[v]; rec /@ al[v]);
  rec[v0];
 ]

g is the input graph, v0 is the starting vertex, and f is a function that will be evaluated for each vertex as they are visited. You may use Sow to collect them in to a list, or Print to just display them.

Demonstration with your graph:

dfs[nG, 4, Print]

4

2

1

3

5

6

Explanation of the function:

  • visited is a local symbol which is used to keep track of which vertices have been visited.
  • rec is the function that traverses the graph recursively. It takes a vertex as input. For each neighbour of this vertex, 1) it checks if it has already been visited 2) if not, it calls f, marks it as visited, and applies itself to all its neighbours.

Alternatively, you could make visited an association and return its keys at the end.

dfs2[g_?GraphQ, v0_, f_] := 
 Module[{visited = <||>, rec, al = IGAdjacencyList[g]}, 
  If[Not@VertexQ[g, v0], Return[$Failed]];
  rec[v_?visited] := Null;
  rec[v_] := (AssociateTo[visited, v -> True]; f[v]; rec /@ al[v]);
  rec[v0];
  Keys[visited]
 ]
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.