🕸️ Module 5: Graph Data Structures & Algorithms

Understand non-linear networks G = (V, E), real-world systems, adjacency representations, BFS/DFS algorithms, and cycle detection.

💡 Introduction to Graphs

A Graph is a non-linear data structure used to represent relationships between different objects. It consists of a collection of vertices (also called nodes) and edges that connect these vertices.

Unlike arrays, linked lists, stacks, and queues, where data is organized in a sequence, graphs allow each node to connect with multiple other nodes. This makes graphs ideal for modeling complex real-world systems such as social networks, transportation networks, computer networks, and the Internet.

📐 Mathematical Representation:

G = (V, E)

Where:
• V represents the set of vertices (nodes).
• E represents the set of edges (connections).

❓ Why Do We Need Graphs?

Many real-world problems cannot be represented using linear data structures. Consider these examples:

🗺️ How does Google Maps find the shortest route?
👥 How does Facebook suggest mutual friends?
📸 How does Instagram recommend people to follow?
✈️ How do airlines determine connecting flights?
🚗 How does GPS navigation avoid traffic?
⚙️ How does a compiler determine the order of compiling files?

All these problems involve objects that are interconnected in multiple ways. Graphs provide an efficient way to model and solve such problems.

🌐 Real-Life Examples of Graphs

1. Social Networks

Each person is represented as a vertex, and friendships are represented as edges.

      Alice
      /   \
   Bob-----Charlie
      \
      David

2. Google Maps

Cities are vertices, and roads are edges. Each road can also have a weight, representing distance or travel time.

Delhi ----- Jaipur
   |            |
 Chandigarh --- Agra

3. Computer Networks

Each computer or router is a vertex. Network cables or wireless links are edges.

PC1 ---- Router ---- PC2
             |
          Server

4. Flight Network

Airports are vertices, and flights are edges.

Mumbai ---- Delhi
   |          |
Chennai ---- Kolkata

5. Website Links

Every webpage is a vertex. Hyperlinks between webpages form edges. This is essentially how search engines like Google model the web.

PageA ➔ PageB
  |       |
  v       v
PageC ➔ PageD

🕸️ Interactive Graph Terminology Inspector Canvas

Click Any Term Below to Highlight

👆 Click any of the 9 terminology cards below to dynamically highlight vertices & edges in the graph above!

📖 Complete Graph Terminology Dictionary

📍

Vertex (Node)

An individual fundamental entity or data element in the graph network.

🔗

Edge

A link or connection between two vertices representing relationships.

🤝

Adjacent Vertices

Two vertices that share a direct connecting edge.

📐

Degree of Vertex

Number of edges incident on a vertex (In-degree & Out-degree for digraphs).

🛤️

Path

A sequence of adjacent vertices connected by edges with no repeated edges.

🔄

Cycle

A closed path starting and ending at the exact same vertex.

🌐

Connected Graph

A graph where a path exists between every single pair of vertices.

🧩

Disconnected Graph

A graph containing two or more isolated components.

🧱

Connected Components

Maximal connected subgraphs where every vertex is reachable.

📐 2. Classification & 12 Types of Graphs

🔍 Click Any Card for Expanded View

1. Undirected Graph ↔️

Edges have no direction. Traversal is bidirectional: (u, v) == (v, u).

2. Directed Graph (Digraph) ➔

Edges have one-way directional arrows: u ➔ v does NOT imply v ➔ u.

3. Weighted Graph ⚖️

Each edge carries a numerical weight representing distance, cost, or latency.

4. Unweighted Graph ⚪

All edges carry equal unit weights (weight = 1). Shortest paths found via BFS.

5. Cyclic Graph 🔄

Contains at least 1 closed path loop starting and ending at the same node.

6. Acyclic Graph ➡️

A graph containing zero cycles or closed loops.

7. Directed Acyclic Graph (DAG) ⚡

Directed graph free of cycles! Essential for Topological Sorting & Task Scheduling.

