Loading...
Graphs are collections of vertices (nodes) connected by edges. They represent relationships and connections between entities, making them perfect for modeling networks, social connections, maps, and many real-world scenarios.
Network of vertices (nodes) connected by edges
Model any type of relationship between entities
Powerful algorithms for pathfinding and analysis
Adjacency matrix, adjacency list, edge list
Social networks, maps, web crawling, AI
Edges have direction (one-way relationships)
Edges are bidirectional (mutual relationships)
Edges have weights/costs associated
Contains cycles (paths back to starting node)
No cycles present (DAG - Directed Acyclic Graph)
Path exists between every pair of vertices
Explore neighbors before going deeper
Explore as far as possible before backtracking
Find shortest path in weighted graphs
Linear ordering of vertices in DAG
Facebook friends, Twitter followers
Road networks and route planning
Following links between web pages
Product recommendations based on connections
| Operation | Adjacency Matrix | Adjacency List | Edge List |
|---|---|---|---|
| Add Vertex | O(V²) | O(1) | O(1) |
| Add Edge | O(1) | O(1) | O(1) |
| Check Edge | O(1) | O(V) | O(E) |
| Get Neighbors | O(V) | O(1) | O(E) |
Space Complexity: Matrix: O(V²), List: O(V + E), Edge List: O(E)
V: Number of vertices, E: Number of edges