Graph Theory Foundation Interactive

Graph Foundation

Build and visualize graphs interactively. Connect nodes with edges and explore adjacency list and matrix representations. Use the pen overlay to annotate and highlight your understanding.

Theory

A graph is a fundamental data structure consisting of nodes (vertices) and edges (connections) that represent relationships between entities. Graphs can be directed (edges have direction) or undirected (bidirectional). Graphs are the foundation for algorithms like BFS, DFS, shortest path, and network flow analysis, and are crucial for modeling real-world networks.

Components: Nodes/Vertices are entities, Edges connect nodes and may have weights or directions
Time Complexity: Adjacency List: O(1) insertion, O(degree) search; Adjacency Matrix: O(1) both
Space Complexity: Adjacency List: O(V + E); Adjacency Matrix: O(V²)
Common Applications:
- Social networks and connections
- Road networks and GPS routing
- Web page link structure and PageRank
- Recommendation systems and relationships

Problem Statement

Build a graph by adding nodes and edges interactively. Use the visualizer to understand how graphs are structured and represented. Observe how the adjacency list and matrix representations change as you modify the graph, and use the pen tool to annotate your analysis.

Interactive Graph Builder

graph.svg

Node

Edge

Graph Controls

Graph Stats

Nodes

Edges

Graph Representations

adjacency_list.txt

A → [ ]
B → [ ]
C → [ ]
D → [ ]
E → [ ]
F → [ ]

adjacency_matrix.txt

  A B C D E F
A 0 1 1 0 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 0
D 0 1 1 0 0 1
E 0 1 0 0 0 0
F 0 0 0 1 0 0

Code Representations

Language:

adjacency_list.c

1#include <stdio.h>
2#include <stdlib.h>
3
4// Adjacency List using array of linked lists
5typedef struct Node {
6int vertex;
7struct Node* next;
8} Node;
9
10typedef struct Graph {
11int V;
12Node** adjList;
13} Graph;
14
15Graph* createGraph(int V) {
16Graph* graph = malloc(sizeof(Graph));
17graph->V = V;
18graph->adjList = malloc(V * sizeof(Node*));
19for (int i = 0; i < V; i++)
20graph->adjList[i] = NULL;
21return graph;
22}
23
24void addEdge(Graph* g, int src, int dest) {
25Node* newNode = malloc(sizeof(Node));
26newNode->vertex = dest;
27newNode->next = g->adjList[src];
28g->adjList[src] = newNode;
29}
30
31void printAdjList(Graph* g) {
32for (int i = 0; i < g->V; i++) {
33printf("%d: ", i);
34for (Node* temp = g->adjList[i]; temp; temp = temp->next)
35printf("%d ", temp->vertex);
36printf("\n");
37}
38}

adjacency_matrix.c

1#include <stdio.h>
2#define MAX_V 100
3
4// Adjacency Matrix representation
5typedef struct {
6int adj[MAX_V][MAX_V];
7int V;  // number of vertices
8} Graph;
9
10Graph* createGraph(int V) {
11Graph* g = malloc(sizeof(Graph));
12g->V = V;
13for (int i = 0; i < V; i++)
14for (int j = 0; j < V; j++)
15g->adj[i][j] = 0;
16return g;
17}
18
19void addEdge(Graph* g, int src, int dest) {
20g->adj[src][dest] = 1;  // undirected
21g->adj[dest][src] = 1;
22}
23
24void printMatrix(Graph* g) {
25for (int i = 0; i < g->V; i++) {
26for (int j = 0; j < g->V; j++)
27printf("%d ", g->adj[i][j]);
28printf("\n");
29}
30}