CS61B: Lecture 23

BFS, DFS, Graph Traversals and Implementations

• To implement any graph algorithms like DFS, we need:
  • An API (Application Programming Interface) for graphs.
    • Defines a set of protocols for how Graph programmers must think.
  • A concrete data structure to represent graphs.

Graph API

• Common Convention: We have number nodes assigned to each node, and use numbers throughout the graph implementation.
  • Looking up a vertex by label needs a Map<Label, Integer>

public class Graph {
    public Graph(int V):                // Create empty grpah with v vertices
    public void addEdge(int v; int w):  // Adds an edge v-w
    Iterable<Integer> adj(int v):       // vertices adjacent to v
    int V():                            // number of vertices
    int E():                            // number of edges
}

• Restrictions about our class
  • Number of vertices must be specified in advance
  • Does not support weights or labels on nodes or edges.
  • Has no method for getting the number of edges for a vertex (the degree of a vertex).

public static int degree(Graph G, int v) {
    int degree = 0;
    for (int u : graph.adj(v)) {
        degree++;
    }
    return degree;
}

public static void print(Graph G) {
    for (int v; v < G.V(); v++) {
        for (int u : G.adj(u)) {
            // Print each edge once
            if (u > v) {
                System.out.println(v + " - " + u);
            }
        }
    }
}

Depth First Search Implementations

• We create a wrapper class for a graph for the operations that we want to perform operations on.
  • We have a specialized class for each type of question that we want to address
  • Ex: Paths.
    • We create a graph object
    • Pass the graph to a graph-processing method (or constructor) in a client class.
    • Query te client class for information.

public class Paths {
    public Paths(Graph G, int s):
    boolean hasPathTo(int v):
    Iterable<Integer> pathTo(int v):
}

• This wrapper class has access to the underlaying graph structure, but we may add another layer of abstraction by adding more helper methods.
• Recall s-t Connectivity
  • connected(s, t):
    • Mark s.
    • Does s == t? If so, return true.
    • Otherwise, if connected(v,t) for any unmarked neighbor v or s, return true.
    • Return false.

public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private int s;

    public DepthFirstPaths(Graph G, int s) {
        // Create a data structure for our graph G
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        // Mark the current vertex as visited
        marked[v] = true;
        for (int w: G.adj(v)) {
            // Visit each unmarked vertex w
            if (!marked[w]) {
                // Set our vertex as the neighbor of w
                edgeTo[w] = v;
                // Recurse on w
                dfs(G, w)
            }
        }
    }

    public boolean hasPathTo(int v) {
        // If we have traveled vertex through dfs, then there is a path
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        // No path
        if (!hasPathTo(v)) return null;
        for (int x = v; x != s; s = edgeTo[x]) {
            path.add(x);
        }
        path.add(s);
        Collections.reverse(path);
        return path;
    }
}

Different Graph Implementations

• Adjacency Matrix
  • We keep a 2-Dimensional array where each index (v, w) represents the presence or the absense of an edge between vertices v and w.
    • Very fast constant time look up but $O(N^2)$ space complexity
• Edge Sets:
  • We have a collection of all edges.
  • HashSet, where each Edge is a pair of ints.
• Adjacency lists:
  • Maintain an array of lists index by vertex number.
  • This is efficient when graphs are “sparse”
• Whichever graph implementation we choose has implications on our runtime.

Breadth First Search Implementation

• Unlike Depth First search, we propagate our search through different levels of the graph relative to some fringe node.
• For each vertex, we keep track of:
  • marked: If the vertex has been marked.
  • edgeTo: What vertex is the vertex connected to in our BFS propagation.
  • distTo: The total distance of our vertex to our fringe vertex.
• Since we go one layer at a time, we guarantee that the paths we find are the fasts paths.
• Breadth first search is $O(V+E)$