i am trying to make a python dfs connecting island with recursion...
the program works fine, however on some cases there are logical error in which the output is incorrect
For example
o o o
o x x
o o o the output is 1 which is correct.
However , on other cases
o x o
o x o
o o o the output is 2 which is incorrect.
Here is my full code that includes dfs function
row = int(input("Enter Row : "))
col = int(input("Enter Col : "))
# declare array baru namanya peta
peta = []
# array 2 dimensi
# Masukkin smua input ke array petas
for i in range(0,row):
line = input()
peta.append(line)
store = []
# declare array baru nama visited
visited = []
for i in range(0,row):
visited.append([])
# buat column di row i false smua
for j in range(0,col):
visited[i].append(False)
def dfs(i,j):
visited[i][j] = True
a = row-1
b = col-1
#peta[i][j] = store[a][b]
for i in range(i,row):
for j in range(j,col):
if(visited[i][j] == True):
return 1
else:
if(peta[i][j] == 'x' and visited[i][j] == False ):
#top left array
if(i == 0 or j == 0):
dfs(i+1,j+1)
dfs(i+1,j)
dfs(i,j+1)
#bottom left array
elif(i == a and j == 0):
dfs(i-1,j)
dfs(i-1,j+1)
dfs(i,j+1)
#top right array
elif(i == 0 and j == b):
dfs(i,j-1)
dfs(i+1,j-1)
dfs(i+1,j)
#bottom right array
elif(i == a and j == b):
dfs(i,j-1)
dfs(i-1,j-1)
dfs(i-1,j)
#west array
elif(i >= 1 and j == 0):
dfs(i-1,j)
dfs(i-1,j+1)
dfs(i+1,j)
dfs(i,j+1)
dfs(i+1,j+1)
#north array
elif(i==0 and j>=1):
dfs(i,j-1)
dfs(i+1,j-1)
dfs(i+1,j)
dfs(i,j+1)
dfs(i+1,j+1)
#east array
elif(i>=1 and j==b):
dfs(i-1,j)
dfs(i-1,j-1)
dfs(i,j-1)
dfs(i+1,j-1)
dfs(i+1,j)
#south array
elif(i==a and j>=1):
dfs(i,j-1)
dfs(i-1,j-1)
dfs(i-1,j)
dfs(i-1,j+1)
dfs(i,j+1)
#middle array
else:
dfs(i-1,j-1)
dfs(i-1,j)
dfs(i-1,j+1)
dfs(i,j-1)
dfs(i,j+1)
dfs(i+1,j-1)
dfs(i+1,j)
dfs(i+1,j+1)
else:
#peta[i][j] = 0
return 0
numberofisland = 0
for i in range(0,row):
for j in range(0,col):
if((peta[i][j] == 'x' and visited[i][j] == False)):
dfs(i,j)
numberofisland+=1
print(numberofisland)
in my opinion, my logical error is i visit the visited node twice , however there seems no error in my arrays. Can you give some suggestion about where my mistake is?
Thank you very much for your time, cheers
edit : i have updated into full code version as community requested ( how to call the function, global variable, etc )
Some things in your code do not make sense:
1) If you want to return a value from the dfs function, this value should have some meaning and it should be used. If you only call a function for its side-effects, then you can just return with no value. In this case, it looks like to me as the purpose of the dfs function is to update the visited array, so you do not need to return 1 or 0 or anything.
2) When you do a depth-first search in a graph, you start at a node, and you visit its connected nodes recursively. If you have a for-loop inside the dfs function which visits a big part of the graph, ignoring connections, then you are not doing DFS. Generally, you only need to recursively call the dfs function on the connected nodes.
3) The way your function looks right now, it seems that it will always return 1 before making any recursive calls.
Also take note of the following good practices for Python code:
1) Avoid constructs like if expression == True:. Instead use if expression:. Also instead of if expression == False, use if not expression.
2) Avoid using parentheses around the conditional expression in if and elif clauses, it is not neccessary, unlike C or Java. For example, instead of elif (a == b): use elif a == b.
3) Add a docstring at the top of a function, to describe what the function does (see my code below for an example).
From what I understand, you want for each call of the dfs function to visit all connected xs that form an island. You can do this with the following code:
def dfs(i,j):
'''
This function starts from the square with coordinates (i,j).
The square (i,j) should be an 'x', and also unvisited.
This function will keep visiting all adjacent 'x' squares, using a
depth first traversal, and marking these squares as visited in the
@visited array.
The squares considered adjacent are the 8 surrounding squares:
(up, up-right, right, down-right, down, down-left, left, up-left).
'''
# The range checks have been moved to the beginning of the function, after each call.
# This makes the code much shorter.
if i < 0 or j < 0 or i >= row or j >= col:
return
# If we reached a non-x square, or an already visited square, stop the recursion.
if peta[i][j] != 'x' or visited[i][j]:
# Notice that since we don't do something with the return value,
# there is no point in returning a value here.
return
# Mark this square as visited.
visited[i][j] = True
# Visit all adjacent squares (up to 8 squares).
# Don't worry about some index falling out of range,
# this will be checked right after the function call.
dfs(i-1,j-1)
dfs(i-1,j)
dfs(i-1,j+1)
dfs(i,j-1)
dfs(i,j+1)
dfs(i+1,j-1)
dfs(i+1,j)
dfs(i+1,j+1)