2021 October 18 CS61B, Java

「CS61B」Note(6) Lab11 Graphs

In this lab, the task is to explore how a few graph algorithms behave in the context of mazes, like the one shown below. The requirements are at this link. Depth First Search:

Breadth First Search

Write an algorithm that crawls the graph, locating the shortest path from position (1, 1) to (N, N), stopping as soon as the (N, N) position is found.

public class MazeBreadthFirstPaths extends MazeExplorer {
    /* Inherits public fields:
    public int[] distTo;
    public int[] edgeTo;
    public boolean[] marked;
    */
    private int s;
    private int t;
    private Maze maze;
    private Queue<Integer> queue;

    public MazeBreadthFirstPaths(Maze m, int sourceX, int sourceY, int targetX, int targetY) {
        super(m);
        maze = m;
        s = maze.xyTo1D(sourceX, sourceY);
        t = maze.xyTo1D(targetX, targetY);
        distTo[s] = 0;
        edgeTo[s] = s;
        // Add more variables here!
    }

    /** Conducts a breadth first search of the maze starting at the source. */
    private void bfs() {
        // TODO: Your code here. Don't forget to update distTo, edgeTo, and marked, as well as call announce()
        queue = new LinkedList<Integer>();
        int v;
        queue.offer(s);
        while (true) {
            v = queue.poll();
            marked[v] = true;
            announce();

            if (v == t) {
                return;
            }
            for (int w : maze.adj(v)) {
                if (!marked[w]) {
                    queue.offer(w);
                    edgeTo[w] = v;
                    distTo[w] = distTo[v] + 1;
                }
            }
        }
    }

Depth First Search & Cycle Check

Use DFS to detect cycles in this maze. The idea is: For every visited vertex v, if there is an adjacent u such that u is already visited and u is not parent of v, then there is a cycle in graph.

public class MazeCycles extends MazeExplorer {
    /* Inherits public fields:
    public int[] distTo;
    public int[] edgeTo;
    public boolean[] marked;
    */
    private int s = 0;
    private boolean cycleFound = false;
    // there should be no edges connecting the part of the graph that doesn’t contain a cycle,
    // so create a temp list to save the original edgeTo info, when find the cycle, copy the needed
    // edges from edgeToTemp to edgeTo then update the maze.
    public int[] edgeToTemp;
    private Maze maze;


    public MazeCycles(Maze m) {
        super(m);
        maze = m;
        distTo[s] = 0;
        edgeToTemp = new int[maze.V()];
        edgeToTemp[s] = s;
    }

    @Override
    public void solve() {
        // TODO: Your code here!
        dfs(s);
    }

    // Helper methods go here
    private void dfs(int v) {
        marked[v] = true;
        announce();

        for (int w : maze.adj(v)) {
            // check if there is an adjacent w such that w is already visited
            // and w is not parent of v, then there is a cycle in graph.
            if (marked[w] && w != edgeToTemp[v]) {
                cycleFound = true;
                // copy the edges in the cycle from edgeToTemp to edgeTo then update the maze
                edgeTo[w] = v;
                while (edgeToTemp[v] != w) {
                    edgeTo[v] = edgeToTemp[v];
                    v = edgeToTemp[v];
                }
                edgeTo[v] = edgeToTemp[v];
                announce();
                return;
            }
            if (!marked[w]) {
                edgeToTemp[w] = v;
                distTo[w] = distTo[v] + 1;
                dfs(w);
                if (cycleFound) {
                    return;
                }
            }
        }
    }
}

I was stuck there for alomst 2 hours beacuse I thought too much on the going-through process. Actually we only need to detect one cycle by finding a vertice v which has an adjacent that is already visited(marked) and is not parent of v. We don’t need to consider the order in which it crawls the graph. As long as the algrithm go to every vertices that are reachable, the cycle will be found.

A*

Implement the A* algorithm to seek the shortest path from (1, 1) to (N, N). I use a Priority Queue to achieve the algrithm, which is similar to HW4.

/** Estimate of the distance from v to the target. */
private int h(int v) {
    return Math.abs(maze.toX(v) - maze.toX(t)) + Math.abs(maze.toY(v) - maze.toY(t));
}

/** Finds vertex estimated to be closest to target. */
private int findMinimumUnmarked() {
    return -1;
    /* You do not have to use this method. */
}

private class NodeComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer v1, Integer v2) {
        return distTo[v1] + h(v1) - (distTo[v2] + h(v2));
    }
}

private MinPQ<Integer> pq = new MinPQ<>(new NodeComparator());

/** Performs an A star search from vertex s. */
private void astar(int s) {
    // TODO
    int v;
    pq.insert(s);
    while (true) {
        v = pq.delMin();
        marked[v] = true;
        announce();

        if (v == t) {
            return;
        }
        for (int w : maze.adj(v)) {
            if (!marked[w]) {
                pq.insert(w);
                edgeTo[w] = v;
                distTo[w] = distTo[v] + 1;
            }
        }
    }
}

A* considers both the distance from source and estimated distance to target. So it saves some time comparing to Breadth First Search. As the image below shows, it didn’t go to the position 34 on the left side of the bottom intersection as the Breadth First Search did.