graph-traversals.md

Graph Traversals and Properties: Concepts, Algorithms, and Implementations

This document elaborates on Graphs, focusing on traversal algorithms (Depth-First Search (DFS) and Breadth-First Search (BFS)), and properties like connected components and cyclic vs. non-cyclic graphs. Each section includes explanations, algorithms visualized with Mermaid diagrams (using correct syntax), and JavaScript implementations with examples.

Graphs Overview

A Graph is a data structure consisting of nodes (vertices) connected by edges. Graphs can be:

• Directed (edges have direction) or Undirected (edges are bidirectional).
• Weighted (edges have weights) or Unweighted (edges have no weights).
• Cyclic (contains cycles) or Acyclic (no cycles).
• Connected (all vertices reachable from each other in an undirected graph) or Disconnected (contains isolated components).

Traversals are used to explore graphs, and properties like connected components and cyclicity help analyze their structure. This document uses an adjacency list representation for graphs.

Sample Graph

For consistency, we use the following undirected graph in examples and diagrams:

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

Adjacency List:

• A: [B, C, D]
• B: [A, D, E]
• C: [A]
• D: [A, B, E]
• E: [B, D]

Graph Traversals

Breadth-First Search (BFS)

Concept

BFS explores nodes level by level, starting from a given vertex, using a queue. It visits all neighbors of a node before moving to the next level. BFS is useful for finding shortest paths in unweighted graphs and discovering connected components.

Algorithm

1. Initialize an empty queue, a visited set, and a result array.
2. Enqueue the starting vertex and mark it as visited.
3. While the queue is not empty:
   • Dequeue a vertex.
   • Add it to the result.
   • Enqueue all unvisited neighbors and mark them as visited.
4. Return the result array.

Mermaid Diagram

graph TD
    A[Start BFS] --> B[Initialize queue, visited set, result array]
    B --> C[Enqueue start vertex, mark visited]
    C --> D{Queue empty?}
    D -->|No| E[Dequeue vertex]
    E --> F[Add vertex to result]
    F --> G[For each neighbor]
    G --> H{Is neighbor unvisited?}
    H -->|Yes| I[Enqueue neighbor, mark visited]
    I --> D
    H -->|No| D
    D -->|Yes| J[Return result]

Loading

Implementation

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(vertex1, vertex2) {
    this.addVertex(vertex1);
    this.addVertex(vertex2);
    this.adjacencyList.get(vertex1).push(vertex2);
    this.adjacencyList.get(vertex2).push(vertex1); // Undirected
  }

  bfs(start) {
    const queue = [start];
    const visited = new Set([start]);
    const result = [];

    while (queue.length > 0) {
      const vertex = queue.shift();
      result.push(vertex);
      const neighbors = this.adjacencyList.get(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return result;
  }
}

// Example usage
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('D', 'E');
console.log(graph.bfs('A')); // Output: ['A', 'B', 'C', 'D', 'E']

Depth-First Search (DFS)

Concept

DFS explores as far as possible along each branch before backtracking, using recursion or a stack. It is useful for detecting cycles, finding connected components, and topological sorting in directed acyclic graphs (DAGs).

Algorithm

1. Initialize a visited set and a result array.
2. Call a recursive helper function on the starting vertex:
   • Mark the vertex as visited.
   • Add it to the result.
   • Recursively visit all unvisited neighbors.
3. Return the result array.

Mermaid Diagram

graph TD
    A[Start DFS] --> B[Initialize visited set, result array]
    B --> C[Call DFS helper on start vertex]
    C --> D[DFS Helper: vertex]
    D --> E{Is vertex visited?}
    E -->|Yes| F[Return]
    E -->|No| G[Mark vertex visited]
    G --> H[Add vertex to result]
    H --> I[For each neighbor]
    I --> J{Is neighbor unvisited?}
    J -->|Yes| K[Recurse on neighbor]
    K --> I
    J -->|No| I
    I --> L[End helper]
    L --> M[Return result]

Loading

Implementation

class Graph {
  // ... (addVertex and addEdge methods as above)

  dfs(start) {
    const result = [];
    const visited = new Set();
    const adjacencyList = this.adjacencyList;

    function dfsHelper(vertex) {
      visited.add(vertex);
      result.push(vertex);
      const neighbors = adjacencyList.get(vertex);
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          dfsHelper(neighbor);
        }
      }
    }

    dfsHelper(start);
    return result;
  }
}

// Example usage
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('B', 'D');
graph.addEdge('B', 'E');
graph.addEdge('D', 'E');
console.log(graph.dfs('A')); // Output: ['A', 'B', 'D', 'E', 'C']

Connected Components

Concept

In an undirected graph, a connected component is a subgraph where every vertex is reachable from every other vertex within that subgraph. A graph with multiple connected components is disconnected. BFS or DFS can be used to identify all components by running the traversal from each unvisited vertex.

Algorithm

1. Initialize a visited set and a components array.
2. For each vertex in the graph:
   • If unvisited, run BFS (or DFS) from that vertex to find all reachable vertices.
   • Add the result as a new component.