8. Connected Graph 🌐

Every pair of vertices has a connecting path.

9. Disconnected Graph 🧩

Graph broken into 2 or more isolated subgraphs.

10. Complete Graph (Kn) 🕸️

Every vertex is connected directly to every other vertex. Total Edges = V*(V-1)/2.

11. Bipartite Graph 🎨

Vertices partitionable into 2 sets U & V such that no edge connects nodes in the same set.

12. Tree (Special Graph) 🌲

A connected acyclic undirected graph with exactly V - 1 edges.

📊 3. Graph Memory Representation Engine

Compare Adjacency Matrix (2D Array), Adjacency List (Array of Linked Lists), and Edge List (Tuples):

Representation	Space Complexity	Edge Query Time (u, v)	Find All Neighbors	Best Used For
Adjacency Matrix	O(V²)	O(1)	`O(V)`	Dense Graphs (E ≈ V²)
Adjacency List	O(V + E)	`O(Degree)`	O(Degree)	Sparse Graphs (E « V²)
Edge List	O(E)	`O(E)`	`O(E)`	Kruskal's MST Algorithm

⚡ C Struct & Memory Representation Tracker

🔍 4. Graph Traversals (BFS, DFS) & Cycle Detection

Step through Breadth-First Search (BFS) using a FIFO Queue, Depth-First Search (DFS) using Stack / Recursion, and Cycle Detection:

💻 Essential C Programs & Problems Suite for Graphs

Production-ready, compilable C implementations for BFS, DFS, Adjacency representations, and Cycle Detection.

1. Adjacency Matrix & Adjacency List Creation in C

#include <stdio.h>
#include <stdlib.h>
#define V 5

// Adjacency Matrix
int adjMatrix[V][V] = {0};

void addEdgeMatrix(int u, int v) {
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1;
}

// Adjacency List Node
struct Node {
    int dest;
    struct Node* next;
};

struct Node* adjList[V];

void addEdgeList(int u, int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->dest = v;
    newNode->next = adjList[u];
    adjList[u] = newNode;
}

2. Breadth-First Search (BFS) in C using Queue

void bfs(int startVertex) {
    int visited[V] = {0};
    int queue[V];
    int front = 0, rear = 0;

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

    printf("BFS Traversal: ");
    while (front < rear) {
        int curr = queue[front++];
        printf("%d ", curr);

        for (int i = 0; i < V; i++) {
            if (adjMatrix[curr][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[rear++] = i;
            }
        }
    }
    printf("\n");
}

3. Depth-First Search (DFS) Recursive Traversal in C

int visitedDFS[V] = {0};

void dfs(int vertex) {
    visitedDFS[vertex] = 1;
    printf("%d ", vertex);

    for (int i = 0; i < V; i++) {
        if (adjMatrix[vertex][i] == 1 && !visitedDFS[i]) {
            dfs(i);
        }
    }
}

4. Cycle Detection in Undirected Graph using DFS

int isCyclicUndirectedDFS(int u, int visited[], int parent) {
    visited[u] = 1;

    for (int v = 0; v < V; v++) {
        if (adjMatrix[u][v]) {
            if (!visited[v]) {
                if (isCyclicUndirectedDFS(v, visited, u)) return 1;
            } else if (v != parent) {
                return 1; // Back-edge detected!
            }
        }
    }
    return 0;
}

5. Cycle Detection in Directed Graph using Recursion Stack

int isCyclicDirectedDFS(int u, int visited[], int recStack[]) {
    visited[u] = 1;
    recStack[u] = 1;

    for (int v = 0; v < V; v++) {
        if (adjMatrix[u][v]) {
            if (!visited[v] && isCyclicDirectedDFS(v, visited, recStack)) return 1;
            else if (recStack[v]) return 1; // Cycle found in active recursion stack!
        }
    }

    recStack[u] = 0; // Backtrack from stack
    return 0;
}