October 17, 2026

Introduction to Graphs

A Graph is a non-linear data structure consisting of vertices (also called nodes) and edges that connect them.

Graphs are used to represent relationships between objects, such as cities connected by roads, users connected on social networks, computers connected in networks, and web pages connected through hyperlinks.

A graph is commonly represented as:

[
G = (V, E)
]

Where:

• (V) is the set of vertices.

• (E) is the set of edges.

For example, if vertices are A, B, and C, and edges connect A–B and B–C, the graph represents a network in which A is connected to B and B is connected to C.

1. Introduction to Graphs

Consider this graph:

       A
      / \
     B---C
      \  /
       D

In this example:

• Vertices: A, B, C, D

• Edges: A-B, A-C, B-C, B-D, C-D

• Number of vertices: 4

• Number of edges: 5

Important Graph Terminology

Vertex: An individual node in a graph.

Edge: A connection between two vertices.

Adjacent Vertices: Two vertices directly connected by an edge.

Degree: In an undirected graph, the number of edges incident to a vertex.

Indegree: In a directed graph, the number of incoming edges to a vertex.

Outdegree: In a directed graph, the number of outgoing edges from a vertex.

Path: A sequence of vertices connected by edges.

Cycle: A path that returns to its starting vertex without repeating other vertices, in the usual simple-cycle definition.

Connected Graph: An undirected graph in which every pair of vertices has a path between them.

Connected Component: A maximal connected part of an undirected graph.

Weight: A numerical value assigned to an edge, such as distance, cost, or travel time.

Adjacent Matrix: A matrix that records which vertex pairs are connected and, in weighted graphs, may store edge weights.

Traversal: The process of visiting vertices systematically, such as with BFS or DFS.

2. Directed and Undirected Graphs

Graphs are commonly classified according to whether their edges have a direction.

Undirected Graph

An Undirected Graph has edges without direction. If vertex A is connected to B, the connection works both ways.

Example:

A ----- B
 \     /
   \ /
    C

This can represent two-way friendships or roads that allow travel in both directions.

Directed Graph

A Directed Graph, also called a digraph, has edges with directions.

Example:

A ----> B
^       |
|       v
C <----- 

An edge A → B means the connection goes from A to B. It does not automatically mean B connects back to A.

Directed graphs can represent one-way streets, social media followers, and web links.

Directed vs Undirected Graph

3. Weighted and Unweighted Graphs

Unweighted Graph

An Unweighted Graph treats edges as connections without a numerical cost.

Example:

A ----- B
|       |
|       |
C ----- D

It can represent whether two people are connected or whether two locations are linked.

Weighted Graph

A Weighted Graph assigns a numerical value to each edge.

Example:

A --5-- B
|       |
2       7
|       |
C --3-- D

The numbers represent costs, distances, or other quantities.

For example:

• A — B has weight 5.

• A — C has weight 2.

• C — D has weight 3.

• B — D has weight 7.

Weighted vs Unweighted Graph

Important: For unweighted graphs, BFS finds a path with the fewest edges. For weighted graphs with nonnegative edge weights, Dijkstra's algorithm can find a minimum-total-weight path.

4. Adjacency Matrix

An Adjacency Matrix represents a graph using a two-dimensional array.

For a graph with (V) vertices, the matrix contains (V \times V) entries.

For an unweighted graph:

• matrix[i][j] = 1 if an edge exists.

• matrix[i][j] = 0 if no edge exists.

Consider an undirected graph with three vertices:

A ----- B
 \
  \
   C

Its edges are A-B and A-C.

The adjacency matrix is:

Because the graph is undirected, the matrix is symmetric.

C Program: Adjacency Matrix

#include 

#define V 4