3. Return the components array.

Mermaid Diagram

graph TD
    A[Start Connected Components] --> B[Initialize visited set, components array]
    B --> C[For each vertex in graph]
    C --> D{Is vertex unvisited?}
    D -->|Yes| E[Run BFS/DFS from vertex]
    E --> F[Add result to components]
    F --> C
    D -->|No| C
    C --> G[Return components]

Loading

Implementation

class Graph {
  // ... (addVertex, addEdge, bfs methods as above)

  connectedComponents() {
    const visited = new Set();
    const components = [];

    for (const vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        const component = this.bfs(vertex);
        components.push(component);
        for (const v of component) {
          visited.add(v);
        }
      }
    }
    return components;
  }
}

// Example usage: Disconnected graph with two components
const graph = new Graph();
graph.addEdge('A', 'B'); // Component 1: A-B
graph.addEdge('C', 'D'); // Component 2: C-D
console.log(graph.connectedComponents()); // Output: [['A', 'B'], ['C', 'D']]

Cyclic vs. Non-Cyclic Graphs

Concept

A graph is cyclic if it contains at least one cycle (a path starting and ending at the same vertex). A non-cyclic graph (acyclic) has no cycles, e.g., trees or DAGs. Cycle detection can be performed using DFS by checking for back edges to visited vertices (excluding the parent in undirected graphs).

Algorithm (Cycle Detection using DFS)

1. Initialize a visited set and a recursion stack (to track vertices in the current DFS path).
2. For each vertex, if unvisited:
   • Run DFS helper:
     • Mark vertex as visited and add to recursion stack.
     • For each neighbor:
       • If unvisited, recurse; if recursion returns true, a cycle exists.
       • If visited and in recursion stack, a cycle exists.
     • Remove vertex from recursion stack.
3. Return true if a cycle is found, false otherwise.

Mermaid Diagram

graph TD
    A[Start Cycle Detection] --> B[Initialize visited set, recursion stack]
    B --> C[For each vertex]
    C --> D{Is vertex unvisited?}
    D -->|Yes| E[DFS Helper: vertex]
    E --> F[Mark visited, add to recursion stack]
    F --> G[For each neighbor]
    G --> H{Is neighbor unvisited?}
    H -->|Yes| I[Recurse on neighbor]
    I -->|Cycle found| J[Return true]
    H -->|No| K{Is neighbor in recursion stack?}
    K -->|Yes| J
    K -->|No| G
    G --> L[Remove vertex from recursion stack]
    L --> M[Return false]
    D -->|No| C
    C --> N[Return false if no cycles]

Loading

Implementation

class Graph {
  // ... (addVertex, addEdge methods as above)

  hasCycle() {
    const visited = new Set();
    const recStack = new Set();

    function dfsHelper(vertex, parent) {
      visited.add(vertex);
      recStack.add(vertex);

      const neighbors = this.adjacencyList.get(vertex) || [];
      for (const neighbor of neighbors) {
        if (!visited.has(neighbor)) {
          if (dfsHelper.call(this, neighbor, vertex)) return true;
        } else if (neighbor !== parent && recStack.has(neighbor)) {
          return true;
        }
      }

      recStack.delete(vertex);
      return false;
    }

    for (const vertex of this.adjacencyList.keys()) {
      if (!visited.has(vertex)) {
        if (dfsHelper.call(this, vertex, null)) return true;
      }
    }
    return false;
  }
}

// Example usage
// Cyclic graph
const cyclicGraph = new Graph();
cyclicGraph.addEdge('A', 'B');
cyclicGraph.addEdge('B', 'C');
cyclicGraph.addEdge('C', 'A'); // Creates cycle
console.log(cyclicGraph.hasCycle()); // Output: true

// Acyclic graph (tree)
const acyclicGraph = new Graph();
acyclicGraph.addEdge('A', 'B');
acyclicGraph.addEdge('A', 'C');
acyclicGraph.addEdge('B', 'D');
console.log(acyclicGraph.hasCycle()); // Output: false

Summary

• BFS: Explores level by level, ideal for shortest paths and connected components. Time complexity: O(V + E), Space complexity: O(V).
• DFS: Explores branch by branch, useful for cycle detection and topological sorting. Time complexity: O(V + E), Space complexity: O(V).
• Connected Components: Identifies isolated subgraphs using BFS or DFS. Time complexity: O(V + E).
• Cyclic vs. Non-Cyclic: Detects cycles using DFS with a recursion stack. Time complexity: O(V + E).
• Applications:
  • BFS: Shortest path, network broadcasting.
  • DFS: Cycle detection, topological sorting.
  • Connected Components: Network analysis, clustering.
  • Cycle Detection: Dependency analysis, deadlock detection.

The Mermaid diagrams use correct syntax, avoiding colons and other problematic characters in node labels. The JavaScript implementations provide functional code for traversals, connected components, and cycle detection, with examples demonstrating their usage on sample graphs.