Я пытаюсь преобразовать этот Python Depth-First Search в Java. Вот мой код Python:
def dfs(graph, current_vertex, target_value, visited=None):
if visited is None: #for when not a recursive call
visited = [] #empty list
visited.append(current_vertex) #adds current vertex to visited
if current_vertex == target_value: #for when current_vertex is target value (ie target reached)
return visited
# Add your recursive case here:
for neighbor in graph[current_vertex]: #checks each neighbor of curr, Remember that the graphs hold key-value pairs for each vertex and its set of connected vertices.
if neighbor not in visited: #if neighbor has not been added to visited
path = dfs(graph, neighbor, target_value, visited) #recursive call with new vertex, a visited list(now a list of at least one vertex value), graph and TV remain same
if path: #if the path exists
return path #return the path
#set with keys and values
the_most_dangerous_graph = {
'lava': set(['sharks', 'piranhas']),
'sharks': set(['lava', 'bees', 'lasers']),
'piranhas': set(['lava', 'crocodiles']),
'bees': set(['sharks']),
'lasers': set(['sharks', 'crocodiles']),
'crocodiles': set(['piranhas', 'lasers'])
}
# Call dfs() below and print the result:
print(dfs(the_most_dangerous_graph, "crocodiles", "bees"))
Я получил общее представление об алгоритме: переходите к дочерним элементам до тех пор, пока не пройдете все, начинайте всплывать, пока не доберетесь до вершины, которая не посещала детей, посетите эту вершину и сохраните все посещенные вершины в порядке посещения. Тем не менее, у меня есть идея, как начать на Java, с рекурсией. Вот что я получил:
import java.util.*;
public class DepthFirstSearch {
private static Set<String> DFSHelper(HashMap<String,String[]> graph, String currentValue,
String targetValue, HashMap<String, String> visited, Stack<String> s) {
Iterator it = graph.values().iterator();
visited.put(currentValue, null);
s.push(currentValue);
System.out.println(s.peek());
System.out.println(currentValue);
//System.out.println(graph.get(currentValue));
if(!s.isEmpty()) {
String neighbor = it.next().toString();
if(!visited.containsKey(neighbor)) {
visited.put(neighbor,currentValue);
currentValue = neighbor;
return DFSHelper(graph,currentValue,targetValue,visited,s);
}
}
return visited.keySet();
}
public static Set<String> DFS(HashMap<String,String[]> graph, String currentValue,
String targetValue) {
HashMap<String,String> visited = new HashMap<>();
Stack<String> s = new Stack<String>();
return DFSHelper(graph,currentValue,targetValue,visited,s);
}
public static void main(String[] args) {
HashMap<String, String[]> myGraph = new HashMap<>();
myGraph.put(
"lava", new String[] {"sharks", "piranhas"}
);
myGraph.put(
"sharks", new String[] {"lava", "bees", "lasers"}
);
myGraph.put(
"piranhas", new String[] {"lava", "crocodiles"}
);
myGraph.put(
"bees", new String[] {"sharks"}
);
myGraph.put(
"lasers", new String[] {"sharks", "crocodiles"}
);
myGraph.put(
"crocodiles", new String[] {"piranhas", "lasers"}
);
System.out.println(DFS(myGraph, "crocodiles", "bees"));
System.out.println(DFS(myGraph, "crocodiles", "crocodiles"));
System.out.println(DFS(myGraph, "crocodiles", "zebras"));
}
}
На данный момент я получаю только другие хеш-коды, кроме своих операторов печати, и я не уверен, что я даже на правильном пути.