Interactive Graph Builder
Build a graph by adding nodes and edges, and see its representation as an Adjacency List and Adjacency Matrix.
Add nodes and edges to build your graph.
Graph Representations Explained
Graphs can be represented in several ways, each with trade-offs in terms of space complexity and efficiency for different operations.
-
Adjacency List:
- Represents a graph as an array (or map) where each index (or key) corresponds to a node. The value at each index is a list (or set) of its adjacent neighbors (and optionally edge weights).
- Space Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. Efficient for sparse graphs (few edges relative to nodes).
- Pros: Space-efficient for sparse graphs. Iterating over neighbors of a node is efficient.
- Cons: Checking if an edge exists between two specific nodes (u, v) can take O(degree(u)) time.
-
Adjacency Matrix:
- Represents a graph as a V x V matrix where the entry at `matrix[i][j]` indicates the presence (and possibly weight) of an edge from node i to node j. A 0 or infinity might represent no edge.
- Space Complexity: O(V²), regardless of the number of edges. More suitable for dense graphs (many edges).
- Pros: Checking for an edge between nodes i and j is very fast (O(1)). Adding/removing edges is O(1).
- Cons: Space-inefficient for sparse graphs. Iterating over all neighbors of a node takes O(V) time. Adding/removing a node is O(V²).
- Edge List: Simply a list of all edges in the graph, often represented as pairs or triplets (u, v, weight). Space complexity is O(E). Useful for some algorithms but less efficient for neighbor lookups.
Conceptual Data Structures
// Adjacency List (using Map for non-numeric IDs)
const adjList = new Map();
adjList.set('A', [{ node: 'B', weight: 5 }, { node: 'C', weight: 2 }]);
adjList.set('B', [{ node: 'A', weight: 5 }]);
adjList.set('C', [{ node: 'A', weight: 2 }]);
// To check neighbors of 'A': adjList.get('A')
// Adjacency Matrix (assuming nodes 0, 1, 2 correspond to A, B, C)
// INF represents no direct edge
const INF = Infinity;
const adjMatrix = [
// A B C
[ 0, 5, 2 ], // A
[ 5, 0, INF ], // B
[ 2, INF, 0 ] // C
];
// To check edge A -> C: adjMatrix[0][2] (returns 2)
// To check edge B -> C: adjMatrix[1][2] (returns Infinity)