Graph Traversal

Question 1

Graph Traversal (DFS - each node is a String) (given an initial String, want to see if DFS on that node contains a target String) ITERATIVE

Answer 1

for (int i = 0; i < words1.length; ++i) {
            String w1 = words1[i], w2 = words2[i];
            Stack stack = new Stack();
            Set seen = new HashSet();
            stack.push(w1);
            seen.add(w1);
            search: {
                while (!stack.isEmpty()) {
                    String word = stack.pop();
                    if (word.equals(w2)) break search;
                    if (graph.containsKey(word)) {
                        for (String nei: graph.get(word)) {
                            if (!seen.contains(nei)) {
                                stack.push(nei);
                                seen.add(nei);
                            }
                        }
                    }
                }

Question 2

Graph Traversal (DFS - each node is a String) (given an initial String, want to see if DFS on that node contains a target String) RECURSIVE

Answer 2

for (int i = 0; i < words1.length; i++) {
if (words1[i].equals(words2[i])) continue;
if (!graph.containsKey(words1[i])) return false;
if (!dfs(graph, words1[i], words2[i], new HashSet<>())) return false;
}

    return true;
}

private boolean dfs(Map> graph, String source, String target, Set visited) {
    if (graph.get(source).contains(target)) return true;

    if (visited.add(source)) {
        for (String next : graph.get(source)) {
            if (!visited.contains(next) && dfs(graph, next, target, visited)) 
                return true;
        }
    }
    return false;

Question 3

Build a Graph (HashMap of String : Set

Answer 3

Map> graph = new HashMap<>();
for (String[] p : pairs) {
graph.putIfAbsent(p[0], new HashSet<>());
graph.putIfAbsent(p[1], new HashSet<>());
graph.get(p[0]).add(p[1]);
graph.get(p[1]).add(p[0]);
}