int main(void) {
    int graph[V][V] = {0};

    // Add undirected edges.
    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[2][3] = graph[3][2] = 1;

    printf("Adjacency Matrix:\n");

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Output:

Adjacency Matrix:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

The vertices are numbered 0, 1, 2, and 3.

Advantages

• Simple to implement.

• Checking whether an edge exists takes O(1) time.

• Suitable for dense graphs.

Disadvantages

• Requires O(V²) memory, even if the graph has very few edges.

• Listing all neighbors of a vertex takes O(V) time.

5. Adjacency List

An Adjacency List stores a list of neighbors for every vertex.

For a sparse graph, it generally uses less memory than an adjacency matrix.

Consider these undirected edges:

A-B, A-C, B-D, C-D

The adjacency list is:

A: B -> C
B: A -> D
C: A -> D
D: B -> C

Each vertex stores its adjacent vertices.

C Program: Adjacency List

The following example uses a fixed-size array of linked lists.

#include 
#include 

#define V 4

struct Node {
    int vertex;
    struct Node *next;
};

struct Node *adj[V];

struct Node *createNode(int vertex) {
    struct Node *node = malloc(sizeof(struct Node));

    if (node == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    node->vertex = vertex;
    node->next = NULL;

    return node;
}

void addDirectedEdge(int src, int dest) {
    struct Node *node = createNode(dest);

    node->next = adj[src];
    adj[src] = node;
}

void addUndirectedEdge(int u, int v) {
    addDirectedEdge(u, v);
    addDirectedEdge(v, u);
}

void displayGraph(void) {
    for (int i = 0; i < V; i++) {
        struct Node *temp = adj[i];

        printf("%d: ", i);

        while (temp != NULL) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }

        printf("NULL\n");
    }
}

void freeGraph(void) {
    for (int i = 0; i < V; i++) {
        struct Node *temp = adj[i];

        while (temp != NULL) {
            struct Node *next = temp->next;
            free(temp);
            temp = next;
        }

        adj[i] = NULL;
    }
}

int main(void) {
    for (int i = 0; i < V; i++) {
        adj[i] = NULL;
    }

    addUndirectedEdge(0, 1);
    addUndirectedEdge(0, 2);
    addUndirectedEdge(1, 3);
    addUndirectedEdge(2, 3);

    printf("Adjacency List:\n");
    displayGraph();

    freeGraph();
    return 0;
}

Output:

Adjacency List:
0: 2 -> 1 -> NULL
1: 3 -> 0 -> NULL
2: 3 -> 0 -> NULL
3: 2 -> 1 -> NULL

The neighbors appear in reverse insertion order because each new node is inserted at the head of the list.

Adjacency Matrix vs Adjacency List

Here, V is the number of vertices and E is the number of edges.

6. Breadth-First Search (BFS)

Breadth-First Search (BFS) traverses a graph level by level. It visits a starting vertex first, then its unvisited neighbors, then the neighbors of those vertices.

BFS uses a Queue.

BFS Algorithm

1. Mark all vertices as unvisited.

2. Mark the starting vertex as visited.

3. Insert the starting vertex into the Queue.

4. Remove a vertex from the front of the Queue and process it.

5. Insert each unvisited neighbor into the Queue and mark it visited.

6. Repeat until the Queue becomes empty.

Consider this graph:

0 ----- 1
|       |
|       |
2 ----- 3

Edges: 0-1, 0-2, 1-3, 2-3.

Starting from vertex 0, one valid BFS order is:

0 1 2 3

The order can differ depending on the order in which neighbors are stored.

BFS Program in C

#include 

#define V 4

void addUndirectedEdge(int graph[V][V], int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1;
}

void BFS(int graph[V][V], int start) {
    int visited[V] = {0};
    int queue[V];
    int front = 0, rear = 0;

    visited[start] = 1;
    queue[rear++] = start;

    printf("BFS Traversal: ");

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        for (int i = 0; i < V; i++) {
            if (graph[current][i] && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }

    printf("\n");
}

int main(void) {
    int graph[V][V] = {0};

    addUndirectedEdge(graph, 0, 1);
    addUndirectedEdge(graph, 0, 2);
    addUndirectedEdge(graph, 1, 3);
    addUndirectedEdge(graph, 2, 3);

    BFS(graph, 0);

    return 0;
}

Output:

BFS Traversal: 0 1 2 3

BFS Complexity

Using an adjacency matrix, BFS takes O(V²) time because it scans all possible neighbors of each visited vertex.

Using an adjacency list, BFS takes O(V + E) time.

Applications of BFS:

• Finding shortest paths in unweighted graphs.

• Level-order traversal of trees.

• Social network connection analysis.

• Network broadcasting.

• Finding connected components.

7. Depth-First Search (DFS)

Depth-First Search (DFS) explores as far as possible along one path before backtracking.

DFS can be implemented using recursion or an explicit stack.

DFS Algorithm

1. Start at a vertex.

2. Mark it as visited.

3. Process the vertex.

4. Visit an unvisited neighbor recursively.

5. Backtrack when no unvisited neighbors remain.

For the same graph:

0 ----- 1
|       |
|       |
2 ----- 3

Starting from 0, one valid DFS order is:

0 1 3 2

The order depends on the neighbor iteration order.

DFS Program in C

#include 

#define V 4

void DFS(int graph[V][V], int vertex, int visited[V]) {
    visited[vertex] = 1;
    printf("%d ", vertex);

    for (int i = 0; i < V; i++) {
        if (graph[vertex][i] && !visited[i]) {
            DFS(graph, i, visited);
        }
    }
}

int main(void) {
    int graph[V][V] = {0};
    int visited[V] = {0};

    graph[0][1] = graph[1][0] = 1;
    graph[0][2] = graph[2][0] = 1;
    graph[1][3] = graph[3][1] = 1;
    graph[2][3] = graph[3][2] = 1;

    printf("DFS Traversal: ");
    DFS(graph, 0, visited);
    printf("\n");

    return 0;
}

Output:

DFS Traversal: 0 1 3 2

DFS Complexity

With an adjacency matrix, DFS takes O(V²) time.

With an adjacency list, DFS takes O(V + E) time.

Applications of DFS:

• Cycle detection.

• Topological sorting in directed acyclic graphs.

• Finding connected components.

• Maze solving.

• Path exploration.

• Detecting strongly connected components with suitable algorithms.

Important: The programs above traverse only vertices reachable from the starting vertex. For a disconnected graph, run BFS or DFS from every vertex that remains unvisited to cover all components.

8. Shortest Path Algorithms

A Shortest Path Algorithm finds a path between vertices that minimizes the number of edges or the total edge weight, depending on the problem.

Different graph types require different algorithms.

Common Shortest Path Algorithms

Dijkstra's algorithm does not work correctly in general when negative-weight edges are present. Bellman–Ford can detect reachable negative-weight cycles.

Dijkstra's Algorithm

Dijkstra's algorithm calculates shortest distances from one source vertex to all other reachable vertices in a graph with nonnegative edge weights.

It maintains a distance array:

• dist[v] stores the currently known shortest distance to vertex v.

• Initially, the source distance is 0.

• Other distances begin at infinity.

• When a shorter path is found through a vertex, the distance is updated. This is called relaxation.

Dijkstra's Algorithm in C

This simple implementation uses an adjacency matrix and scans vertices linearly to find the next minimum-distance vertex. It supports nonnegative weights and uses 0 to indicate no edge, so it cannot represent a zero-weight edge.

#include 
#include 

#define V 5

int minDistance(int dist[V], int visited[V]) {
    int min = INT_MAX;
    int minIndex = -1;

    for (int i = 0; i < V; i++) {
        if (!visited[i] && dist[i] < min) {
            min = dist[i];
            minIndex = i;
        }
    }

    return minIndex;
}

void dijkstra(int graph[V][V], int source) {
    int dist[V];
    int visited[V] = {0};

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
    }

    dist[source] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);

        if (u == -1) {
            break;
        }

        visited[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!visited[v] &&
                graph[u][v] > 0 &&
                dist[u] != INT_MAX &&
                dist[u] <= INT_MAX - graph[u][v] &&
                dist[u] + graph[u][v] < dist[v]) {

                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex\tDistance from source\n");

    for (int i = 0; i < V; i++) {
        if (dist[i] == INT_MAX) {
            printf("%d\tUnreachable\n", i);
        } else {
            printf("%d\t%d\n", i, dist[i]);
        }
    }
}

int main(void) {
    int graph[V][V] = {
        {0, 10, 0, 5, 0},
        {10, 0, 1, 2, 0},
        {0, 1, 0, 9, 4},
        {5, 2, 9, 0, 2},
        {0, 0, 4, 2, 0}
    };

    dijkstra(graph, 0);

    return 0;
}

Output:

Vertex  Distance from source
0       0
1       7
2       8
3       5
4       7

Distances are measured from source vertex 0.

For example, the shortest distance to vertex 1 is 7, through the path 0 → 3 → 1, whose weights are 5 + 2.

Dijkstra's Time Complexity

With an adjacency matrix and linear minimum selection, the time complexity is O(V²).

Using an adjacency list and a suitable priority queue, implementations commonly achieve O((V + E) log V), depending on the data structures used.

9. Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a spanning tree of a connected, undirected, weighted graph with the minimum possible total edge weight.

A spanning tree:

• Connects all vertices.

• Contains no cycles.

• Has exactly V - 1 edges for V vertices.

An MST is used in network design, road planning, communication infrastructure, and other cost-minimization problems.

Example

Consider this weighted graph:

A --1-- B
|       |
4       2
|       |
C --3-- D

The edges have weights:

• A–B: 1

• B–D: 2

• C–D: 3

• A–C: 4

The MST chooses A–B, B–D, and C–D.

Total weight:

[
1 + 2 + 3 = 6
]

All four vertices are connected without forming a cycle.

Common MST Algorithms

Kruskal's Algorithm: Sorts edges by weight and adds the next lightest edge that does not create a cycle.

Prim's Algorithm: Grows a tree by repeatedly adding the lowest-weight edge connecting the current tree to a new vertex.

Both algorithms find an MST for a connected, undirected, weighted graph. For a disconnected graph, their natural extensions produce a minimum spanning forest.

Kruskal's Algorithm in C

The following program implements Kruskal's algorithm using an edge list and Disjoint Set Union (DSU).

#include 
#include 

#define V 4
#define E 5

struct Edge {
    int src;
    int dest;
    int weight;
};

int parent[V];
int rankSet[V];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }

    return parent[x];
}

