Graph in Data Structure: Types, Terminology & Representation

Chapter 50 — Data Structure
Graph in Data Structure: Types, Terminology & Representation

Learn graph terminology, directed and undirected graphs, vertices, edges, adjacency matrix, adjacency list, C programming and practical examples for semester exams.

Graph Basics Graph Types Matrix and List C Program Interactive Explorer
Graph in Data Structure: Types, Terminology and Representation

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.

Quick Answer: What Is a Graph?

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.

01 / Introduction

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

G = (V, E) V = Set of vertices E = Set of edges

Consider a Graph with vertices A, B, C and D, having the edges AB, AC, BC and CD.

V = {A, B, C, D} E = {AB, AC, BC, CD} Number of Vertices = 4 Number of Edges = 4

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.

02 / Basic Terminology

Important Graph Terminology in Data Structure

Understanding these terms will help you solve graph questions in university examinations.

1. Vertex

A node of a Graph. A, B, C and D are vertices.

2. Edge

A connection between vertices. AB connects A and B.

3. Adjacent Vertices

Two vertices connected directly by an edge. A and B are adjacent.

4. Incident Edge

An edge is incident on a vertex if that vertex is one of its endpoints.

5. Degree

Number of incident edge ends in an undirected Graph. Vertex C has degree 3.

6. Path

A sequence of connected vertices without repeated vertices. A–C–D is a path.

7. Cycle

A closed path that returns to its starting vertex. A–B–C–A is a cycle.

8. Connected Graph

Every pair of vertices has a path between them.

9. Isolated Vertex

A vertex with degree zero and no incident edges.

10. Pendant Vertex

A vertex with degree one. D is a pendant vertex in our example.

11. Order of Graph

Total number of vertices. Our Graph has order 4.

12. Size of Graph

Total number of edges. Our Graph has size 4.

13. Self-Loop

An edge connecting a vertex to itself.

14. Subgraph

A Graph formed using selected vertices and edges of another Graph.

15. Bridge

An undirected edge whose removal increases connected components. CD is a bridge here.

16. Connected Component

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

Path: A → C → D Vertices = 3 Edges = 2 Path Length = 2
03 / Classification

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.

04 / Degree and Formulas

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

Sum of Degrees = 2 × E 2 + 2 + 3 + 1 = 8 Number of Edges = 4 2 × 4 = 8

In-Degree and Out-Degree

In a Directed Graph, in-degree counts incoming edges, while out-degree counts outgoing edges.

Edges: A → B A → C B → C C → D For Vertex C: In-Degree = 2 Out-Degree = 1

Important Graph Formulas

Undirected Degree Sum = 2E Directed In-Degree Sum = E Directed Out-Degree Sum = E Complete Undirected Graph: E = V(V - 1) / 2 Simple Directed Graph without loops: Maximum Arcs = V(V - 1)
05 / Graph Representation

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.

Matrix[A][B] = Matrix[B][A] Adjacency Matrix Space: O(V²) Direct Edge Lookup: O(1)

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.
06 / Memory-Efficient Representation

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.

A → B → C → NULL
B → A → C → NULL
C → A → B → D → NULL
D → C → NULL

In an undirected Graph, an edge normally appears in the neighbour lists of both endpoints.

Adjacency List Space: O(V + E) Neighbour Traversal: O(degree of vertex)

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.
07 / Comparison

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.

08 / C Programming

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.

graph_representation.c
#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

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

Expected 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

Compile
gcc -std=c11 -Wall -Wextra graph_representation.c -o graph_representation
Windows PowerShell
.\graph_representation.exe
09 / Interactive Practice

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.

Live Graph Diagram

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
4 Vertices
4 Edges
2,2,3,1 Degrees (A–D)

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.

10 / Practical Applications

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.

11 / Common Mistakes

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).
12 / Exam Preparation

Important Graph Questions and Answers

2 MARKS

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 MARKS

2. What Is an Adjacency Matrix?

An Adjacency Matrix is a V × V array used to represent edges between graph vertices.

2 MARKS

3. What Is an Adjacency List?

An Adjacency List stores the neighbours of each vertex using lists.

5 MARKS

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 MARKS

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.

10 MARKS

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.

13 / Practice Questions

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.

14 / Frequently Asked Questions

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.

15 / Quick Revision

Graph in Data Structure Quick Revision Notes

Graph = G(V,E) Vertices = Nodes Edges = Connections Degree Sum (Undirected) = 2E Complete Undirected Graph: E = V(V-1)/2 Adjacency Matrix: O(V²) Space Adjacency List: O(V+E) Space Matrix Edge Lookup: O(1) BFS: Queue DFS: Stack or Recursion

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

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources