Module 1: Graphs I

Understanding Graphs

A graph is a data structure consisting of vertices (nodes) and edges that connect these vertices. Graphs are highly versatile and can represent many real-world relationships and networks.

Types of Graphs:

• Directed Graph: Edges have a specific direction (one-way connections)
• Undirected Graph: Edges have no direction (two-way connections)
• Weighted Graph: Edges have associated weights/values
• Cyclic Graph: Contains at least one cycle (a path that starts and ends at the same vertex)
• Acyclic Graph: Contains no cycles
• Connected Graph: There is a path between any two vertices

Real-world Applications:

• Social networks (friends as vertices, connections as edges)
• Road maps (intersections as vertices, roads as edges)
• Computer networks (devices as vertices, connections as edges)
• Recommendation systems (users/items as vertices, preferences as edges)

Adjacency Lists Explained

An adjacency list is one of the most common ways to represent a graph. It uses an array or object where each vertex is associated with a list of its adjacent vertices (neighbors).

Implementation in Java:

import java.util.*;

public class Graph {
    private Map<String, List<String>> adjacencyList = new HashMap<>();

    public void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String vertex1, String vertex2) {
        adjacencyList.get(vertex1).add(vertex2);
        adjacencyList.get(vertex2).add(vertex1);
    }

    public void removeEdge(String vertex1, String vertex2) {
        adjacencyList.get(vertex1).remove(vertex2);
        adjacencyList.get(vertex2).remove(vertex1);
    }

    public void removeVertex(String vertex) {
        List<String> neighbors = new ArrayList<>(adjacencyList.get(vertex));
        for (String neighbor : neighbors) {
            removeEdge(vertex, neighbor);
        }
        adjacencyList.remove(vertex);
    }
}

Time Complexity:

• Add Vertex: O(1)
• Add Edge: O(1)
• Remove Edge: O(E) where E is the number of edges
• Remove Vertex: O(V + E) where V is the number of vertices and E is the number of edges
• Space Complexity: O(V + E)

Adjacency Matrices Explained

An adjacency matrix is a 2D array where rows and columns represent vertices. The value at matrix[i][j] indicates if there is an edge from vertex i to vertex j.

Implementation in Java:

import java.util.*;

public class GraphMatrix {
    private int numVertices;
    private int[][] matrix;

    public GraphMatrix(int numVertices) {
        this.numVertices = numVertices;
        this.matrix = new int[numVertices][numVertices];
    }

    // Add edge for undirected graph
    public void addEdge(int v1, int v2) {
        matrix[v1][v2] = 1;
        matrix[v2][v1] = 1; // Remove for directed graph
    }

    // Add edge with weight
    public void addWeightedEdge(int v1, int v2, int weight) {
        matrix[v1][v2] = weight;
        matrix[v2][v1] = weight; // Remove for directed graph
    }

    // Remove edge
    public void removeEdge(int v1, int v2) {
        matrix[v1][v2] = 0;
        matrix[v2][v1] = 0; // Remove for directed graph
    }

    // Check if there is an edge between vertices
    public boolean hasEdge(int v1, int v2) {
        return matrix[v1][v2] != 0;
    }

    // Get all adjacent vertices of a vertex
    public List<Integer> getAdjacentVertices(int v) {
        List<Integer> adjacent = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            if (matrix[v][i] != 0) {
                adjacent.add(i);
            }
        }
        return adjacent;
    }
}

Comparison with Adjacency Lists:

• Adjacency Matrix:
  • Space Complexity: O(V²)
  • Checking if two vertices are connected: O(1)
  • Better for dense graphs
• Adjacency List:
  • Space Complexity: O(V + E)
  • Checking if two vertices are connected: O(V) worst case
  • Better for sparse graphs

Depth-First Traversal (DFT) Explained

Depth-First Traversal is an algorithm used to explore nodes and edges of a graph. It starts at a source node and explores as far as possible along each branch before backtracking.

Recursive Implementation:

import java.util.*;

public class Graph {
    // ... previous methods ...
  
    public List<String> depthFirstTraversal(String start) {
        List<String> result = new ArrayList<>();
        Map<String, Boolean> visited = new HashMap<>();
        Map<String, List<String>> adjacencyList = this.adjacencyList;

        (function dfs(vertex) {
            if (!vertex) return null;
            visited.put(vertex, true);
            result.add(vertex);
            adjacencyList.get(vertex).forEach(neighbor -> {
                if (!visited.get(neighbor)) {
                    return dfs(neighbor);
                }
            });
        })(start);

        return result;
    }
  
    // Iterative implementation using stack
    public List<String> depthFirstIterative(String start) {
        List<String> stack = new ArrayList<>();
        List<String> result = new ArrayList<>();
        Map<String, Boolean> visited = new HashMap<>();
        visited.put(start, true);
        
        stack.add(start);
        
        while (!stack.isEmpty()) {
            String currentVertex = stack.remove(stack.size() - 1);
            result.add(currentVertex);
            
            adjacencyList.get(currentVertex).forEach(neighbor -> {
                if (!visited.get(neighbor)) {
                    visited.put(neighbor, true);
                    stack.add(neighbor);
                }
            });
        }
        
        return result;
    }
}

Applications of DFT:

• Detecting cycles in a graph
• Topological sorting
• Finding connected components
• Solving mazes and puzzles
• Path finding algorithms