How Algorithms Work
Chapter 5 Graphs

Chapter 5: Graphs in Algorithms

Graphs are a fundamental data structure that model connections and relationships between objects. They have wide-ranging applications in computer science and beyond, from modeling social networks and web page links, to solving problems in transportation, scheduling, and resource allocation. In this chapter, we explore the basic properties and algorithms for working with graphs, focusing on undirected graphs, depth-first and breadth-first search, minimum spanning trees, and shortest paths.

Undirected Graphs

An undirected graph is a set of vertices (or nodes) connected by edges. Formally, we define an undirected graph G as a pair (V, E), where V is a set of vertices and E is a set of unordered pairs of vertices, called edges. An edge (v, w) connects vertices v and w. We say that v and w are adjacent or neighbors. The degree of a vertex is the number of edges incident to it.

Here is a simple example of an undirected graph:

   A --- B
  /     / \
 /     /   \
C --- D --- E

In this graph, the set of vertices V = {A, B, C, D, E} and the set of edges E = {(A, B), (A, C), (B, D), (B, E), (C, D), (D, E)}.

There are several ways to represent a graph in a program. Two common representations are:

  1. Adjacency Matrix: An n x n boolean matrix A, where n is the number of vertices. The entry A[i][j] is true if there is an edge from vertex i to vertex j, and false otherwise.

  2. Adjacency Lists: An array Adj of size n, where n is the number of vertices. The entry Adj[v] is a list containing the neighbors of v.

The choice of representation depends on the graph's density (ratio of edges to vertices) and the operations we need to perform. Adjacency matrices are simple but can be inefficient for sparse graphs. Adjacency lists are more space-efficient for sparse graphs and provide faster access to a vertex's neighbors.

Here's an example of how we might represent the above graph using adjacency lists in Java:

List<Integer>[] graph = (List<Integer>[]) new List[5];
graph[0] = Arrays.asList(1, 2);        // A -> B, C
graph[1] = Arrays.asList(0, 3, 4);     // B -> A, D, E
graph[2] = Arrays.asList(0, 3);        // C -> A, D
graph[3] = Arrays.asList(1, 2, 4);     // D -> B, C, E
graph[4] = Arrays.asList(1, 3);        // E -> B, D

Depth-First Search (DFS)

Depth-first search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be used to solve many graph problems, such as finding connected components, topological sorting, and detecting cycles.

The DFS algorithm works as follows:

  1. Start at a source vertex s.
  2. Mark the current vertex as visited.
  3. Recursively visit all unmarked vertices w adjacent to the current vertex.
  4. If all vertices adjacent to the current vertex have been visited, backtrack to the vertex from which the current vertex was explored.
  5. If any vertices remain unmarked, select one and repeat from step 1.

Here's a simple Java implementation of DFS using adjacency lists:

boolean[] visited;
 
void dfs(List<Integer>[] graph, int v) {
    visited[v] = true;
    for (int w : graph[v]) {
        if (!visited[w]) {
            dfs(graph, w);
        }
    }
}

To perform a full DFS traversal, we call dfs(graph, s) for each vertex s in the graph, where visited is initialized to false for all vertices.

DFS has many applications. For example, we can use it to find connected components in an undirected graph by running DFS from each unvisited vertex and assigning each vertex to a component based on the DFS tree.

Breadth-First Search (BFS)

Breadth-first search (BFS) is another fundamental graph traversal algorithm that explores vertices in layers. It visits all vertices at the current depth before moving on to vertices at the next depth level.

The BFS algorithm works as follows:

  1. Start at a source vertex s and mark it as visited.
  2. Enqueue s into a FIFO queue.
  3. While the queue is not empty:
    • Dequeue a vertex v.
    • For each unmarked vertex w adjacent to v:
      • Mark w as visited.
      • Enqueue w.

Here's a Java implementation of BFS using adjacency lists:

boolean[] visited;
 
void bfs(List<Integer>[] graph, int s) {
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.offer(s);
 
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph[v]) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

BFS is particularly useful for finding shortest paths in unweighted graphs. The distance from the source vertex to any other vertex is the minimum number of edges in a path between them. BFS guarantees to find the shortest path.

Minimum Spanning Trees

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices, without any cycles and with the minimum possible total edge weight.

