Graph Data Structure

Interactive visualizer for graph data structures using adjacency list representation with add/remove vertices and edges

Graph Data Structure

Graphs are non-linear data structures consisting of vertices (nodes) and edges (connections between vertices). They are used to represent networks, relationships, and connections in various applications.

Try It Out

Experiment with the interactive graph visualizer:

Graph Visualizer

Add vertices, create edges, and visualize the adjacency list representation in real-time

Graph Representations

Adjacency List

An adjacency list uses a collection where each vertex stores a list of its adjacent vertices. This is the representation used in our visualizer.

Structure:

• Main container: Object/HashMap storing all vertices
• Each vertex: Key in the object with an array of connected nodes
• Each edge: Node object in the adjacency list

Advantages:

• Space efficient: O(V + E) space
• Fast vertex addition: O(1)
• Fast edge addition: O(1)
• Better for sparse graphs

Disadvantages:

• Slower edge lookup: O(E) in worst case
• Checking if edge exists requires traversing the list

Adjacency Matrix

An adjacency matrix uses a 2D array where matrix[i][j] indicates whether there’s an edge from vertex i to vertex j.

Advantages:

• Fast edge lookup: O(1)
• Fast edge removal: O(1)
• Better for dense graphs

Disadvantages:

• Space intensive: O(V²) space
• Slower vertex addition: O(V²)
• Wastes space for sparse graphs

Implementation

Node Structure

Each node in the adjacency list is represented as a Node object:

class Node<T> {
  value: T;
  private id: string;

  constructor(value: T) {
    this.value = value;
    this.id = "id" + Node._id++;
  }

  render(): JSX.Element {
    // Renders the node with animations
    return (
      <motion.div className="nodeValue">
        {this.value}
      </motion.div>
    );
  }
}

Graph Interface

The graph is represented as an object mapping vertex labels to arrays of nodes:

interface IGraph {
  [vertex: string]: Array<Node<string>>;
}

Operations

1. Add Vertex

   Creates a new vertex in the graph. Each vertex is unique and starts with an empty adjacency list.

   const addVertex = (label: string) => {
     setGraph({ ...graph, [label]: [] });
   };
   

   Time Complexity: O(1) with object/HashMap

   Space Complexity: O(1)

   The visualizer prevents adding duplicate vertices. Each vertex must have a unique label.

2. Add Edge

   Creates a directed edge from one vertex to another. The edge is stored in the source vertex’s adjacency list.

   const addEdge = (from: string, to: string) => {
     if (from === to) return; // Prevent self-loops
     if (!graph[from] || !graph[to]) return; // Both vertices must exist
     if (graph[from].find((node) => node.value === to)) return; // Prevent duplicates
   
     setGraph({ 
       ...graph, 
       [from]: [...graph[from], new Node(to)] 
     });
   };
   

   Time Complexity: O(V) - checking for duplicate edges

   Space Complexity: O(1)

   This creates a directed graph. For an undirected graph, you would need to add edges in both directions.

3. Remove Edge

   Removes the connection between two vertices by finding and removing the target node from the source vertex’s adjacency list.

   const removeEdge = (from: string, to: string) => {
     if (from === to) return;
     if (!graph[from] || !graph[to]) return;
   
     const nodeIndex = graph[from].findIndex(
       (node) => node.value === to
     );
   
     if (nodeIndex === -1) return;
   
     graph[from].splice(nodeIndex, 1);
     setGraph({ ...graph, [from]: [...graph[from]] });
   };
   

   Time Complexity: O(E) - finding the edge in adjacency list

   Space Complexity: O(1)

4. Remove Vertex

   Removes a vertex and all edges connected to it. This requires removing the vertex itself and cleaning up all references in other vertices’ adjacency lists.

   const removeVertex = (label: string) => {
     if (!graph[label]) return;
   
     const newGraph = { ...graph };
     delete newGraph[label]; // Remove the vertex
   
     // Remove all edges pointing to this vertex
     for (const key in newGraph) {
       const nodeIndex = newGraph[key].findIndex(
         (node) => node.value === label
       );
       if (nodeIndex !== -1) {
         newGraph[key].splice(nodeIndex, 1);
       }
     }
   
     setGraph(newGraph);
   };
   

   Time Complexity: O(V × E) - iterating through all vertices and their edges

   Space Complexity: O(1)

   This is the most expensive operation because it must clean up all references to the removed vertex across the entire graph.

Complexity Analysis

Space Complexity

Overall Graph Storage: O(V + E)

• V vertices stored in the main object
• E edges stored across all adjacency lists

With HashMap optimization: Using a HashMap for vertex storage provides O(1) lookup instead of O(V) with a linked list.

Time Complexity Summary

Operation	Time Complexity	With HashMap
Add Vertex	O(V)	O(1)
Remove Vertex	O(V × E)	O(V + E)
Add Edge	O(V)	O(1)
Remove Edge	O(V + E)	O(E)

The visualizer uses an object (similar to HashMap) for fast vertex lookups, achieving the optimized complexities.

Visualization Features

The interactive visualizer displays:

Vertices

Each vertex is displayed as a colored box with its label, showing all vertices in the graph

Adjacency Lists

For each vertex, the connected vertices are shown horizontally, representing the adjacency list

Animations

Smooth animations when adding or removing vertices and edges using Framer Motion

Directed Edges

The visualization shows directed edges (one-way connections) from source to target vertices

Use Cases

Graphs are used to model:

• Social Networks: Users as vertices, friendships as edges
• Web Pages: Pages as vertices, hyperlinks as edges
• Maps: Locations as vertices, roads as edges
• Dependencies: Tasks as vertices, dependencies as edges
• Network Routing: Routers as vertices, connections as edges

Next Steps

Graph Traversals

Learn BFS and DFS algorithms for traversing graphs

Try the Visualizer

Practice building graphs with the interactive tool

Key Takeaways

• Adjacency lists are space-efficient for sparse graphs
• Choose adjacency list vs. matrix based on your use case (sparse vs. dense graphs)
• Vertex removal is expensive because all edge references must be cleaned up
• The implementation uses a directed graph (one-way edges)