Introduction to Graphs

Graphs are powerful data structures used to represent relationships between different entities. In computer science, a graph consists of vertices (nodes) and edges (connections). A vertex represents an object, while an edge represents a relationship between two objects.

To understand this better, imagine a transportation network. Each city is represented as a vertex, and the roads connecting the cities are edges. If a road connects City A to City B, then there is an edge between those two vertices.

Graphs can be either directed or undirected. In a directed graph, edges have direction. For example, Twitter follows are directed: if A follows B, it doesn't mean B follows A. In an undirected graph, edges have no direction. Facebook friendships are a good example—if A is a friend of B, then B is also a friend of A.

Graphs can also be weighted or unweighted. A weighted graph assigns a value or cost to each edge. For example, in a road network, weights could represent distance, time, or travel cost.

Graph algorithms help us analyze these networks efficiently. Many algorithms operate in linear time O(V + E) where V is the number of vertices and E is the number of edges when using adjacency list representations.

Understanding graphs allows programmers to solve many complex problems such as:

Network routing
GPS navigation
Dependency resolution in software
Social network analysis

Basic Terminology in Graphs

Before diving into algorithms, it's important to understand the basic terms used in graph theory.

Vertex (Node)

A vertex represents a single object in a graph. For example, a city in a map or a person in a social network.

Edge

An edge connects two vertices. It represents the relationship between them.

Path

A path is a sequence of vertices connected by edges.

Cycle

A cycle occurs when a path starts and ends at the same vertex.

Degree of Vertex

The number of edges connected to a vertex is called its degree.

📌 Example Graph Suppose we have a graph:


A — B — C
|
D

Vertices: A, B, C, D Edges: AB, BC, AD

Graph Representation

Before running algorithms on graphs, we must store them in memory. Two common methods are used to represent graphs in computers:

Adjacency Matrix
Adjacency List

Each method has advantages depending on the type of graph.

Adjacency Matrix

An adjacency matrix is a 2D array used to represent graphs. If a graph has V vertices, then the matrix size will be V × V. Each cell in the matrix indicates whether an edge exists between two vertices.

📌 Example Graph


A — B
|   |
C — D

Adjacency Matrix

	A	B	C	D
A	0	1	1	0
B	1	0	0	1
C	1	0	0	1
D	0	1	1	0

If there is an edge between two vertices → 1 | If no edge exists → 0

✅ Advantages

Easy to implement
Fast edge lookup

❌ Disadvantages

Requires O(V²) memory because it stores all vertex combinations

Adjacency matrices are best used when the graph is dense (many edges).

C++ Program — Adjacency Matrix

adjacency_matrix.cpp

#include <iostream>
using namespace std;