void unionSets(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);

    if (rootA == rootB) {
        return;
    }

    if (rankSet[rootA] < rankSet[rootB]) {
        parent[rootA] = rootB;
    } else if (rankSet[rootA] > rankSet[rootB]) {
        parent[rootB] = rootA;
    } else {
        parent[rootB] = rootA;
        rankSet[rootA]++;
    }
}

int compareEdges(const void *a, const void *b) {
    const struct Edge *x = a;
    const struct Edge *y = b;

    if (x->weight < y->weight) return -1;
    if (x->weight > y->weight) return 1;
    return 0;
}

int main(void) {
    struct Edge edges[E] = {
        {0, 1, 10},
        {0, 2, 6},
        {0, 3, 5},
        {1, 3, 15},
        {2, 3, 4}
    };

    for (int i = 0; i < V; i++) {
        parent[i] = i;
        rankSet[i] = 0;
    }

    qsort(edges, E, sizeof(edges[0]), compareEdges);

    int selected = 0;
    int totalWeight = 0;

    printf("Edges in MST:\n");

    for (int i = 0; i < E && selected < V - 1; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;

        if (find(u) != find(v)) {
            unionSets(u, v);

            printf("%d - %d : %d\n", u, v, edges[i].weight);

            totalWeight += edges[i].weight;
            selected++;
        }
    }

    if (selected != V - 1) {
        printf("Graph is disconnected; no spanning tree exists\n");
    } else {
        printf("Total MST Weight: %d\n", totalWeight);
    }

    return 0;
}

