Graphs I: Guided Project

Graph Representations

There are two common ways to represent a graph in code:

1. Adjacency List

A collection of lists or maps where each vertex stores its neighboring vertices.

// Using HashMap for adjacency list
Map> adjacencyList = new HashMap<>();

// Example of a simple graph:
//   A --- B
//   |     |
//   |     |
//   C --- D

adjacencyList.put("A", Arrays.asList("B", "C"));
adjacencyList.put("B", Arrays.asList("A", "D"));
adjacencyList.put("C", Arrays.asList("A", "D"));
adjacencyList.put("D", Arrays.asList("B", "C"));

2. Adjacency Matrix

A 2D matrix where cell [i][j] indicates if vertex i is connected to vertex j.

// Using a 2D array for adjacency matrix
// 1 indicates an edge, 0 indicates no edge
int[][] adjacencyMatrix = {
    {0, 1, 1, 0}, // A's connections: B, C
    {1, 0, 0, 1}, // B's connections: A, D
    {1, 0, 0, 1}, // C's connections: A, D
    {0, 1, 1, 0}  // D's connections: B, C
};

Implementation Steps

1. 1

   Create Graph Structure

   Define the basic graph class with vertex and edge management

   public class Graph {
       private Map> adjacencyList;
       
       public Graph() {
           adjacencyList = new HashMap<>();
       }
       
       // Add a vertex to the graph
       public void addVertex(String vertex) {
           if (!adjacencyList.containsKey(vertex)) {
               adjacencyList.put(vertex, new ArrayList<>());
           }
       }
       
       // Print the adjacency list (for debugging)
       public void printGraph() {
           for (String vertex : adjacencyList.keySet()) {
               System.out.print(vertex + " -> ");
               System.out.println(String.join(", ", adjacencyList.get(vertex)));
           }
       }
   }

2. 2

   Implement Graph Operations

   Add methods for adding/removing vertices and edges

   // Add an edge between two vertices (undirected graph)
   public void addEdge(String source, String destination) {
       // Ensure both vertices exist
       addVertex(source);
       addVertex(destination);
       
       // Add edge in both directions (for undirected graph)
       adjacencyList.get(source).add(destination);
       adjacencyList.get(destination).add(source);
   }
   
   // Remove an edge between two vertices
   public void removeEdge(String source, String destination) {
       if (adjacencyList.containsKey(source) && adjacencyList.containsKey(destination)) {
           adjacencyList.get(source).remove(destination);
           adjacencyList.get(destination).remove(source);
       }
   }
   
   // Remove a vertex and all its edges
   public void removeVertex(String vertex) {
       if (!adjacencyList.containsKey(vertex)) {
           return;
       }
       
       // Remove all edges to this vertex from other vertices
       for (String adjacentVertex : adjacencyList.get(vertex)) {
           adjacencyList.get(adjacentVertex).remove(vertex);
       }
       
       // Remove the vertex itself
       adjacencyList.remove(vertex);
   }

3. 3

   Add Traversal Methods

   Implement depth-first and breadth-first traversals

   // Depth-First Search (DFS)
   public void depthFirstSearch(String startVertex) {
       if (!adjacencyList.containsKey(startVertex)) {
           return;
       }
       
       Set visited = new HashSet<>();
       dfsHelper(startVertex, visited);
   }
   
   private void dfsHelper(String vertex, Set visited) {
       // Mark current vertex as visited and print it
       visited.add(vertex);
       System.out.print(vertex + " ");
       
       // Recursively visit all adjacent vertices
       for (String adjacentVertex : adjacencyList.get(vertex)) {
           if (!visited.contains(adjacentVertex)) {
               dfsHelper(adjacentVertex, visited);
           }
       }
   }
   
   // Breadth-First Search (BFS)
   public void breadthFirstSearch(String startVertex) {
       if (!adjacencyList.containsKey(startVertex)) {
           return;
       }
       
       Set visited = new HashSet<>();
       Queue queue = new LinkedList<>();
       
       // Start with the given vertex
       visited.add(startVertex);
       queue.add(startVertex);
       
       while (!queue.isEmpty()) {
           // Dequeue a vertex and print it
           String currentVertex = queue.poll();
           System.out.print(currentVertex + " ");
           
           // Visit all adjacent vertices
           for (String adjacentVertex : adjacencyList.get(currentVertex)) {
               if (!visited.contains(adjacentVertex)) {
                   visited.add(adjacentVertex);
                   queue.add(adjacentVertex);
               }
           }
       }
   }

