🕸️ Graphs

📖 What is a Graph?

A Graph is a non-linear data structure made of a set of vertices and a set of edges that connect pairs of vertices. Graphs are useful when the relationships between items are as important as the items themselves.

🧠 Essential Graph Terms

↔️ Common Types of Graphs

🧮 How Do We Store a Graph?

The three standard representations are Edge List, Adjacency Matrix, and Adjacency List. The best choice depends on how many vertices/edges the Graph has and which operations are frequent.

🧩 One Graph, Three Representations

Use the undirected Graph:

V = {0, 1, 2, 3, 4}

E = {
    (0,1),
    (0,2),
    (1,3),
    (2,3),
    (3,4),
    (1,4)
}

0 1
0 2
1 3
2 3
3 4
1 4

    0 1 2 3 4
0 : 0 1 1 0 0
1 : 1 0 0 1 1
2 : 1 0 0 1 0
3 : 0 1 1 0 1
4 : 0 1 0 1 0

0 : 1 2
1 : 0 3 4
2 : 0 3
3 : 1 2 4
4 : 1 3

🎬 Graph Representation Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Graph Representation Visualizer Build edges one by one and switch between Edge List, Adjacency Matrix, and Adjacency List views.

Edges

Graph Type Undirected Directed

Representation Edge List Adjacency Matrix Adjacency List

  Load / Apply

Graph

Edge List

—

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

Press Next to add the first edge.

💻 Store a Graph using an Edge List

For the first Graph program, we use the simplest representation: each row stores the two endpoint vertices of one edge.

#include <stdio.h>

#define MAX_EDGES 100

int main()
{
    int vertices;
    int edges;
    int edgeList[MAX_EDGES][2];
    int i;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d",
              &edgeList[i][0],
              &edgeList[i][1]);
    }

    printf("Vertices: %d\n", vertices);
    printf("Edges:\n");

    for(i = 0; i < edges; i++)
    {
        printf("%d -> %d\n",
               edgeList[i][0],
               edgeList[i][1]);
    }

    return 0;
}

5 6
0 1
0 2
1 3
2 3
3 4
1 4

Vertices: 5
Edges:
0 -> 1
0 -> 2
1 -> 3
2 -> 3
3 -> 4
1 -> 4

🔎 Trace Edge List Representation

—

⚡ Representation Complexity

🧮 Adjacency Matrix Representation

An Adjacency Matrix stores a Graph in a two-dimensional array. For V vertices, we create a V × V matrix. The row represents the starting vertex and the column represents the ending vertex.

↔️ Directed, Undirected, Weighted & Unweighted

matrix[u][v] = value;
matrix[v][u] = value;

matrix[u][v] = value;

0 = no edge
1 = edge exists

matrix[u][v] = weight

⚙️ Insert Edge, Check Edge & Iterate Neighbors

// directed
matrix[u][v] = value;

// undirected
matrix[u][v] = value;
matrix[v][u] = value;

if(matrix[u][v] != 0)
    // edge exists

for(v = 0; v < vertices; v++)
{
    if(matrix[u][v] != 0)
        // v is adjacent to u
}

🎬 Adjacency Matrix Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Adjacency Matrix Visualizer Watch each edge update its exact matrix cell, then perform an O(1) edge check.

Edges (u-v:weight)

Graph Type Undirected Directed

Weight Mode Weighted Unweighted

Check Edge

Vertices

  Load / Apply

Graph

Adjacency Matrix

Current Edge—

Cell—

Value—

Operation—

Result—

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Adjacency Matrix in C

This program supports directed/undirected and weighted/unweighted construction. The sample demonstrates an undirected weighted Graph.

#include <stdio.h>

#define MAX 10

int main()
{
    int matrix[MAX][MAX] = {0};
    int vertices;
    int edges;
    int directed;
    int weighted;
    int i;
    int j;
    int u;
    int v;
    int w;
    int value;

    scanf("%d %d %d %d",
          &vertices,
          &edges,
          &directed,
          &weighted);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d %d", &u, &v, &w);

        value = weighted ? w : 1;

        matrix[u][v] = value;

        if(!directed)
            matrix[v][u] = value;
    }

    printf("Adjacency Matrix:\n");

    for(i = 0; i < vertices; i++)
    {
        for(j = 0; j < vertices; j++)
            printf("%d ", matrix[i][j]);

        printf("\n");
    }

    u = 1;
    v = 4;

    if(matrix[u][v] != 0)
        printf("Edge %d -> %d exists with value %d\n",
               u, v, matrix[u][v]);
    else
        printf("Edge %d -> %d does not exist\n", u, v);

    return 0;
}

