So I have an adjacency matrix of size N x N
for a graph with N
nodes. I would like to conduct a Depth First Search through this matrix in order to find if a path does or does not exist from a Source
node to a Destination
node. If it exists I would like to print the path.
In the psuedocode below, it uses a matrix/graph G
to find all vertices that can be accessed with a starting node of v
. How would I modify this algorithm so I can have something similar to this: procedure DFS(G,v,d)
where d
is the target node I am searching for?
procedure DFS(G,v):
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G,w)
Also as a sidenote, how would I add the ability to return the total weight of all the edges for the path that it discovered?
The algorithm needs to be modified in two ways
In the pseudocode below, the path variable P
starts as an empty list. When the destination is found, the destination node is placed in P
. Then as each level of recursion returns, the current node w
is appended to the path. When the top-level call returns, P
contains the full path. There's only one problem, the path is in reverse: destination to source. So you'll have to turn it around.
procedure DFS(G,v,d,P=empty):
if v equals d
initialize P with d
return P
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G,w,d,P)
if P is not empty
append v to P
return P
return empty