CODEWITHSUNDEEP
algorithmpseudocodeadjacency-matrix
Rivasa
Rivasa

Reputation: 6740

Modifying a Depth First Search Algorithm using an Adjacency Matrix to search for specific end-node

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?

Upvotes: 2

Views: 216

Answers (1)

user3386109
user3386109

Reputation: 34839

The algorithm needs to be modified in two ways

  1. it needs to stop when it finds the destination
  2. it needs to produce a path to the destination

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

Upvotes: 2

Related Questions