5 6 0 1
0 1 4
0 2 2
1 3 5
2 3 1
3 4 3
1 4 6

Adjacency Matrix:
0 4 2 0 0 
4 0 0 5 6 
2 0 0 1 0 
0 5 1 0 3 
0 6 0 3 0 
Edge 1 -> 4 exists with value 6

🔎 Trace Adjacency Matrix Construction

—

⚡ Adjacency Matrix Complexity

🔗 Adjacency List Representation

An Adjacency List stores, for every vertex, only the neighbors that are actually connected to it. This makes it especially efficient for sparse Graphs, where the number of edges is much smaller than V².

🧱 How an Adjacency List is Stored

In C, a common implementation uses an array of linked-list head pointers. Each linked-list node stores the neighbor vertex, optional edge weight, and a pointer to the next neighbor.

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

struct Node *adj[MAX] = {NULL};

↔️ Adjacency List Rules

addEdge(adj, u, v, value);

addEdge(adj, u, v, value);
addEdge(adj, v, u, value);

⚙️ Insert Edge, Check Edge & Visit Neighbors

newNode->next = adj[u];
adj[u] = newNode;

current = adj[u];

while(current != NULL)
{
    if(current->vertex == v)
        // edge exists

    current = current->next;
}

current = adj[u];

while(current != NULL)
{
    // process current->vertex
    current = current->next;
}

🎬 Adjacency List Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Adjacency List Visualizer Watch each edge create linked-list nodes and inspect the final neighbors of any vertex.

Edges (u-v:weight)

Graph Type Undirected Directed

Weight Mode Weighted Unweighted

Inspect Vertex

Vertices

  Load / Apply

Graph

Adjacency Lists

Current Edge—

List Head—

Inserted Node—

Operation—

Result—

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Weighted Adjacency List in C

This implementation uses dynamic memory and linked lists. The sample uses an undirected weighted Graph and inserts new neighbor nodes at the head.

#include <stdio.h>
#include <stdlib.h>

#define MAX 10

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

struct Node *createNode(int vertex, int weight)
{
    struct Node *newNode =
        (struct Node *)malloc(sizeof(struct Node));

    newNode->vertex = vertex;
    newNode->weight = weight;
    newNode->next = NULL;

    return newNode;
}

void addEdge(struct Node *adj[],
             int u,
             int v,
             int weight)
{
    struct Node *newNode =
        createNode(v, weight);

    newNode->next = adj[u];
    adj[u] = newNode;
}

void printGraph(struct Node *adj[], int vertices)
{
    int i;
    struct Node *current;

    for(i = 0; i < vertices; i++)
    {
        printf("%d:", i);

        current = adj[i];

        while(current != NULL)
        {
            printf(" (%d,%d)",
                   current->vertex,
                   current->weight);

            current = current->next;
        }

        printf("\n");
    }
}

int main()
{
    struct Node *adj[MAX] = {NULL};
    int vertices;
    int edges;
    int directed;
    int weighted;
    int i;
    int u;
    int v;
    int w;
    int value;

    scanf("%d %d %d %d",
          &vertices,
          &edges,
          &directed,
          &weighted);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d %d", &u, &v, &w);

        value = weighted ? w : 1;

        addEdge(adj, u, v, value);

        if(!directed)
            addEdge(adj, v, u, value);
    }

    printf("Adjacency List:\n");
    printGraph(adj, vertices);

    return 0;
}

5 6 0 1
0 1 4
0 2 2
1 3 5
2 3 1
3 4 3
1 4 6

Adjacency List:
0: (2,2) (1,4)
1: (4,6) (3,5) (0,4)
2: (3,1) (0,2)
3: (4,3) (2,1) (1,5)
4: (1,6) (3,3)

🔎 Trace Adjacency List Construction

—

⚡ Adjacency List Complexity

🌊 Breadth-First Search (BFS)