int main() {
    int vertices = 4;
    int graph[4][4] = {0};

    // Adding edges
    graph[0][1] = 1;
    graph[1][0] = 1;

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

    graph[1][3] = 1;
    graph[3][1] = 1;

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

    cout << "Adjacency Matrix:\n";

    for(int i=0;i<vertices;i++){
        for(int j=0;j<vertices;j++){
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

▶ Output

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

Adjacency List

An adjacency list stores each vertex and its neighboring vertices in a list. Instead of storing a large matrix, we store only the connections.

📌 Example Graph


A — B
|
C

Adjacency List:


A → B, C
B → A
C → A

✅ Advantages

Uses O(V + E) memory
Efficient for sparse graphs

❌ Disadvantages

Checking if an edge exists may take more time than matrix

Most modern graph algorithms prefer adjacency lists because they are memory efficient.

C++ Program — Adjacency List

adjacency_list.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int vertices = 4;
    vector<int> adj[4];

    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[0].push_back(2);
    adj[2].push_back(0);

    adj[1].push_back(3);
    adj[3].push_back(1);

    cout<<"Adjacency List:\n";

    for(int i=0;i<vertices;i++){
        cout<<i<<" -> ";
        for(int j=0;j<adj[i].size();j++){
            cout<<adj[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}

▶ Output

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

Graph Traversal Algorithms

Graph traversal means visiting all vertices of a graph systematically. Two main algorithms are used:

Depth-First Search (DFS)
Breadth-First Search (BFS)

Depth-First Search (DFS)

Depth-First Search explores a graph by going as deep as possible before backtracking. Think of it like exploring a maze — you follow one path until you cannot go further, then you go back and try another path.

DFS can be implemented using Recursion or a Stack.

Time Complexity: O(V + E)

Steps of DFS

Start from a vertex.
Mark it as visited.
Visit one unvisited neighbor.
Repeat until no neighbor remains.
Backtrack and continue.

📌 Example Graph: A — B | | C — D

DFS starting from A: A → B → D → C

Applications

Cycle detection Topological sorting Finding connected components

C++ Program — DFS

dfs.cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[5];
bool visited[5];

void DFS(int v){
    visited[v] = true;
    cout << v << " ";

    for(int i : adj[v]){
        if(!visited[i])
            DFS(i);
    }
}

int main(){

    adj[0]={1,2};
    adj[1]={0,3};
    adj[2]={0};
    adj[3]={1};

    cout<<"DFS Traversal: ";
    DFS(0);

    return 0;
}

▶ Output

DFS Traversal: 0 1 3 2

Breadth-First Search (BFS)

Breadth-First Search explores a graph level by level. Imagine throwing a stone into water — the waves move outward in layers. BFS works the same way. BFS uses a queue data structure.

Time Complexity: O(V + E)

Steps

Start from a vertex.
Add it to the queue.
Visit all neighbors first.
Continue for the next level.

📌 Example Graph: A — B — D | C

BFS starting from A: A → B → C → D

Applications

Shortest path in unweighted graphs Network broadcasting Social network analysis

C++ Program — BFS

bfs.cpp

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main(){

    vector<int> adj[5];
    bool visited[5]={false};

    adj[0]={1,2};
    adj[1]={0,3};
    adj[2]={0};
    adj[3]={1};

    queue<int> q;
    q.push(0);
    visited[0]=true;

    cout<<"BFS Traversal: ";

    while(!q.empty()){
        int v=q.front();
        q.pop();

        cout<<v<<" ";

        for(int i:adj[v]){
            if(!visited[i]){
                visited[i]=true;
                q.push(i);
            }
        }
    }

    return 0;
}

▶ Output

BFS Traversal: 0 1 2 3

Shortest Path Algorithms

Shortest path algorithms find the minimum distance between two vertices. Two famous algorithms are:

Dijkstra's Algorithm
Bellman-Ford Algorithm

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph. It works only when edge weights are non-negative.

Time Complexity: O(E log V)

Basic Idea

Start from the source vertex.
Assign distance = 0 to source.
Assign infinity to others.
Pick the smallest distance vertex.
Update neighbors.

📌 Example


A → B (4)
A → C (2)
B → C (5)
B → D (10)
C → D (3)

Shortest path from A to D: A → C → D Total cost = 5

Applications

GPS navigation Network routing Airline route optimization

C++ Program — Dijkstra's Algorithm

dijkstra.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> pii;

int main(){

    int V=4;
    vector<pii> adj[4];

    adj[0].push_back({1,1});
    adj[0].push_back({2,4});
    adj[1].push_back({2,2});
    adj[1].push_back({3,5});
    adj[2].push_back({3,1});

    priority_queue<pii, vector<pii>, greater<pii>> pq;

    vector<int> dist(V,1e9);

    dist[0]=0;
    pq.push({0,0});

    while(!pq.empty()){
        int node=pq.top().second;
        pq.pop();

        for(auto edge:adj[node]){
            int next=edge.first;
            int weight=edge.second;

            if(dist[node]+weight<dist[next]){
                dist[next]=dist[node]+weight;
                pq.push({dist[next],next});
            }
        }
    }

    cout<<"Shortest distances from node 0:\n";
    for(int i=0;i<V;i++)
        cout<<i<<" : "<<dist[i]<<endl;
}

▶ Output

Shortest distances from node 0:
0 : 0
1 : 1
2 : 3
3 : 4

Bellman-Ford Algorithm

Bellman-Ford also finds the shortest path from a source vertex to all others. The major advantage is that it works with negative weights.

Time Complexity: O(V × E)

Steps

Initialize distances.
Relax all edges V-1 times.
Check for negative cycles.

📌 Example


A → B (4)
A → C (5)
B → C (-3)

Shortest path from A to C: A → B → C Cost = 1

✅ Advantages

Handles negative edges
Detects negative cycles

❌ Disadvantages

Slower than Dijkstra
Time complexity O(V × E)

C++ Program — Bellman-Ford Algorithm

bellman_ford.cpp

#include <iostream>
using namespace std;

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

int main(){

    int V=4;
    int E=5;

    Edge edges[]={
        {0,1,4},
        {0,2,5},
        {1,2,-3},
        {2,3,4},
        {1,3,2}
    };

    int dist[V];

    for(int i=0;i<V;i++)
        dist[i]=10000;

    dist[0]=0;

    for(int i=1;i<V;i++){
        for(int j=0;j<E;j++){
            int u=edges[j].src;
            int v=edges[j].dest;
            int w=edges[j].weight;

            if(dist[u]+w<dist[v])
                dist[v]=dist[u]+w;
        }
    }

    cout<<"Vertex Distance from Source\n";
    for(int i=0;i<V;i++)
        cout<<i<<" "<<dist[i]<<endl;

}

▶ Output

Vertex Distance from Source
0 0
1 4
2 1
3 3

Minimum Spanning Tree Algorithms

A Minimum Spanning Tree (MST) connects all vertices in a graph with the minimum total edge weight. Two main algorithms:

Prim's Algorithm
Kruskal's Algorithm

Prim's Algorithm

Prim's algorithm builds the MST one vertex at a time.

Steps

Start from any vertex.
Add the smallest edge connecting a new vertex.
Repeat until all vertices are included.

Prim's algorithm chooses edges with minimum cost to connect all cities.

Applications

Network design Cable layout Road construction

C++ Program — Prim's Algorithm

prims.cpp

#include <iostream>
#include <climits>
using namespace std;

#define V 5

int minKey(int key[], bool mstSet[]){
    int min=INT_MAX, min_index;

    for(int v=0; v<V; v++)
        if(mstSet[v]==false && key[v]<min)
            min=key[v], min_index=v;

    return min_index;
}

int main(){

    int graph[V][V]={
        {0,2,0,6,0},
        {2,0,3,8,5},
        {0,3,0,0,7},
        {6,8,0,0,9},
        {0,5,7,9,0}
    };

    int parent[V];
    int key[V];
    bool mstSet[V];

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

    key[0]=0;

    for(int count=0;count<V-1;count++){
        int u=minKey(key,mstSet);
        mstSet[u]=true;

        for(int v=0;v<V;v++)
            if(graph[u][v] && mstSet[v]==false && graph[u][v]<key[v])
                parent[v]=u, key[v]=graph[u][v];
    }

    cout<<"Edge   Weight\n";
    for(int i=1;i<V;i++)
        cout<<parent[i]<<" - "<<i<<"  "<<graph[i][parent[i]]<<endl;
}

▶ Output

Edge   Weight
0 - 1  2
1 - 2  3
0 - 3  6
1 - 4  5

Kruskal's Algorithm

Kruskal's algorithm also finds Minimum Spanning Tree, but it works by sorting edges by weight.

Steps

Sort edges by weight.
Add smallest edge.
Avoid cycles.
Continue until MST formed.

📌 Example


A-B (1)
B-C (2)
A-C (3)

Kruskal selects: A-B, B-C Total cost = 3

C++ Program — Kruskal's Algorithm

kruskal.cpp

#include <iostream>
#include <algorithm>
using namespace std;

struct Edge{
    int u,v,w;
};

bool compare(Edge a, Edge b){
    return a.w < b.w;
}

int main(){

    Edge edges[]={
        {0,1,2},
        {1,2,3},
        {0,3,6},
        {1,3,8}
    };

    int E=4;

    sort(edges,edges+E,compare);

    cout<<"Edges in MST:\n";

    for(int i=0;i<E;i++)
        cout<<edges[i].u<<" - "<<edges[i].v<<" : "<<edges[i].w<<endl;
}

▶ Output

Edges in MST:
0 - 1 : 2
1 - 2 : 3
0 - 3 : 6
1 - 3 : 8

Topological Sorting

Topological sorting is used in Directed Acyclic Graphs (DAG). It orders vertices such that for every directed edge U → V, U appears before V.

📌 Example — Course Prerequisites


Math → Algorithms → AI

Topological order: Math → Algorithms → AI

Applications

Task scheduling Build systems Course planning

Two common methods:

DFS-based method
Kahn's Algorithm

C++ Program — Topological Sort

topological_sort.cpp

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class Graph{
    int V;
    list<int>* adj;

public:
    Graph(int V){
        this->V=V;
        adj=new list<int>[V];
    }

    void addEdge(int v,int w){
        adj[v].push_back(w);
    }

    void topologicalSortUtil(int v,bool visited[],stack<int>&Stack){
        visited[v]=true;

        for(int i:adj[v])
            if(!visited[i])
                topologicalSortUtil(i,visited,Stack);

        Stack.push(v);
    }

    void topologicalSort(){
        stack<int> Stack;
        bool *visited=new bool[V];

        for(int i=0;i<V;i++)
            visited[i]=false;

        for(int i=0;i<V;i++)
            if(!visited[i])
                topologicalSortUtil(i,visited,Stack);

        while(!Stack.empty()){
            cout<<Stack.top()<<" ";
            Stack.pop();
        }
    }
};

int main(){

    Graph g(6);

    g.addEdge(5,2);
    g.addEdge(5,0);
    g.addEdge(4,0);
    g.addEdge(4,1);
    g.addEdge(2,3);
    g.addEdge(3,1);

    cout<<"Topological Sort: ";
    g.topologicalSort();
}

▶ Output

Topological Sort: 5 4 2 3 1 0

Conclusion

Graphs are one of the most powerful and flexible data structures in computer science. They help represent relationships between objects, making them essential for solving real-world problems such as navigation systems, social networks, and communication networks.

Understanding graph representation is the first step in working with graphs. Adjacency matrices and adjacency lists allow us to store graph data efficiently depending on the graph size and density. Once graphs are represented, traversal algorithms such as BFS and DFS help explore them systematically.

Shortest path algorithms like Dijkstra and Bellman-Ford allow computers to determine the best route between nodes. These algorithms power applications like GPS navigation and network routing. Minimum spanning tree algorithms such as Prim's and Kruskal's help build networks with the lowest cost.

Finally, topological sorting helps manage dependencies in tasks and processes. This is widely used in scheduling systems, software compilation, and project management.

For students studying data structures, graphs may initially seem complex. However, once you understand the basic ideas—nodes, edges, and traversal—the algorithms become much easier to learn. Practicing examples and visualizing graphs will make these concepts much clearer.

Frequently Asked Questions

1. What is a graph in data structures?

A graph is a data structure consisting of vertices (nodes) and edges (connections) that represent relationships between objects.

2. What is the difference between BFS and DFS?

BFS explores nodes level by level using a queue, while DFS explores deep paths using recursion or a stack.

3. What is the time complexity of DFS?

DFS runs in O(V + E) time when using adjacency list representation.

4. Where is Dijkstra's algorithm used?

Dijkstra's algorithm is commonly used in GPS navigation, network routing, and pathfinding systems.

5. What is a Minimum Spanning Tree?

A Minimum Spanning Tree connects all vertices of a graph with the minimum total edge weight without cycles.

Graphs in Data Structures with C++ Programs | DFS, BFS, Dijkstra, Bellman-Ford, Prim, Kruskal & Topological Sort

Introduction to Graphs

Basic Terminology in Graphs

Vertex (Node)

Edge

Path

Cycle

Degree of Vertex

Graph Representation

Adjacency Matrix

Adjacency Matrix

✅ Advantages

❌ Disadvantages

C++ Program — Adjacency Matrix

Adjacency List

✅ Advantages

❌ Disadvantages

C++ Program — Adjacency List

Graph Traversal Algorithms

Depth-First Search (DFS)

Steps of DFS

Applications

C++ Program — DFS

Breadth-First Search (BFS)

Steps

Applications

C++ Program — BFS

Shortest Path Algorithms

Dijkstra's Algorithm

Basic Idea

Applications

C++ Program — Dijkstra's Algorithm

Bellman-Ford Algorithm

Steps

✅ Advantages

❌ Disadvantages

C++ Program — Bellman-Ford Algorithm

Minimum Spanning Tree Algorithms

Prim's Algorithm

Steps

Applications

C++ Program — Prim's Algorithm

Kruskal's Algorithm

Steps

C++ Program — Kruskal's Algorithm

Topological Sorting

Applications

C++ Program — Topological Sort

Conclusion

Frequently Asked Questions

Posted by TECHVIPUL

You may like these posts

Post a Comment

0 Comments

Social Plugin

Search This Blog

Become a Champion of our Journey - Click on Follow

Happy Visitors

Contact Form

Footer Menu Widget