Popcorn Hack #1

The last representation is most effecient since it’s the most compact storage wise, since you only store the edges/connections not every single non-connection too.

Homework Part 1

How might I represent a weighted graph?

Using an Adjacency List?

A weighted graph can be represented using an adjacency list where each vertex maps to a list of neighboring vertices and their edge weights. For example, A: [(B, 5), (C, 2)] shows edges with weights from A to B and C.

Using a Vertex and Edge Set?

You can use a vertex set and an edge set, where each edge is a tuple like (A, B, 5) indicating a directed edge from A to B with a weight of 5. This approach clearly separates node definitions and weighted connections.

How might I represent a directed graph?

Using an Adjacency List?

In a directed graph’s adjacency list, each vertex points only to its outbound neighbors. For example, A: [B, C] means there are edges from A to B and A to C.

Using a Vertex and Edge Set?

A directed graph can also be represented using a set of vertices and a set of ordered edge pairs like (A, B). The order of the pair reflects the direction of the edge—from A to B.

  1. Represent the following graph using an adjacency matrix Image broken on the website

Homework Part 2

addNode Adds a node to the graph No connections be default removeEdge Removes a specified edge from the graph Does NOT remove the nodes

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

    public void removeEdge(int source, int destination) {
        adjacencyList[source].remove(Integer.valueOf(destination));
        adjacencyList[destination].remove(Integer.valueOf(source));
    }

Homework - Part 3

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

If the graph has loops (cycles), both BFS and DFS could get stuck in infinite recursion or repeated processing, because they may visit the same node multiple times.

BONUS: 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

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

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

List<Integer> shortestPath = null;

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

    if (isValidPath(fullPath)) {
        if (shortestPath == null || fullPath.size() < shortestPath.size()) {
            shortestPath = new ArrayList<>(fullPath);
        }
    }
}

if (shortestPath != null) {
    System.out.println("Cursed TSP Path: " + shortestPath);
    System.out.println("Steps: " + (shortestPath.size() - 1));
} else {
    System.out.println("No valid path found that visits all nodes.");
} }

private void permute(List arr, int k, List<List> result) { if (k == arr.size()) { result.add(new ArrayList<>(arr)); } else { for (int i = k; i < arr.size(); i++) { Collections.swap(arr, i, k); permute(arr, k + 1, result); Collections.swap(arr, k, i); } } }

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