Searching

Problem: Given a starting node, I want to find a path to the end node.

Popcorn Hack #3

As a human, how might you do this? Describe a process.

BFS

  1. Check if the starting node is equal to target
  2. Move to every node connected to starting node
    • Check if each of those nodes are equal to the target
  3. Move to every node connected to one you just checked
    • Check if each of those nodes are equal to the target
  4. Repeat

BFS first checks the nodes closest to the starting node, and checks the nodes farthest away last.

alt text

import java.util.*;

public class Graph {

    private int nodes;
    private LinkedList<Integer>[] adjacencyList;

    public Graph(int nodes) {
        this.nodes = nodes;
        adjacencyList = new LinkedList[nodes];

        for (int i = 0; i < nodes; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
    }

    public void displayGraph() {
        System.out.println("Graph adjacency list:");
        for (int i = 0; i < nodes; i++) {
            System.out.print(i + " -> ");
            for (int neighbor : adjacencyList[i]) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public void bfs(int start, int target) {
        Queue<Integer> queue = new LinkedList<>();
        Map<Integer, Integer> parent = new HashMap<>();
        Set<Integer> visited = new HashSet<>(); // Track visited nodes

        queue.add(start);
        parent.put(start, -1);
        visited.add(start); // Mark start as visited

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.println("Visiting: " + current);

            if (current == target) {
                System.out.println("Target " + target + " found!");
                printPath(parent, target);
                return;
            }

            for (int neighbor : adjacencyList[current]) {
                if (!visited.contains(neighbor)) { // Only visit unvisited nodes
                    parent.put(neighbor, current);
                    queue.add(neighbor);
                    visited.add(neighbor); // Mark as visited
                }
            }
        }

        System.out.println("Target " + target + " not found.");
    }

    private void printPath(Map<Integer, Integer> parent, int target) {
        List<Integer> path = new ArrayList<>();
        for (int at = target; at != -1; at = parent.get(at)) {
            path.add(at);
        }
        Collections.reverse(path);
        System.out.println("Path: " + path);
    }

}

// Sample Usage
Graph graph = new Graph(7);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);

graph.displayGraph();

System.out.println("");
graph.bfs(0, 6);

Graph adjacency list:
0 -> 1 2 
1 -> 3 4 
2 -> 5 
3 -> 6 
4 -> 
5 -> 
6 -> 

Visiting: 0
Visiting: 1
Visiting: 2
Visiting: 3
Visiting: 4
Visiting: 5
Visiting: 6
Target 6 found!
Path: [0, 1, 3, 6]

DFS

  1. Check if the starting node is equal to target
  2. Move to the first node connected to the target
    • Check if that node is equal to the target
  3. Move to the first node connected to the node in 2
    • Check if that node is equal to the target
  4. Repeat 2-3 until there are no more child nodes
  5. Backtrack a Node
  6. Repeat 4-5
  7. Repeat 2-6

DFS first checks every node in a “branch” of the tree, before moving on the next branch

alt text

import java.util.*;

public class Graph {

    private int nodes;
    private LinkedList<Integer>[] adjacencyList;

    public Graph(int nodes) {
        this.nodes = nodes;
        adjacencyList = new LinkedList[nodes];

        for (int i = 0; i < nodes; i++) {
            adjacencyList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
    }

    public void displayGraph() {
        System.out.println("Graph adjacency list:");
        for (int i = 0; i < nodes; i++) {
            System.out.print(i + " -> ");
            for (int neighbor : adjacencyList[i]) {
                System.out.print(neighbor + " ");
            }
            System.out.println();
        }
    }

    public void bfs(int start, int target) {
        // queue is used to explore nodes in breadth-first order
        // essentially, any encountered nodes are added to the Queue
        // Queue is then iterated in order to see who to visit next
        Queue<Integer> queue = new LinkedList<>(); 
        // tracks each node's parent to reconstruct the path
        Map<Integer, Integer> parent = new HashMap<>(); 

        queue.add(start);
        // start node has no parent
        parent.put(start, -1); 

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.println("Visiting: " + current);

            if (current == target) {
                System.out.println("Target " + target + " found!");
                printPath(parent, target);
                return;
            }

            for (int neighbor : adjacencyList[current]) {
                // track how neighbor was reached
                parent.put(neighbor, current); 
                // add neighbor to queue; means will visit at some later point
                queue.add(neighbor); 
            }
        }

        System.out.println("Target " + target + " not found.");
    }

    public void dfs(int start, int target) {
        Map<Integer, Integer> parent = new HashMap<>();
        Set<Integer> visited = new HashSet<>(); // Track visited nodes
        parent.put(start, -1); // Fix: set start node's parent
        dfsHelper(start, target, parent, visited);
    }

    private boolean dfsHelper(int current, int target, Map<Integer, Integer> parent, Set<Integer> visited) {
        System.out.println("Visiting: " + current);
        visited.add(current); // Mark as visited

        if (current == target) {
            System.out.println("Target " + target + " found!");
            printPath(parent, target);
            return true;
        }

        for (int neighbor : adjacencyList[current]) {
            if (!visited.contains(neighbor)) { // Only visit unvisited nodes
                parent.put(neighbor, current);
                if (dfsHelper(neighbor, target, parent, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    private void printPath(Map<Integer, Integer> parent, int target) {
        List<Integer> path = new ArrayList<>();
        for (int at = target; at != -1; at = parent.get(at)) {
            path.add(at);
        }
        Collections.reverse(path);
        System.out.println("Path: " + path);
    }

}

// Sample Usage
Graph graph = new Graph(7);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 6);

graph.displayGraph();

System.out.println("");
graph.dfs(0, 6);

Graph adjacency list:
0 -> 1 2 
1 -> 3 4 
2 -> 5 
3 -> 6 
4 -> 
5 -> 
6 -> 

Visiting: 0
Visiting: 1
Visiting: 3
Visiting: 6
Target 6 found!
Path: [0, 1, 3, 6]

Homework - Part 3

  1. What happens if the graph has a loop in it? Please account for this in the two algorithms above.

If the graph has a loop, the algorithms may keep visiting the same nodes, and cause infinite loops or redundancies. code changed above

BONUS:

  1. Traveling Salesman but cursed
    • Your code should take in a graph and output the fastest path to travel to every single graph given a starting and ending node
    • Assume each edge has the same cost
    • Efficiency doesn’t matter