Breadth-First Search explores a Graph level by level. Starting from one vertex, it first visits all immediately reachable neighbors, then their unvisited neighbors, and continues outward.

🚶 Why BFS Uses a Queue

When a vertex is discovered, it is added at the rear of the Queue. The vertex that has been waiting the longest is removed from the front. This FIFO behavior creates the level-by-level traversal order.

🧠 BFS Algorithm

BFS(adj, start)

1. Mark every vertex unvisited.

2. Mark start as visited.
3. Enqueue start.

4. While Queue is not empty:

      current = Dequeue()

      Visit current

      For each neighbor of current:

          If neighbor is not visited:

              Mark neighbor visited
              Enqueue neighbor

🧩 BFS from Vertex 0

Use the same undirected Graph from the representation lessons:

Edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4
1 - 4

0 : 1 2
1 : 0 3 4
2 : 0 3
3 : 1 2 4
4 : 3 1

🎬 BFS Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Breadth-First Search Visualizer Watch visited vertices, the Queue, active neighbors, and BFS output change together.

Edges

Graph Type Undirected Directed

Start Vertex

Vertices

  Load / Apply

Graph

BFS State

Queue

visited[]

Adjacency Lists

Traversal Output

Current —

Neighbor —

Front 0

Rear 0

Operation —

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 BFS using Queue in C

This program stores the undirected Graph as adjacency lists inside arrays: adj[u][0 ... degree[u]-1]. BFS then uses visited[] and an array-based Queue.

#include <stdio.h>

#define MAX 10

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int visited[MAX] = {0};
    int queue[MAX];
    int vertices;
    int edges;
    int start;
    int front = 0;
    int rear = 0;
    int i;
    int u;
    int v;
    int current;
    int neighbor;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        adj[v][degree[v]] = u;
        degree[v]++;
    }

    scanf("%d", &start);

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

    printf("BFS: ");

    while(front < rear)
    {
        current = queue[front];
        front++;

        printf("%d ", current);

        for(i = 0; i < degree[current]; i++)
        {
            neighbor = adj[current][i];

            if(!visited[neighbor])
            {
                visited[neighbor] = 1;
                queue[rear] = neighbor;
                rear++;
            }
        }
    }

    printf("\n");

    return 0;
}

5 6
0 1
0 2
1 3
2 3
3 4
1 4
0

BFS: 0 1 2 3 4 

🔎 Trace BFS with Queue + visited[]

—

⚡ BFS Complexity

🌍 Where BFS is Used

🧭 Depth-First Search (DFS)

Depth-First Search explores one path as deeply as possible before returning to the most recent vertex that still has an unvisited neighbor.

📚 Why Recursive DFS Uses the Call Stack

When DFS moves from a vertex to one unvisited neighbor, the current function call is not discarded. It waits on the Call Stack while the recursive call explores deeper vertices. When the deeper call finishes, execution returns to the waiting call and continues with its next neighbor.

🧠 Recursive DFS Algorithm

DFS(adj, current)

1. Mark current as visited.
2. Visit current.

3. For each neighbor of current:

      If neighbor is not visited:

          DFS(adj, neighbor)

🧩 DFS from Vertex 0

Use the same undirected Graph:

Edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4
1 - 4

0 : 1 2
1 : 0 3 4
2 : 0 3
3 : 1 2 4
4 : 3 1

🎬 DFS Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Depth-First Search Visualizer Watch recursion, backtracking, visited vertices, active neighbors, and DFS output together.

Edges

Graph Type Undirected Directed

Start Vertex

Vertices

  Load / Apply

Graph

DFS State

Recursion Call Stack

visited[]

Adjacency Lists

Traversal Output

Current —

Neighbor —

Depth 0

Stack Top —

Operation —

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Recursive DFS in C

This program stores the Graph using adjacency-list arrays and performs recursive DFS. Each recursive call has its own local i, neighbor, and current.

#include <stdio.h>

#define MAX 10

