Below is my code for DFS[Depth first search], and my code could handle complicated graph, but failed to handle simple graph like the graph i gave, so my Question is that how to work it out? I am doing it recursively. Any kind of help is appreciated.
graph = { 'A' : ['B','S']}
def dfs(graph,start_node,visited):
if start_node:
if start_node not in visited:
visited.append(start_node)
for node in graph[start_node]:
dfs(graph,node,visited)
else:
return visited
return visited
visited=dfs(graph,"A",[])
print(visited)
How are you representing graphs? If it is as standard graph (with 2-way edges) represented as a dictionary keyed by the nodes in which the values are lists of adjacent nodes, then your "graph" is not a graph at all since it is missing edge lists for 'B' and 'S'. But then, why are you using it as a test case? The only relevant question for such input is if you want to test if your code fails gracefully on them (yours doesn't -- but proper error handling is tangential to your question).
On the other hand, if these are directed graphs, then your example makes sense (interpreting the values as corresponding to outgoing edges and the keys are nodes which have outgoing edges). But in that case, you are failing to handle terminal nodes. You can either explicitly check if a node is in the dictionary before recursing on it, or treat the list of directly reachable nodes for terminal nodes as implicitly [] and using the dictionary get() method to return it in those cases:
def dfs(graph,start_node,visited):
if start_node:
if start_node not in visited:
visited.append(start_node)
for node in graph.get(start_node,[]):
dfs(graph,node,visited)
else:
return visited
return visited
This will work as expected, printing ['A', 'B', 'S'].