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 JavaScript:

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  
  addEdge(vertex1, vertex2) {
    // For undirected graph
    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }
  
  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1]
      .filter(v => v !== vertex2);
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2]
      .filter(v => v !== vertex1);
  }
  
  removeVertex(vertex) {
    while(this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[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 JavaScript:

class GraphMatrix {
  constructor(numVertices) {
    this.numVertices = numVertices;
    // Initialize matrix with zeros
    this.matrix = Array(numVertices).fill()
      .map(() => Array(numVertices).fill(0));
  }
  
  // Add edge for undirected graph
  addEdge(v1, v2) {
    // Set values to 1 to indicate an edge
    this.matrix[v1][v2] = 1;
    this.matrix[v2][v1] = 1; // Remove this line for directed graph
  }
  
  // Add edge with weight
  addWeightedEdge(v1, v2, weight) {
    this.matrix[v1][v2] = weight;
    this.matrix[v2][v1] = weight; // Remove this line for directed graph
  }
  
  // Remove edge
  removeEdge(v1, v2) {
    this.matrix[v1][v2] = 0;
    this.matrix[v2][v1] = 0; // Remove this line for directed graph
  }
  
  // Check if there is an edge between vertices
  hasEdge(v1, v2) {
    return this.matrix[v1][v2] !== 0;
  }
  
  // Get all adjacent vertices of a vertex
  getAdjacentVertices(v) {
    const adjacent = [];
    for (let i = 0; i < this.numVertices; i++) {
      if (this.matrix[v][i] !== 0) {
        adjacent.push(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:

class Graph {
  // ... previous methods ...
  
  depthFirstTraversal(start) {
    const result = [];
    const visited = {};
    
    // Helper function to perform recursive DFT
    const dfs = (vertex) => {
      if (!vertex) return null;
      
      // Mark as visited and add to result
      visited[vertex] = true;
      result.push(vertex);
      
      // Visit all neighbors
      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    };
    
    // Start traversal
    dfs(start);
    return result;
  }
  
  // Iterative implementation using stack
  depthFirstIterative(start) {
    const stack = [start];
    const result = [];
    const visited = {};
    visited[start] = true;
    
    while (stack.length) {
      const currentVertex = stack.pop();
      result.push(currentVertex);
      
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    
    return result;
  }
}

Applications of DFT:

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