Graph Basics in C
So far, you have worked with arrays, linked lists, stacks, queues, trees, and searching algorithms.
Now we move to one of the most powerful and widely used data structures: Graphs.
Graphs are used to represent relationships between objects.
What is a Graph?
A graph is a collection of:
- Vertices (Nodes) – the data points
- Edges – the connections between nodes
Graphs are different from trees because:
- Graphs can have cycles
- Graphs can have multiple paths
- Graphs do not have a single root
Real-World Examples of Graphs
- Social networks (people connected as friends)
- Road maps (cities connected by roads)
- Computer networks
- Internet links
Basic Graph Terminology
- Vertex: A node in the graph
- Edge: Connection between two vertices
- Degree: Number of edges connected to a vertex
- Path: A sequence of vertices
- Cycle: A path that starts and ends at the same vertex
Types of Graphs
Graphs can be classified based on direction:
- Undirected Graph – edges have no direction
- Directed Graph – edges have direction
Example:
- Facebook friends → Undirected
- Instagram follow → Directed
Graph Representation
Graphs are commonly represented in two ways:
- Adjacency Matrix
- Adjacency List
Adjacency Matrix Representation
An adjacency matrix uses a 2D array to represent connections.
If there is an edge between vertex i and j, the value is 1, otherwise 0.
#include <stdio.h>
int main() {
int graph[3][3] = {
{0, 1, 1},
{1, 0, 0},
{1, 0, 0}
};
int i, j;
for(i = 0; i < 3; i++) {
for(j = 0; j < 3; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
return 0;
}
This representation is simple but uses more memory.
Adjacency List (Concept)
In adjacency list representation, each vertex stores a list of connected vertices.
This approach is more memory efficient for large graphs.
We will implement adjacency lists and graph traversal in the next lesson.
Mini Practice
- Create an adjacency matrix for 4 vertices
- Connect vertex 0 with all other vertices
- Print the matrix
Quick Quiz
Q1. What are the two main components of a graph?
Q2. Which structure can have cycles?
Q3. Which graph has directional edges?
Q4. Which representation uses more memory?
Q5. Graphs are used to represent what?