void dfs(int adj[][MAX],
         int degree[],
         int visited[],
         int current)
{
    int i;
    int neighbor;

    visited[current] = 1;
    printf("%d ", current);

    for(i = 0; i < degree[current]; i++)
    {
        neighbor = adj[current][i];

        if(!visited[neighbor])
            dfs(adj,
                degree,
                visited,
                neighbor);
    }
}

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int visited[MAX] = {0};
    int vertices;
    int edges;
    int start;
    int i;
    int u;
    int v;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        adj[v][degree[v]] = u;
        degree[v]++;
    }

    scanf("%d", &start);

    printf("DFS: ");
    dfs(adj, degree, visited, start);
    printf("\n");

    return 0;
}

5 6
0 1
0 2
1 3
2 3
3 4
1 4
0

DFS: 0 1 3 2 4 

🔎 Trace Recursive DFS

—

⚡ DFS Complexity

🌍 Where DFS is Used

🔁 Detecting Cycles in Graphs

A cycle exists when a traversal can leave a vertex, follow Graph edges, and eventually return to a previously active part of the traversal without simply reversing the same undirected parent edge.

↔️ Cycle Detection using Parent Tracking

During DFS, suppose we are at vertex current and inspect neighbor. If the neighbor is unvisited, recurse normally. If it is already visited, it forms a cycle only when it is not the parent of the current vertex.

neighbor == parent

visited[neighbor] == 1
AND
neighbor != parent

➡️ Cycle Detection using a Recursion Stack

For a directed Graph, a normal visited[] array is not enough. A visited vertex may belong to an already completed DFS branch and therefore may not create a cycle. We additionally maintain recStack[].

visited[current] = 1;
recStack[current] = 1;

recStack[current] = 0;

🧠 Cycle Detection Algorithms

DFS(current, parent)

mark current visited

for each neighbor:

    if neighbor is unvisited:
        if DFS(neighbor, current)
            return cycle

    else if neighbor != parent:
        return cycle

return no cycle

DFS(current)

visited[current] = 1
recStack[current] = 1

for each neighbor:

    if neighbor is unvisited:
        if DFS(neighbor)
            return cycle

    else if recStack[neighbor] == 1:
        return cycle

recStack[current] = 0
return no cycle

🧩 Understanding the Two Cycle Signals

0 - 1
|   /
|  /
2 - 3 - 4

0 → 1 → 2
↑       |
|_______|

🎬 Cycle Detection Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Graph Cycle Detection Visualizer Switch between Undirected Parent Tracking and Directed Recursion-Stack detection.

Edges

Detection Mode Undirected + Parent Directed + recStack[]

Vertices

  Load / Apply

Graph

DFS Cycle State

Recursion Call Stack

visited[]

parent[]

Adjacency Lists

Current —

Neighbor —

Parent —

Operation —

Result Checking

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Undirected Cycle Detection using DFS + Parent

The program checks every component and passes the parent vertex into each recursive DFS call.

#include <stdio.h>

#define MAX 10

int hasCycle(int adj[][MAX],
             int degree[],
             int visited[],
             int current,
             int parent)
{
    int i;
    int neighbor;

    visited[current] = 1;

    for(i = 0; i < degree[current]; i++)
    {
        neighbor = adj[current][i];

        if(!visited[neighbor])
        {
            if(hasCycle(adj,
                        degree,
                        visited,
                        neighbor,
                        current))
                return 1;
        }
        else if(neighbor != parent)
        {
            return 1;
        }
    }

    return 0;
}

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int visited[MAX] = {0};
    int vertices;
    int edges;
    int i;
    int u;
    int v;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        adj[v][degree[v]] = u;
        degree[v]++;
    }

    for(i = 0; i < vertices; i++)
    {
        if(!visited[i])
        {
            if(hasCycle(adj,
                        degree,
                        visited,
                        i,
                        -1))
            {
                printf("Cycle Found\n");
                return 0;
            }
        }
    }

    printf("No Cycle\n");

    return 0;
}

5 5
0 1
1 2
2 0
2 3
3 4

Cycle Found

🔎 Trace Undirected Cycle Detection

—

💻 Directed Cycle Detection using DFS + recStack[]

The program marks each active recursive vertex in recStack[]. Reaching another active vertex means a directed cycle exists.

#include <stdio.h>

#define MAX 10

