Graphs – Introduction
📘 Data Structure and Algorithm
👁 64 views
📅 Nov 05, 2025
⏱ Estimated reading time: 2 min
Graphs – Introduction
A graph is a non-linear data structure that represents relationships between entities. It consists of a set of vertices (nodes) and edges (connections) that connect pairs of vertices.
Basic Terminology
- Vertex (Node): Fundamental unit representing an entity.
- Edge: Connection between two vertices.
- Degree: Number of edges incident to a vertex.
- Path: Sequence of vertices connected by edges.
- Cycle: Path that starts and ends at the same vertex.
Types of Graphs
- Undirected Graph: Edges have no direction.
- Directed Graph (Digraph): Edges have direction (u → v).
- Weighted Graph: Each edge has an associated cost or weight.
- Unweighted Graph: All edges have equal weight.
- Cyclic Graph: Contains at least one cycle.
- Acyclic Graph: No cycles (e.g., trees, DAGs).
Graph Representation
Graphs can be represented in two primary ways:
1. Adjacency Matrix
A 2D array where matrix[i][j] = 1 if there is an edge from vertex i to j.
// Example (Adjacency Matrix)
int graph[4][4] = {
{0, 1, 1, 0},
{1, 0, 0, 1},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
2. Adjacency List
An array of lists where each list represents neighbors of a vertex.
// Example (Adjacency List) vectorgraph[4]; graph[0].push_back(1); graph[0].push_back(2);
Applications of Graphs
- Social networks (friend connections)
- Maps and GPS navigation
- Web page link structures
- Computer networks and routing
- Dependency resolution (task scheduling, compilers)
Conclusion
Graphs are powerful structures for representing relationships between objects. They form the foundation for advanced algorithms such as traversal, shortest path, and spanning tree computation.
🔒 Some advanced sections are available for Registered Members
Register Now
Register Now
Share this Post
← Back to Tutorials