Graphs

Popcorn hack 1

The last represenation is the most efficient because it is the most compact, since you only store the edges.

Homework Part 1

How might I represented a weighted graph?

Using an Adjacency List?

Each vertex maps to a list of its neighbors, with edge weights.

import java.util.*;

class WeightedGraphAdjList {
    private Map<String, List<Edge>> adjList = new HashMap<>();

    static class Edge {
        String destination;
        int weight;

        Edge(String dest, int w) {
            destination = dest;
            weight = w;
        }
    }

    public void addEdge(String src, String dest, int weight) {
        adjList.computeIfAbsent(src, k -> new ArrayList<>()).add(new Edge(dest, weight));
    }

    public void printGraph() {
        for (String vertex : adjList.keySet()) {
            System.out.print(vertex + " -> ");
            for (Edge edge : adjList.get(vertex)) {
                System.out.print("(" + edge.destination + ", " + edge.weight + ") ");
            }
            System.out.println();
        }
    }
}

Using a Vertex and Edge Set?

Use sets to separately store vertices and weighted edges.

import java.util.*;

class WeightedGraphSet {
    Set<String> vertices = new HashSet<>();
    Set<WeightedEdge> edges = new HashSet<>();

    static class WeightedEdge {
        String from, to;
        int weight;

        WeightedEdge(String f, String t, int w) {
            from = f;
            to = t;
            weight = w;
        }

        @Override
        public String toString() {
            return "(" + from + " -> " + to + ", " + weight + ")";
        }
    }

    public void addEdge(String from, String to, int weight) {
        vertices.add(from);
        vertices.add(to);
        edges.add(new WeightedEdge(from, to, weight));
    }

    public void printGraph() {
        System.out.println("Vertices: " + vertices);
        System.out.println("Edges:");
        for (WeightedEdge edge : edges) {
            System.out.println(edge);
        }
    }
}

How might I represented a directed graph?

Using an Adjacency List?

Each vertex points to a list of its outgoing neighbors.

import java.util.*;

class DirectedGraphAdjList {
    private Map<String, List<String>> adjList = new HashMap<>();

    public void addEdge(String src, String dest) {
        adjList.computeIfAbsent(src, k -> new ArrayList<>()).add(dest);
    }

    public void printGraph() {
        for (String vertex : adjList.keySet()) {
            System.out.println(vertex + " -> " + adjList.get(vertex));
        }
    }
}

Using a Vertex and Edge Set?

Each edge is stored as a directed pair, and all vertices are tracked separately.

import java.util.*;

class DirectedGraphSet {
    Set<String> vertices = new HashSet<>();
    Set<Edge> edges = new HashSet<>();

    static class Edge {
        String from, to;

        Edge(String f, String t) {
            from = f;
            to = t;
        }

        @Override
        public String toString() {
            return "(" + from + " -> " + to + ")";
        }
    }

    public void addEdge(String from, String to) {
        vertices.add(from);
        vertices.add(to);
        edges.add(new Edge(from, to));
    }

    public void printGraph() {
        System.out.println("Vertices: " + vertices);
        System.out.println("Edges:");
        for (Edge edge : edges) {
            System.out.println(edge);
        }
    }
}

Homework Part 2

addNode

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<>();
        }
    }

    // Adds a new node with no connections
    public void addNode() {
        nodes++;
        LinkedList<Integer>[] newAdjList = new LinkedList[nodes];
        for (int i = 0; i < nodes - 1; i++) {
            newAdjList[i] = adjacencyList[i];
        }
        newAdjList[nodes - 1] = new LinkedList<>();
        adjacencyList = newAdjList;
    }

    // For visualizing the graph
    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();
        }
    }
}

removeEdge

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<>();
        }
    }

    // Adds an undirected edge
    public void addEdge(int source, int destination) {
        adjacencyList[source].add(destination);
        adjacencyList[destination].add(source); // remove for directed
    }

    // Removes an undirected edge
    public void removeEdge(int source, int destination) {
        adjacencyList[source].remove(Integer.valueOf(destination));
        adjacencyList[destination].remove(Integer.valueOf(source)); // remove for directed
    }

    // For visualizing the graph
    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();
        }
    }
}

Popcorn Hack #3

Start at the beginning node and look at all the connected neighbors. Choose one path to follow and keep track of the nodes you’ve visited. If you reach a dead end, backtrack and try a different path until you reach the end node.

Homework Part 3

If the graph contains a loop (cycle), the current BFS and DFS implementations may enter an infinite loop or throw errors because they revisit the same nodes again and again without stopping. To fix this, we need to track visited nodes and avoid visiting the same node more than once.

Updated bfs with loop protection:

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

    queue.add(start);
    visited.add(start);      // ✅ mark start as visited
    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]) {
            if (!visited.contains(neighbor)) { // ✅ only add unvisited
                visited.add(neighbor);         // ✅ mark as visited
                parent.put(neighbor, current);
                queue.add(neighbor);
            }
        }
    }

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

Updated dfs with loop protection:

public void dfs(int start, int target) {
    Map<Integer, Integer> parent = new HashMap<>();
    Set<Integer> visited = new HashSet<>(); // ✅ track visited
    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!");
        parent.put(current, -1); // in case start == target
        printPath(parent, target);
        return true;
    }

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

    return false;
}

Bonus

import java.util.*;

public class Graph {
    private int nodes;
    private List<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 src, int dest) {
        adjacencyList[src].add(dest);
        adjacencyList[dest].add(src); // assume undirected for TSP
    }

    public int cursedTSP(int start, int end) {
        List<Integer> nodesToVisit = new ArrayList<>();
        for (int i = 0; i < nodes; i++) {
            if (i != start && i != end) {
                nodesToVisit.add(i);
            }
        }

        List<List<Integer>> allPermutations = new ArrayList<>();
        permute(nodesToVisit, 0, allPermutations);

        int minPathLength = Integer.MAX_VALUE;
        List<Integer> bestPath = null;

        for (List<Integer> perm : allPermutations) {
            List<Integer> fullPath = new ArrayList<>();
            fullPath.add(start);
            fullPath.addAll(perm);
            fullPath.add(end);

            if (isValidPath(fullPath)) {
                int pathLength = fullPath.size() - 1; // each edge = 1
                if (pathLength < minPathLength) {
                    minPathLength = pathLength;
                    bestPath = new ArrayList<>(fullPath);
                }
            }
        }

        System.out.println("Best path: " + bestPath);
        return minPathLength == Integer.MAX_VALUE ? -1 : minPathLength;
    }

    private boolean isValidPath(List<Integer> path) {
        for (int i = 0; i < path.size() - 1; i++) {
            if (!adjacencyList[path.get(i)].contains(path.get(i + 1))) {
                return false;
            }
        }
        return true;
    }

    private void permute(List<Integer> list, int l, List<List<Integer>> result) {
        if (l == list.size()) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = l; i < list.size(); i++) {
            Collections.swap(list, i, l);
            permute(list, l + 1, result);
            Collections.swap(list, i, l);
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);

        int length = graph.cursedTSP(0, 4);
        System.out.println("Shortest cursed TSP path length: " + length);
    }
}