int hasDirectedCycle(int adj[][MAX],
                     int degree[],
                     int visited[],
                     int recStack[],
                     int current)
{
    int i;
    int neighbor;

    visited[current] = 1;
    recStack[current] = 1;

    for(i = 0; i < degree[current]; i++)
    {
        neighbor = adj[current][i];

        if(!visited[neighbor])
        {
            if(hasDirectedCycle(adj,
                                degree,
                                visited,
                                recStack,
                                neighbor))
                return 1;
        }
        else if(recStack[neighbor])
        {
            return 1;
        }
    }

    recStack[current] = 0;
    return 0;
}

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int visited[MAX] = {0};
    int recStack[MAX] = {0};
    int vertices;
    int edges;
    int i;
    int u;
    int v;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;
    }

    for(i = 0; i < vertices; i++)
    {
        if(!visited[i])
        {
            if(hasDirectedCycle(adj,
                                degree,
                                visited,
                                recStack,
                                i))
            {
                printf("Cycle Found\n");
                return 0;
            }
        }
    }

    printf("No Cycle\n");

    return 0;
}

5 5
0 1
1 2
2 0
2 3
3 4

Cycle Found

🔎 Trace Directed Cycle Detection

—

⚡ Cycle Detection Complexity

📋 Topological Ordering of a Directed Graph

A Topological Sort is a linear ordering of the vertices of a directed Graph such that for every directed edge u → v, vertex u appears before vertex v.

🚫 Why Cycles Make Topological Ordering Impossible

Suppose a directed cycle contains:

A → B → C → A

The dependencies demand A before B, B before C, and C before A. Those three requirements cannot all be true in one linear order. Therefore a directed Graph with a cycle has no valid topological ordering.

🚶 Topological Sort using indegree[] + Queue

Kahn's Algorithm repeatedly processes vertices with no remaining prerequisites. The indegree[] array stores how many incoming edges each vertex currently has.

1. Compute indegree of every vertex.

2. Enqueue every vertex whose indegree is 0.

3. While Queue is not empty:

      current = Dequeue()

      append current to topological order

      for each outgoing neighbor:

          indegree[neighbor]--

          if indegree[neighbor] becomes 0:
              Enqueue neighbor

4. If processed vertex count != V:
      cycle exists
   else:
      topological order is valid

📚 Topological Sort using DFS Finishing Order

DFS(u)

mark u visited

for each unvisited neighbor v:
    DFS(v)

push u onto Stack

🧩 Kahn's Algorithm Step by Step

Vertices: 0, 1, 2, 3, 4, 5

Edges:
5 → 2
5 → 0
4 → 0
4 → 1
2 → 3
3 → 1

The initial Queue is [4, 5]. Processing those vertices gradually reduces other indegrees to zero.

🎬 Topological Sort Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Kahn's Topological Sort Visualizer Watch indegree[], the Queue, processed vertices, and topological order change together.

Directed Edges

Vertices

Example Mode DAG Example Cyclic Example

  Load / Apply

Directed Graph

Kahn's Algorithm State

Queue of indegree-0 Vertices

indegree[]

Adjacency Lists

Topological Order

Current —

Neighbor —

Processed 0

Operation —

Result Checking

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Kahn's Topological Sort in C

This program builds directed adjacency lists in arrays, computes indegree[], uses an array-based Queue, stores the output in order[], and checks whether every vertex was processed.

#include <stdio.h>

#define MAX 10

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int indegree[MAX] = {0};
    int queue[MAX];
    int order[MAX];
    int vertices;
    int edges;
    int front = 0;
    int rear = 0;
    int count = 0;
    int i;
    int u;
    int v;
    int current;
    int neighbor;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        indegree[v]++;
    }

    for(i = 0; i < vertices; i++)
    {
        if(indegree[i] == 0)
        {
            queue[rear] = i;
            rear++;
        }
    }

    while(front < rear)
    {
        current = queue[front];
        front++;

        order[count] = current;
        count++;

        for(i = 0; i < degree[current]; i++)
        {
            neighbor = adj[current][i];
            indegree[neighbor]--;

            if(indegree[neighbor] == 0)
            {
                queue[rear] = neighbor;
                rear++;
            }
        }
    }

    if(count != vertices)
    {
        printf("Topological ordering not possible\n");
    }
    else
    {
        printf("Topological Order: ");

        for(i = 0; i < count; i++)
            printf("%d ", order[i]);

        printf("\n");
    }

    return 0;
}

