Depth First Search Implementation (iterative)

Question

Here is my code for Depth First Search and, as far as I know, it is working fine on most cases. It is not very efficient as I have implemented it for the very first time..

Warning: It is only for bi-directional Graphs or Trees.. And it is not searching anything, just traversing. I think searching should be easy if it is traversing correctly..

def DFS(matrix,x):
 for i in range(len(matrix)):
 for j in range(len(matrix[i])):
 if matrix[i][j]=="farigh" or matrix[i][j]=="hogya":
 matrix[i].pop()
 stack = [x]
 Matrix=matrix
 print(Matrix)
 dimen=len(Matrix)
 rslt = [x]
 while stack:
 current=Matrix[stack[-1]-1]
 for j in range(len(current)):
 if current[j]==1 :
 a=False
 if (j+1 not in stack) and (j+1 not in rslt):
 stack.append(j+1)
 rslt.append(j+1)
 print("stack",stack)
 a= True
 break
 if j+1== len(current):
 current.append("farigh")
 if len(Matrix[stack[-1]-1]) == dimen and a == True :
 b=0
 current2= Matrix[stack[-1]-1]
 for e in range(len(current2)):
 if current2[e]==1:
 b=b+1
 if b==1:
 stack.pop()
 current2.append("Hogya")
 if current[-1]=="farigh":
 stack.pop()
 print(stack,"stack")
 return(rslt,"rslt")

Let me know if you find any bugs.

• Gareth Rees: For other reviewers: "farigh" = "free" and "hogya" = "done" (in Urdu).
• Janne Karila: DFS([[0,0,1],[0,0,1],[1,1,0]], 0) gives [0, 1, 2] while I expected [0, 2, 1]
• Ateeb Ahmed: Janne Karila, Hi :) This code is built on the assumption that the node counting always starts from 1 not 0. Try giving it DFS([[0,0,1],[0,0,1],[1,1,0]], 1) it will give [1,3,2].

Answer 1

Advice 1 (Space around binary operators)

Matrix=matrix

PEP-8 requires one space before a binary operator and after it:

Matrix = matrix

Advice 2 (Variable names should start from a lowercase letter)

Once again, you have a variable called Matrix. This applies to the function name DFS as well; I suggest you rename it to depth_first_search.

Advice 3

You print intermediate progress in your algorithm. Never do this. Think about what happens when your friend reuses your implementation: he or she will get overwhelmed with all that output that has no value. Also, it might slow down the execution of your algorithm, since printing goes down the chain to the very kernel. If you need to print anything, modify your algorithm to return a data structure which can do that, but let it do its work silently.

Advice 4

Your implementation seems to run in \$\Theta(V^2)\$ time. I suggest you convert the adjacency matrix to an adjacency list and input that list to your depth first search; this will bring down complexity to \$\Theta(E + V)\,ドル which is more efficient on sparse graphs (where \$E = o(V^2)\$).

Alternative implementation

Putting all together, I had this in mind:

from collections import deque
def adjacency_matrix_to_adjacency_list(adjacency_matrix):
 map = dict()
 j = 0
 for i in range(len(adjacency_matrix)):
 map[i] = []
 for adjacency_matrix_row in adjacency_matrix:
 for i in range(len(adjacency_matrix_row)):
 current_entry = adjacency_matrix_row[i]
 if current_entry == 1:
 map[j].append(i)
 j += 1
 return map
def depth_first_search(adjacency_matrix, source_node):
 open = deque([source_node])
 parents = {source_node: None}
 while open:
 current_node = open.pop()
 for child_node in adjacency_matrix[current_node]:
 if child_node not in parents.keys():
 parents[child_node] = current_node
 open.append(child_node)
 return parents

Answer 2

Let me know if you find any bugs.

I saw no bugs. Nothing leapt off the page.

It would be helpful if you post unit tests which exercise the code.

Testing j+1 == len(current): did not seem very idiomatic. It would be more pythonic to ask if j points at len(current) - 1, the last entry.

There's nothing wrong with working back-to-front instead of front-to-back, but it feels slightly odd. I get the sense that you wanted to take advantage of O(1) list pop(). I encourage you to consider deque, which also offers popleft().

Answer 3

You have this code at the top of your function:

for i in range(len(matrix)):
 for j in range(len(matrix[i])):
 if matrix[i][j]=="farigh" or matrix[i][j]=="hogya":
 matrix[i].pop()

I don't know what this is trying to do, but by default the .pop() is going to remove an item from the matrix row (assuming the matrix is a list of lists, and not some other type).

Since you are iterating over range(len(matrix[i])), and since you don't break after doing the pop, it seems like there should be an IndexError when you try to access the last element in that row.

Edit:

Also, you spell "Hogya" differently in different places, although this doesn't seem to matter.