Learn graph terminology, directed and undirected graphs, vertices, edges, adjacency matrix, adjacency list, C programming and practical examples for semester exams.
When we study Data Structure, we begin with arrays, stacks, queues, linked lists and trees. These structures help us store and organise data.
But suppose we want to represent a network of cities connected by roads. One city may be connected to many others, and there can be several different routes between locations.
This type of relationship can be represented using a Graph.
Students usually understand that a Graph contains vertices and edges, but topics like degree, paths, cycles, adjacency matrix and adjacency list can feel confusing in the beginning.
In this chapter, we will learn Graph in Data Structure using simple examples, clear diagrams, useful formulas, a working C program and an interactive Graph Explorer.
A Graph is a non-linear data structure consisting of vertices and edges. It is represented as G = (V, E), where V is the set of vertices and E is the set of edges. Graphs represent relationships and connections between entities.
What Is Graph in Data Structure?
A Graph is a collection of nodes called vertices and connections called edges. Each vertex may connect to one or more vertices, or it may have no connections.
A Graph is called a non-linear data structure because its elements do not need to be arranged in a single sequence.
Mathematical Representation
Consider a Graph with vertices A, B, C and D, having the edges AB, AC, BC and CD.
Vertex C connects directly with A, B and D, while vertex D connects only with C.
Remember: A vertex represents an object or entity. An edge represents a connection between vertices.
Important Graph Terminology in Data Structure
Understanding these terms will help you solve graph questions in university examinations.
A node of a Graph. A, B, C and D are vertices.
A connection between vertices. AB connects A and B.
Two vertices connected directly by an edge. A and B are adjacent.
An edge is incident on a vertex if that vertex is one of its endpoints.
Number of incident edge ends in an undirected Graph. Vertex C has degree 3.
A sequence of connected vertices without repeated vertices. A–C–D is a path.
A closed path that returns to its starting vertex. A–B–C–A is a cycle.
Every pair of vertices has a path between them.
A vertex with degree zero and no incident edges.
A vertex with degree one. D is a pendant vertex in our example.
Total number of vertices. Our Graph has order 4.
Total number of edges. Our Graph has size 4.
An edge connecting a vertex to itself.
A Graph formed using selected vertices and edges of another Graph.
An undirected edge whose removal increases connected components. CD is a bridge here.
A maximal connected part of an undirected Graph.
Walk vs Trail vs Path
| Term | Explanation |
|---|---|
| Walk | Connected sequence where vertices and edges may repeat. |
| Trail | A walk that never repeats an edge. |
| Path | A walk with no repeated vertices. |
Path Length Example
Types of Graph in Data Structure
1. Undirected Graph
In an Undirected Graph, edges have no fixed direction. If A connects to B, the connection is mutual.
2. Directed Graph
A Directed Graph contains edges with directions. A → B does not automatically mean B → A.
3. Weighted Graph
A Weighted Graph stores numerical values with edges, such as distance, cost or travel time.
4. Unweighted Graph
In an Unweighted Graph, edges indicate connections without separate numerical costs.
5. Simple Graph
A Simple Graph does not have self-loops or parallel edges.
6. Multigraph
A Multigraph permits multiple edges between the same pair of vertices.
7. Complete Graph
A Complete Graph has an edge between every pair of distinct vertices. A complete simple undirected graph with n vertices contains n(n−1)/2 edges.
8. Connected Graph
An undirected Graph is connected when every vertex is reachable from every other vertex.
9. Disconnected Graph
A Disconnected Graph contains vertices that cannot all reach one another.
10. Cyclic and Acyclic Graph
A Cyclic Graph contains at least one cycle. An Acyclic Graph contains no cycles.
11. Directed Acyclic Graph (DAG)
A DAG is a Directed Graph without directed cycles. It is useful for representing task dependencies.
12. Bipartite Graph
A Bipartite Graph divides vertices into two groups. Every edge connects vertices belonging to different groups.
Exam Tip: These Graph types can overlap. A Graph can be both directed and weighted, or connected and cyclic.
Degree of Vertex in Graph with Examples
In an undirected Graph, degree is the number of incident edge ends of a vertex. A self-loop contributes two to the degree.
| Vertex | Neighbours | Degree |
|---|---|---|
| A | B, C | 2 |
| B | A, C | 2 |
| C | A, B, D | 3 |
| D | C | 1 |
Handshaking Lemma
In-Degree and Out-Degree
In a Directed Graph, in-degree counts incoming edges, while out-degree counts outgoing edges.
Important Graph Formulas
Adjacency Matrix Representation of Graph
An Adjacency Matrix uses a two-dimensional array to represent a Graph.
For V vertices, the matrix contains V rows and V columns.
In an unweighted graph, value 1 normally means an edge exists, while value 0 means it does not.
Adjacency Matrix Example
| V | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 |
Because our example is undirected, its adjacency matrix is symmetric.
Advantages of Adjacency Matrix
- Simple representation using arrays.
- Direct edge lookup takes O(1) time.
- Convenient for dense Graphs.
Disadvantages
- Requires O(V²) space.
- Many cells remain empty in sparse Graphs.
- Finding all neighbours takes O(V) time.
Adjacency List Representation of Graph
An Adjacency List stores the neighbours of every vertex.
Instead of keeping a complete square matrix, it stores the connections that actually exist.
In an undirected Graph, an edge normally appears in the neighbour lists of both endpoints.
Advantages of Adjacency List
- Useful for sparse Graphs.
- Uses O(V+E) space.
- Efficient neighbour traversal.
- Commonly used in BFS and DFS.
Disadvantages
- Searching a particular edge may take time.
- Linked-list implementations require pointer handling.
Adjacency Matrix vs Adjacency List
| Feature | Matrix | List |
|---|---|---|
| Structure | 2D Array | Neighbour Lists |
| Space | O(V²) | O(V+E) |
| Edge Lookup | O(1) | O(deg(u)) for a simple unsorted list |
| Neighbour Traversal | O(V) | O(deg(u)) |
| Best Use | Dense Graphs | Sparse Graphs |
| BFS / DFS Time | O(V²) | O(V+E) |
Memory Trick: Matrix = Fast direct edge checking. List = Efficient storage of relatively few connections.
Graph Representation in C with Output
The following C program creates an undirected Graph using both Adjacency Matrix and linked-list-based Adjacency List.
It accepts vertices and edges from the user, checks for invalid edges, and prints both forms.
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct Node {
int vertex;
struct Node *next;
} Node;
void freeLists(Node *adj[], int n) {
for (int i = 0; i < n; i++) {
Node *cur = adj[i];
while (cur != NULL) {
Node *next = cur->next;
free(cur);
cur = next;
}
adj[i] = NULL;
}
}
int insertSorted(Node **head, int vertex) {
Node *node = malloc(sizeof(*node));
if (node == NULL) {
return 0;
}
node->vertex = vertex;
node->next = NULL;
Node **at = head;
while (
*at != NULL &&
(*at)->vertex < vertex
) {
at = &(*at)->next;
}
node->next = *at;
*at = node;
return 1;
}
int main(void) {
int n, m;
int matrix[MAX][MAX] = {{0}};
Node *adj[MAX] = {NULL};
printf("Enter vertices and edges: ");
if (
scanf("%d %d", &n, &m) != 2 ||
n < 1 ||
n > MAX ||
m < 0 ||
m > n * (n - 1) / 2
) {
puts("Invalid graph size.");
return 1;
}
printf(
"Enter %d edges as index pairs (0 to %d):\n",
m, n - 1
);
for (int k = 0; k < m; k++) {
int u, v;
if (
scanf("%d %d", &u, &v) != 2 ||
u < 0 || v < 0 ||
u >= n || v >= n ||
u == v || matrix[u][v]
) {
puts("Invalid, duplicate or self-loop edge.");
freeLists(adj, n);
return 1;
}
if (
!insertSorted(&adj[u], v) ||
!insertSorted(&adj[v], u)
) {
puts("Memory allocation failed.");
freeLists(adj, n);
return 1;
}
matrix[u][v] = 1;
matrix[v][u] = 1;
}
puts("\nAdjacency Matrix:");
printf(" ");
for (int i = 0; i < n; i++) {
printf("%c ", 'A' + i);
}
putchar('\n');
for (int i = 0; i < n; i++) {
printf("%c : ", 'A' + i);
for (int j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
putchar('\n');
}
puts("\nAdjacency List:");
for (int i = 0; i < n; i++) {
printf("%c", 'A' + i);
Node *cur = adj[i];
while (cur != NULL) {
printf(
" -> %c",
'A' + cur->vertex
);
cur = cur->next;
}
puts(" -> NULL");
}
freeLists(adj, n);
return 0;
}
Sample Input
Enter vertices and edges: 4 4
Enter 4 edges as index pairs (0 to 3):
0 1
0 2
1 2
2 3
Output
Adjacency Matrix:
A B C D
A : 0 1 1 0
B : 1 0 1 0
C : 1 1 0 1
D : 0 0 1 0
Adjacency List:
A -> B -> C -> NULL
B -> A -> C -> NULL
C -> A -> B -> D -> NULL
D -> C -> NULL
Explanation of the C Program
The program first creates a matrix filled with zeros and an array of empty adjacency-list heads.
Whenever an undirected edge is entered, the program updates both matrix positions.
It also allocates adjacency-list nodes to store each endpoint in the other endpoint's list.
Finally, it prints the matrix and lists, and releases the allocated memory.
How to Run in VS Code
gcc -std=c11 -Wall -Wextra graph_representation.c -o graph_representation
.\graph_representation.exe
Interactive Graph Representation Explorer
Reading Graph diagrams is useful, but creating connections yourself makes the concept easier to remember.
Select vertices, add or remove edges and observe how the Adjacency Matrix and Adjacency List update automatically.
Graph Learning Atlas
Work with four vertices: A, B, C and D. Switch between Directed and Undirected Graphs.
Starting edges: AB, AC, BC, CD.
Adjacency Matrix
| V | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 |
Adjacency List
- A→ B → C
- B→ A → C
- C→ A → B → D
- D→ C
Example Graph loaded.
Practice: Remove the edge C–D. Vertex D will become isolated. Then switch to Directed mode and compare the matrix and outgoing adjacency lists.
Applications of Graph in Data Structure
1. Road Networks
Cities are represented by vertices and roads by edges. Weights can represent distance.
2. Social Networks
People are represented by vertices, while friendships and follows form edges.
3. Computer Networks
Routers and computers can be vertices, while network links are edges.
4. Websites
Web pages form vertices, and hyperlinks can form directed edges.
5. Task Scheduling
Directed Acyclic Graphs help represent task dependencies and prerequisites.
6. BFS and DFS
Breadth-First Search uses a Queue, while Depth-First Search uses recursion or an explicit Stack.
7. Shortest Paths
Graph algorithms help find routes between vertices. Dijkstra's algorithm can find shortest paths with non-negative edge weights.
8. Minimum Spanning Trees
Prim's and Kruskal's algorithms can find a minimum spanning tree in a connected, weighted, undirected Graph.
Common Mistakes in Graph Representation
| Mistake | Correct Concept |
|---|---|
| Confusing vertices and edges | Vertices are nodes; edges connect nodes. |
| Treating all edges as undirected | Directed edges have a fixed orientation. |
| Forgetting matrix symmetry | An undirected adjacency matrix is symmetric. |
| Ignoring isolated vertices | They still belong to the Graph. |
| Using O(V+E) for matrix storage | Matrix space is O(V²). |
| Using O(V²) for list storage | Standard adjacency-list space is O(V+E). |
Important Graph Questions and Answers
1. Define Graph.
A Graph is a non-linear data structure made up of vertices and edges. It is represented by G=(V,E).
2. What Is an Adjacency Matrix?
An Adjacency Matrix is a V × V array used to represent edges between graph vertices.
3. What Is an Adjacency List?
An Adjacency List stores the neighbours of each vertex using lists.
4. Differentiate Directed and Undirected Graph.
A Directed Graph contains edges with a fixed direction. A → B does not imply B → A.
An Undirected Graph has edges without direction. An edge A–B represents a mutual connection.
5. Compare Adjacency Matrix and List.
Adjacency Matrix uses a two-dimensional array and requires O(V²) space. It allows O(1) direct edge checking.
Adjacency List stores actual neighbours and uses O(V+E) space. It is commonly preferred for sparse Graphs.
6. Explain Graph, Its Types and Representations.
A Graph is a non-linear data structure represented by G=(V,E), where V is the set of vertices and E is the set of edges.
Important graph types include directed, undirected, weighted, unweighted, connected, disconnected, cyclic and acyclic graphs.
Adjacency Matrix stores connections inside a square array and requires O(V²) memory.
Adjacency List stores each vertex's neighbours and requires O(V+E) space.
Graphs are widely used in road networks, social networks, computer networks and path-finding applications.
Graph Practice Questions with Solutions
Q1. How Many Edges Does K5 Have?
Show Solution
n(n−1)/2 = 5×4/2 = 10. Therefore, K5 has 10 edges.
Q2. Find Degree of C.
Show Answer
C connects to A, B and D. Therefore, degree(C) = 3.
Q3. Which Representation Uses O(V²) Space?
Show Answer
Adjacency Matrix.
Q4. What Happens When Edge C–D Is Removed?
Show Answer
D becomes isolated. The graph now has two connected components: {A,B,C} and {D}.
Q5. Which Data Structure Is Used in BFS?
Show Answer
Queue is used in standard Breadth-First Search.
FAQs About Graph in Data Structure
What is Graph in simple words?
A Graph contains nodes and connections between them.
What are vertices and edges?
Vertices are nodes. Edges represent connections.
What are the main Graph types?
Directed, undirected, weighted, unweighted, connected, disconnected, cyclic and acyclic graphs.
What is the space complexity of an Adjacency Matrix?
O(V²).
What is the space complexity of an Adjacency List?
O(V+E).
Which is better for sparse Graphs?
An Adjacency List is usually more memory-efficient.
What is the difference between Tree and Graph?
A Tree is a connected, acyclic, undirected Graph. General Graphs may have cycles and be disconnected.
Graph in Data Structure Quick Revision Notes
Memory Trick: Graph = Nodes + Connections. Matrix = Rows and Columns. List = Neighbours.
Conclusion
Graph in Data Structure is an important topic because many practical problems involve connections between different objects.
Once you understand vertices, edges, degree, paths and Graph types, learning Adjacency Matrix and Adjacency List becomes easier.
For semester examinations, practise drawing a Graph, calculating degrees, writing both representations and running the C program.
Chapter 50 — Completed