6 6
5 2
5 0
4 0
4 1
2 3
3 1

Topological Order: 4 5 2 0 3 1 

Input:
3 3
0 1
1 2
2 0

Output:
Topological ordering not possible

🔎 Trace Kahn's Algorithm

—

⚡ Topological Sort Complexity

🧩 Connected Components in an Undirected Graph

A connected component is a maximal group of vertices in an undirected Graph where every vertex in that group is reachable from every other vertex in the same group.

🔗 Connected and Disconnected Graphs

Number of connected components = 1

Number of connected components > 1

📚 Finding Components using DFS

components = 0

for every vertex v:

    if v is unvisited:

        components++

        DFS(v)

        during DFS:
            mark each reached vertex visited
            componentId[vertex] = components

The outer loop is what makes the algorithm work for disconnected Graphs. DFS completely explores one component before the loop searches for the next unvisited vertex.

🚶 Finding Components using BFS

BFS can be used instead of DFS without changing the final grouping. The difference is only the traversal order inside each component.

for each unvisited vertex v:

    components++

    mark v visited
    enqueue v

    while Queue is not empty:

        current = dequeue

        componentId[current] = components

        for each neighbor:

            if neighbor is unvisited:
                mark visited
                enqueue neighbor

🧠 Counting Components

Vertices: 0 1 2 3 4 5 6 7

Edges:
0 - 1
1 - 2
3 - 4
5 - 6
6 - 7

The Graph therefore contains 3 connected components.

🎬 Connected Components Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Connected Components Visualizer Switch between DFS and BFS and watch each component receive its own ID.

Edges

Traversal DFS BFS

Vertices

Preset 3 Components Connected Graph Includes Isolated Vertex

  Load / Apply

Undirected Graph

Component Traversal State

DFS Call Stack

visited[]

componentId[]

Adjacency Lists

Current —

Neighbor —

Component 0

Operation —

Count 0

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Connected Components using DFS in C

This program counts connected components and assigns a componentId[] to every vertex.

#include <stdio.h>

#define MAX 10

void dfsComponent(int adj[][MAX],
                  int degree[],
                  int visited[],
                  int componentId[],
                  int current,
                  int component)
{
    int i;
    int neighbor;

    visited[current] = 1;
    componentId[current] = component;

    for(i = 0; i < degree[current]; i++)
    {
        neighbor = adj[current][i];

        if(!visited[neighbor])
            dfsComponent(adj,
                         degree,
                         visited,
                         componentId,
                         neighbor,
                         component);
    }
}

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int visited[MAX] = {0};
    int componentId[MAX] = {0};
    int vertices;
    int edges;
    int components = 0;
    int i;
    int u;
    int v;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        adj[v][degree[v]] = u;
        degree[v]++;
    }

    for(i = 0; i < vertices; i++)
    {
        if(!visited[i])
        {
            components++;

            dfsComponent(adj,
                         degree,
                         visited,
                         componentId,
                         i,
                         components);
        }
    }

    printf("Components: %d\n", components);

    for(i = 0; i < vertices; i++)
        printf("Vertex %d -> Component %d\n",
               i,
               componentId[i]);

    return 0;
}

8 5
0 1
1 2
3 4
5 6
6 7

Components: 3
Vertex 0 -> Component 1
Vertex 1 -> Component 1
Vertex 2 -> Component 1
Vertex 3 -> Component 2
Vertex 4 -> Component 2
Vertex 5 -> Component 3
Vertex 6 -> Component 3
Vertex 7 -> Component 3

🔎 Trace Connected Components using DFS

—

⚡ Connected Components Complexity

🛣️ Shortest Path in an Unweighted Graph

In an unweighted Graph, the shortest path from a source to a target is the path that uses the minimum number of edges. Because every edge has equal cost, Breadth-First Search can find these minimum edge distances.

🌊 Why BFS Gives the Minimum Edge Distance

BFS processes vertices in layers:

Level 0 : source
Level 1 : vertices one edge away
Level 2 : vertices two edges away
Level 3 : vertices three edges away
...

Therefore, the first time BFS discovers a vertex, it has reached that vertex using the smallest possible number of edges.

📊 Using distance[] and parent[]

distance[start] = 0

distance[neighbor]
    = distance[current] + 1