Two classic algorithms for finding MSTs are Kruskal's algorithm and Prim's algorithm.

Kruskal's algorithm works as follows:

  1. Create a forest F where each vertex is a separate tree.
  2. Create a set S containing all the edges in the graph.
  3. While S is nonempty and F is not yet a spanning tree:
    • Remove an edge with minimum weight from S.
    • If the removed edge connects two different trees, add it to F, combining two trees into a single tree.

Prim's algorithm works as follows:

  1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
  2. Grow the tree by one edge: of all the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
  3. Repeat step 2 until all vertices are in the tree.

Here's a Java implementation of Prim's algorithm:

int minKey(int[] key, boolean[] mstSet, int V) {
    int min = Integer.MAX_VALUE, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
 
void primMST(int[][] graph, int V) {
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        key[i] = Integer.MAX_VALUE;
        mstSet[i] = false;
    }
 
    key[0] = 0;
    parent[0] = -1;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
 
    printMST(parent, graph, V);
}

MSTs have many applications, such as designing networks (communication, electrical, hydraulic, computer) and approximating traveling salesman problems.

Shortest Paths

The shortest path problem is to find a path between two vertices in a graph such that the sum of the weights of its edges is minimized. This problem has many variations, such as single-source shortest paths, all-pairs shortest paths, and single-destination shortest paths.

Dijkstra's algorithm is a greedy algorithm that solves the single-source shortest paths problem for a graph with non-negative edge weights. It works as follows:

  1. Create a set sptSet (shortest path tree set) that keeps track of vertices included in the shortest path tree.
  2. Assign a distance value to all vertices in the graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex.
  3. While sptSet doesn't includeall vertices, pick a vertex v which is not there in sptSet and has minimum distance value. Include v to sptSet.

Update dist value of all adjacent vertices of v. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex w, if sum of distance value of v (from source) and weight of edge v-w, is less than the distance value of w, then update the distance value of w.

Here's a Java implementation of Dijkstra's algorithm:

public void dijkstra(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
    boolean[] sptSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        dist[i] = Integer.MAX_VALUE;
        sptSet[i] = false;
    }
 
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    printSolution(dist);
}

The Bellman-Ford algorithm is another algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted digraph. Unlike Dijkstra's algorithm, the Bellman-Ford algorithm can handle graphs with negative edge weights, as long as there are no negative cycles.

The algorithm works as follows:

  1. Initialize distances from the source to all vertices as infinite and distance to the source itself as 0.
  2. Relax all edges |V| - 1 times. For each edge u-v, if the distance to v can be shortened by taking the edge u-v, update the distance to v.
  3. Check for negative-weight cycles. Run a step of relaxation for all edges. If any distance changes, then there is a negative weight cycle.

Here's a Java implementation of the Bellman-Ford algorithm:

public void bellmanFord(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
 
    for (int i = 0; i < V; i++)
        dist[i] = Integer.MAX_VALUE;
    dist[src] = 0;
 
    for (int i = 1; i < V; i++) {
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
 
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                System.out.println("Graph contains negative weight cycle");
                return;
            }
        }
    }
 
    printSolution(dist);
}

Shortest paths algorithms have numerous applications, such as in navigation systems, network routing protocols, and transportation planning. They are fundamental tools in graph theory and are essential in many graph processing tasks.

Conclusion

Graphs are versatile and powerful data structures that can model a wide variety of problems. In this chapter, we explored the basic properties and types of graphs, and studied fundamental graph algorithms including depth-first search, breadth-first search, minimum spanning trees, and shortest paths.

Depth-first search and breadth-first search provide systematic ways to explore a graph, and form the basis for many advanced graph algorithms. Minimum spanning tree algorithms like Kruskal's and Prim's find a tree that connects all vertices with minimum total edge weight. Shortest path algorithms like Dijkstra's and Bellman-Ford find paths of minimum weight between vertices.

Understanding these core concepts and algorithms is crucial for working effectively with graphs and tackling complex problems in various domains. As you progress further in your study of algorithms, you will encounter more advanced graph algorithms that build upon these foundational techniques.

Graphs provide a powerful language for describing and solving problems in computer science and beyond. Mastering graph algorithms will equip you with a versatile toolset for modeling and solving a broad range of computational challenges.

Chapter 4 Searching AlgorithmsChapter 6 Strings