🕸️ Graph Visualization (Click a node!)
Selected
Neighbor
Normal
📊 Current Graph Properties
Vertices
6
Edges
9
Type
Undirected
Weighted
Yes
Connected
Yes
Density
0.60
📝 Graph Terminology Dictionary (Click to visualize)
Vertex (Node)
A fundamental unit of a graph, representing an entity or data point
Edge (Link)
A connection between two vertices; may have weight or direction
Adjacent
Two vertices connected directly by an edge are adjacent
Degree
Number of edges connected to a vertex (in-degree / out-degree for directed)
Path
A sequence of vertices connected by edges with no repeated vertices
Cycle
A path that starts and ends at the same vertex, forming a loop
Connected
A graph where a path exists between every pair of vertices
Weight
A numerical value assigned to an edge representing cost or distance
Directed
Edges have a specific direction from source to destination
Component
A maximal connected subgraph where every vertex is reachable from every other
📖 Concept Guide
🔗 What is a Graph?
A Graph is a non-linear data structure consisting of vertices (nodes) and edges (links) connecting pairs of vertices.
💡 Formal Definition:
G = (V, E) where:
• V = set of vertices {v₁, v₂, ..., vₙ}
• E = set of edges {(u,v) | u,v ∈ V}
• Unlike trees, graphs can have cycles and multiple paths
G = (V, E) where:
• V = set of vertices {v₁, v₂, ..., vₙ}
• E = set of edges {(u,v) | u,v ∈ V}
• Unlike trees, graphs can have cycles and multiple paths
Graph vs Tree
| Feature | Tree | Graph |
|---|---|---|
| Cycles | Not allowed | Allowed |
| Root node | Has one root | No root concept |
| Edges | Exactly N-1 | Any number |
| Direction | Parent → Child | Optional |
| Connection | Always connected | Can be disconnected |
📝 Analogy
Think of a city map! Cities are vertices, roads are edges. Roads can be one-way (directed) or two-way (undirected), and have distances (weights).
📐 Mathematical Properties
| Property | Formula |
|---|---|
| Max edges (undirected) | V(V-1)/2 |
| Max edges (directed) | V(V-1) |
| Sum of all degrees | 2 × |E| (undirected) |
| Density | 2|E| / V(V-1) |
| Tree condition | |E| = |V| - 1 + connected |
📊 Handshaking Lemma:
The sum of all vertex degrees = 2 × number of edges.
Example: 9 edges → sum of degrees = 18
The sum of all vertex degrees = 2 × number of edges.
Example: 9 edges → sum of degrees = 18
⏱️ Complexity by Representation
| Operation | Adj. Matrix | Adj. List |
|---|---|---|
| Check edge exists | O(1) | O(deg) |
| Get all neighbors | O(V) | O(deg) |
| Add edge | O(1) | O(1) |
| Remove edge | O(1) | O(deg) |
| Space | O(V²) | O(V+E) |
📚 Types of Graphs
| Type | Description |
|---|---|
| Undirected | Edges have no direction; (u,v) = (v,u) |
| Directed (Digraph) | Edges have direction; (u→v) ≠ (v→u) |
| Weighted | Edges carry numerical values (cost/distance) |
| Unweighted | All edges are treated equally |
| Connected | Path exists between every pair of vertices |
| Disconnected | Some vertices are unreachable from others |
| Cyclic | Contains at least one cycle |
| Acyclic (DAG) | No cycles; Directed Acyclic Graph |
| Complete (Kn) | Every vertex connects to every other vertex |
| Bipartite | Vertices split into two disjoint sets; edges only between sets |
| Sparse | |E| much less than |V|² → use Adjacency List |
| Dense | |E| close to |V|² → use Adjacency Matrix |
💡 DAG (Directed Acyclic Graph):
Used in task scheduling, dependency resolution, build systems (Makefile, npm), and version control (Git commit history).
Used in task scheduling, dependency resolution, build systems (Makefile, npm), and version control (Git commit history).
🌍 Real-World Applications
- Social Networks — Friend connections (Facebook, LinkedIn, Instagram)
- GPS / Maps — Shortest path navigation (Google Maps, Waze)
- Internet — Web page links (PageRank), network routing
- Recommendations — Netflix, Amazon, Spotify suggestions
- Package Managers — Dependency resolution (npm, pip, Maven)
- Compilers — Control flow graphs, syntax trees, call graphs
- Biology — Protein interactions, neural networks, gene regulation
- Transportation — Flight routes, railway networks, delivery optimization
- AI / ML — Knowledge graphs, graph neural networks (GNN)
- Blockchain — Transaction graphs, DAG-based ledgers
Data Structure Hierarchy:
• Array/List → 1D sequential data
• Tree → Hierarchical (1 parent per node)
• Graph → Complex relationships (any-to-any connections)
• Array/List → 1D sequential data
• Tree → Hierarchical (1 parent per node)
• Graph → Complex relationships (any-to-any connections)
🎯 Selected Node Info
📍 Click a node
Click a node in the graph to display its detailed information.
🔀 Graph Mode
🔦 Highlight by Term
💾 Graph Representations
// Adjacency Matrix (Weighted)
// A B C D E F
A [ 0 4 2 0 0 0 ]
B [ 4 0 1 5 0 0 ]
C [ 2 1 0 8 10 0 ]
D [ 0 5 8 0 2 6 ]
E [ 0 0 10 2 0 3 ]
F [ 0 0 0 6 3 0 ]
// 0 means no edge exists
// Space: O(V²) = O(36)
// Adjacency List (Weighted)
A → [B:4] → [C:2]
B → [A:4] → [C:1] → [D:5]
C → [A:2] → [B:1] → [D:8] → [E:10]
D → [B:5] → [C:8] → [E:2] → [F:6]
E → [C:10] → [D:2] → [F:3]
F → [D:6] → [E:3]
// Space: O(V + 2E) = O(6+18)
// Edge List (src, dst, weight)
edges = [
(A, B, 4), (A, C, 2),
(B, C, 1), (B, D, 5),
(C, D, 8), (C, E, 10),
(D, E, 2), (D, F, 6),
(E, F, 3)
]
// Space: O(E) = O(9)
// Good for Kruskal's MST
📐 Key Formulas
Max edges (undirected)
V(V-1)/2Sum of degrees
2|E|Density
2E / V(V-1)Tree condition
E = V-1Complete graph edges
n(n-1)/2🌍 Real-World Examples
Social Network — Friends & followers
Google Maps — Shortest path routes
Flight Routes — Airport connections
npm / pip — Package dependencies