parent[neighbor] = current

To reconstruct the path, start at the target and repeatedly follow parent[] until -1:

Because reconstruction runs backward, reverse the collected sequence before printing it.

🧠 Unweighted Shortest Path Algorithm

Initialize:
    visited[] = 0
    distance[] = -1
    parent[] = -1

visited[start] = 1
distance[start] = 0
enqueue start

while Queue is not empty:

    current = dequeue

    for each neighbor of current:

        if neighbor is unvisited:

            visited[neighbor] = 1

            distance[neighbor]
                = distance[current] + 1

            parent[neighbor] = current

            enqueue neighbor

If distance[target] == -1:
    target is unreachable

Else:
    follow parent[] backward
    to reconstruct the path

🧩 Shortest Path from 0 to 5

Edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4
4 - 5
2 - 6

Starting from vertex 0, BFS discovers the vertices by increasing edge distance. For target 5:

distance[5] = 4

parent[5] = 4
parent[4] = 3
parent[3] = 1
parent[1] = 0
parent[0] = -1

🎬 Unweighted Shortest Path Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Unweighted Shortest Path Visualizer Watch BFS build distance[] and parent[], then reconstruct the final shortest path.

Edges

Start

Target

Vertices

Preset Reachable Target Unreachable Target

  Load / Apply

Undirected Graph

BFS Shortest-Path State

Queue

distance[]

parent[]

Adjacency Lists

Reconstructed Path

Current —

Neighbor —

Distance —

Operation —

Result Checking

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Shortest Path in an Unweighted Graph using BFS

This program computes minimum edge distance, records parent[], and reconstructs one shortest path from start to target.

#include <stdio.h>

#define MAX 10

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int visited[MAX] = {0};
    int distance[MAX];
    int parent[MAX];
    int queue[MAX];
    int path[MAX];
    int vertices;
    int edges;
    int start;
    int target;
    int front = 0;
    int rear = 0;
    int pathLength = 0;
    int i;
    int u;
    int v;
    int current;
    int neighbor;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < vertices; i++)
    {
        distance[i] = -1;
        parent[i] = -1;
    }

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        adj[v][degree[v]] = u;
        degree[v]++;
    }

    scanf("%d %d", &start, &target);

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

    while(front < rear)
    {
        current = queue[front];
        front++;

        for(i = 0; i < degree[current]; i++)
        {
            neighbor = adj[current][i];

            if(!visited[neighbor])
            {
                visited[neighbor] = 1;
                distance[neighbor] = distance[current] + 1;
                parent[neighbor] = current;

                queue[rear] = neighbor;
                rear++;
            }
        }
    }

    if(distance[target] == -1)
    {
        printf("Target unreachable\n");
    }
    else
    {
        current = target;

        while(current != -1)
        {
            path[pathLength] = current;
            pathLength++;
            current = parent[current];
        }

        printf("Distance: %d\n", distance[target]);
        printf("Path: ");

        for(i = pathLength - 1; i >= 0; i--)
            printf("%d ", path[i]);

        printf("\n");
    }

    return 0;
}

7 7
0 1
0 2
1 3
2 3
3 4
4 5
2 6
0 5

Distance: 4
Path: 0 1 3 4 5 

If distance[target] remains -1:

Target unreachable

🔎 Trace BFS Shortest Path

—

⚡ Unweighted Shortest Path Complexity

🎨 What is a Bipartite Graph?

A Graph is bipartite if its vertices can be divided into two disjoint sets so that every edge connects a vertex from one set to a vertex from the other set. No edge may connect two vertices inside the same set.

🟦🟨 Bipartite Graph = Valid 2-Coloring

Use two colors, represented here as 0 and 1. An uncolored vertex stores -1.

color[v] = -1   → not colored yet
color[v] =  0   → Set A
color[v] =  1   → Set B

Whenever an uncolored neighbor is discovered:

color[neighbor] = 1 - color[current]

If an already colored neighbor has the same color as the current vertex, the Graph cannot be bipartite.

🚶 Bipartite Check using BFS

Initialize color[] = -1

for every vertex start:

    if start is already colored:
        continue

    color[start] = 0
    enqueue start

    while Queue is not empty:

        current = dequeue

        for each neighbor:

            if neighbor is uncolored:
                color[neighbor]
                    = 1 - color[current]
                enqueue neighbor

            else if color[neighbor]
                    == color[current]:

                Graph is not bipartite