Output:

Edges in MST:
2 - 3 : 4
0 - 3 : 5
0 - 1 : 10
Total MST Weight: 19

The selected edges connect all four vertices without forming a cycle. Their total weight is 4 + 5 + 10 = 19.

MST Complexity

For Kruskal's algorithm:

• Sorting edges takes O(E log E).

• DSU operations are nearly constant amortized time with path compression and union by rank.

• Overall complexity is O(E log E).

For Prim's algorithm, complexity depends on the implementation. An adjacency matrix implementation takes O(V²), while an adjacency list with a binary heap commonly takes O((V + E) log V).

Graph Representation and Algorithm Summary

Real-World Applications of Graphs

1. Google Maps and Navigation: Cities or locations are vertices, and roads are edges.

2. Social Networks: Users are vertices, and relationships are edges.

3. Computer Networks: Devices are vertices connected by communication links.

4. Web Search: Web pages are vertices, and hyperlinks are directed edges.

5. Project Scheduling: Dependencies can be represented by directed graphs.

6. Recommendation Systems: Relationships between users and products can be modeled as graphs.

7. Network Design: MST algorithms help reduce the cost of connecting locations.

8. Route Optimization: Shortest-path algorithms calculate minimum-cost routes.

Key Takeaways

• A Graph consists of vertices and edges.

• Directed graphs have edge directions; undirected graphs do not.

• Weighted graphs associate costs or distances with edges.

• An adjacency matrix uses O(V²) space.

• An adjacency list uses O(V + E) space.

• BFS uses a Queue and finds shortest paths in unweighted graphs.

• DFS explores paths deeply before backtracking.

• Dijkstra's algorithm requires nonnegative edge weights.

• Kruskal's and Prim's algorithms are used to find Minimum Spanning Trees.

• Choosing the correct graph representation and algorithm depends on graph size, density, edge weights, and the problem being solved.

Conclusion

Graphs are essential data structures for representing relationships, routes, and networks. By learning graph representations, BFS, DFS, shortest-path algorithms, and Minimum Spanning Trees, you develop the foundation for solving real-world connectivity and optimization problems.

Practice each program, change the graph edges, and test disconnected graphs, directed graphs, and graphs with different weights to understand how the algorithms behave.