Graph Algorithms
A graph is a non-linear data structure made up of vertices (nodes) connected by edges. Unlike trees, graphs do not impose a strict hierarchical structure and may contain cycles, multiple paths, or disconnected components. This flexibility makes graphs ideal for modeling complex relationships between entities.
Graphs are widely used in areas such as social networks, transportation systems, recommendation engines, computer networks, and dependency analysis.
What Is a Graph?
A graph consists of:
- Vertices (Nodes) - individual elements that store data
- Edges - connections between pairs of vertices
- Direction - edges may be directed or undirected
- Weight - edges may carry cost or distance values
Unlike trees, graphs may contain cycles and may have multiple paths between two vertices.
Basic Terminology
Understanding graph terminology is essential before working with graph algorithms.
Vertex (Node)
A vertex represents an individual entity in the graph.
(A) (B) (C)
Edge
An edge represents a connection between two vertices.
A ----- B
Edges can be:
- Undirected - connection works both ways
- Directed - connection has a direction
A → B
Adjacent Vertices
Two vertices are adjacent if they are connected by an edge.
A ----- B ← adjacent
Path
A path is a sequence of vertices connected by edges.
A → B → C → D
Cycle
A cycle exists if a path starts and ends at the same vertex.
A → B → C → A
Graphs may contain cycles - unlike trees.
Degree of a Vertex
The degree of a vertex is the number of edges connected to it.
-
Undirected graph - number of connected edges
-
Directed graph:
- In-degree - number of incoming edges
- Out-degree - number of outgoing edges
A → B → C
B has in-degree 1 and out-degree 1
Types of Graphs (High-Level Overview)
Here are common graph categories:
| Graph Type | Description |
|---|---|
| Undirected Graph | Edges have no direction |
| Directed Graph | Edges have direction |
| Weighted Graph | Edges have weights (cost, distance) |
| Unweighted Graph | All edges have equal weight |
| Cyclic Graph | Contains at least one cycle |
| Acyclic Graph | Contains no cycles |
| Connected Graph | All vertices are reachable |
| Disconnected Graph | One or more isolated components |
Graph vs Tree (Key Differences)
| Aspect | Tree | Graph |
|---|---|---|
| Structure | Hierarchical | Arbitrary relationships |
| Cycles | ❌ Not allowed | ✅ Allowed |
| Root | Exactly one | None required |
| Paths | Exactly one path | Multiple paths possible |
| Connectivity | Always connected | May be disconnected |
Why Graphs Are Useful
Graphs provide powerful solutions for problems involving:
- Modeling relationships (social networks, maps)
- Shortest-path and routing problems
- Dependency resolution (build systems, package managers)
- Network flow and connectivity analysis
Their flexibility allows them to represent real-world systems more accurately than linear or hierarchical structures.