📚 Bipartite Check using DFS

DFS(current)

for each neighbor:

    if neighbor is uncolored:
        assign opposite color
        DFS(neighbor)

    else if same color:
        conflict

🔺 Why an Odd-Length Cycle is Not Bipartite

Along a cycle, colors must alternate:

A → B → A → B → ...

For an even cycle, this alternating pattern returns consistently to the starting vertex. For an odd cycle, the final edge forces two same-colored vertices to become adjacent.

Triangle:
0 - 1
 \ /
  2

Try:
0 = A
1 = B
2 must be A because of edge 1-2
but edge 2-0 connects A to A → conflict

🧩 Two-Coloring a Bipartite Graph

Edges:
0 - 1
1 - 2
2 - 3
3 - 0
3 - 4
4 - 5
5 - 2

Every listed edge crosses between Set A and Set B, so the Graph is bipartite.

🎬 Bipartite Graph Visualizer

INTERACTIVE ALGORITHM VISUALIZATION

CodeBhavya

🎬 Premium Bipartite Graph Checking Visualizer Switch between BFS and DFS while color[] separates vertices into two sets.

Edges

Traversal BFS DFS

Vertices

Preset Bipartite Example Odd Cycle Disconnected Example

  Load / Apply

Undirected Graph

2-Coloring State

BFS Queue

color[]

Adjacency Lists

Current Sets

Set A

Set B

Current —

Neighbor —

Color —

Operation —

Result Checking

Details: Press Next to begin.

← Previous Next → ▶ Auto Run Ⅱ Pause ↺ Reset

💻 Bipartite Graph Check using BFS in C

This program checks every connected component. The value -1 means uncolored, while colors 0 and 1 represent Set A and Set B.

#include <stdio.h>

#define MAX 10

int main()
{
    int adj[MAX][MAX];
    int degree[MAX] = {0};
    int color[MAX];
    int queue[MAX];
    int vertices;
    int edges;
    int start;
    int front;
    int rear;
    int i;
    int u;
    int v;
    int current;
    int neighbor;

    scanf("%d %d", &vertices, &edges);

    for(i = 0; i < vertices; i++)
        color[i] = -1;

    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &u, &v);

        adj[u][degree[u]] = v;
        degree[u]++;

        adj[v][degree[v]] = u;
        degree[v]++;
    }

    for(start = 0; start < vertices; start++)
    {
        if(color[start] != -1)
            continue;

        front = 0;
        rear = 0;

        color[start] = 0;
        queue[rear] = start;
        rear++;

        while(front < rear)
        {
            current = queue[front];
            front++;

            for(i = 0; i < degree[current]; i++)
            {
                neighbor = adj[current][i];

                if(color[neighbor] == -1)
                {
                    color[neighbor] = 1 - color[current];
                    queue[rear] = neighbor;
                    rear++;
                }
                else if(color[neighbor] == color[current])
                {
                    printf("Graph is Not Bipartite\n");
                    return 0;
                }
            }
        }
    }

    printf("Graph is Bipartite\n");

    for(i = 0; i < vertices; i++)
        printf("Vertex %d -> Set %c\n",
               i,
               color[i] == 0 ? 'A' : 'B');

    return 0;
}

6 7
0 1
1 2
2 3
3 0
3 4
4 5
5 2

Graph is Bipartite
Vertex 0 -> Set A
Vertex 1 -> Set B
Vertex 2 -> Set A
Vertex 3 -> Set B
Vertex 4 -> Set A
Vertex 5 -> Set B

3 3
0 1
1 2
2 0

Output:
Graph is Not Bipartite

🔎 Trace Bipartite Checking using BFS

—

⚡ Bipartite Checking Complexity

📊 Graph Representations & Core Algorithms — Comparison

🧭 Which Graph Algorithm Should I Choose?

⚡ Core Graph Complexity Summary

❓ Graph Interview Questions — Parts 1–10

🎯 20 Graph Practice Problems

Try every problem yourself first. Use Solve It Yourself to write and test your C program. Open Hint only when necessary, and use Show Program when you want to study the complete official solution.