Visual Example: Graph Traversal

Consider the following graph:

    A --- B
    |     |
    |     |
    C --- D

Depth-First Search (DFS) starting from A:

Traversal order: A → B → D → C

Explanation:

1. Start at A, mark as visited
2. Visit first neighbor B, mark as visited
3. Visit B's first unvisited neighbor D, mark as visited
4. Visit D's first unvisited neighbor C, mark as visited
5. All vertices visited, DFS complete

Breadth-First Search (BFS) starting from A:

Traversal order: A → B → C → D

Explanation:

1. Start at A, mark as visited, add to queue
2. Dequeue A, visit all its neighbors (B, C), mark as visited, add to queue
3. Dequeue B, visit unvisited neighbor D, mark as visited, add to queue
4. Dequeue C, all neighbors already visited
5. Dequeue D, all neighbors already visited
6. Queue empty, BFS complete

Advanced Features: Weighted Graphs

To represent a weighted graph, we can modify our adjacency list to store both the destination vertex and the weight of the edge:

public class WeightedGraph {
    // Map of vertex to list of its edges (destination and weight)
    private Map> adjacencyList;
    
    // Inner class to represent an edge
    private class Edge {
        String destination;
        int weight;
        
        public Edge(String destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }
    
    public WeightedGraph() {
        adjacencyList = new HashMap<>();
    }
    
    public void addVertex(String vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new ArrayList<>());
        }
    }
    
    public void addEdge(String source, String destination, int weight) {
        addVertex(source);
        addVertex(destination);
        
        // Add edge in both directions (for undirected graph)
        adjacencyList.get(source).add(new Edge(destination, weight));
        adjacencyList.get(destination).add(new Edge(source, weight));
    }
}

Performance Considerations

• Adjacency List:
  • Space Complexity: O(V + E) where V is number of vertices and E is number of edges
  • Time Complexity for Adding Vertex: O(1)
  • Time Complexity for Adding Edge: O(1)
  • Time Complexity for Checking if two vertices are connected: O(V) in worst case
  • Good for sparse graphs (few edges)
• Adjacency Matrix:
  • Space Complexity: O(V²) regardless of number of edges
  • Time Complexity for Adding Vertex: O(V²) (need to resize matrix)
  • Time Complexity for Adding Edge: O(1)
  • Time Complexity for Checking if two vertices are connected: O(1)
  • Good for dense graphs (many edges)

Exercise 1: Graph Creation

Implement a Graph class with methods to add vertices and edges.

public class Graph {
    // Your adjacency list implementation here
    
    public void addVertex(String vertex) {
        // Add implementation
    }
    
    public void addEdge(String source, String destination) {
        // Add implementation
    }
}

Exercise 2: Graph Traversal

Implement depth-first search (DFS) traversal starting from a given vertex.

public void depthFirstSearch(String startVertex) {
    // Your implementation here
    // Remember to use a set to track visited vertices
}

Exercise 3: Path Finding

Implement a method to find if a path exists between two vertices.

public boolean hasPath(String source, String destination) {
    // Your implementation here
    // Use either DFS or BFS approach
}

Exercise 4: Connected Components

Find all connected components in an undirected graph.

public List> findConnectedComponents() {
    // Your implementation here
    // Hint: Perform DFS or BFS starting from each unvisited vertex
}

Exercise 5: Cycle Detection

Implement a method to detect if the graph contains a cycle.

public boolean hasCycle() {
    // Your implementation here
    // Hint: Modify DFS to detect back edges
}

Exercise 6: Advanced - Bipartite Graph Check

Determine if a graph is bipartite (can be divided into two sets where no vertices in the same set are adjacent).

public boolean isBipartite() {
    // Your implementation here
    // Hint: Try coloring the graph with two colors
}