A graph is a collection of vertices (or nodes) and edges that connect pairs of vertices. Graphs are a fundamental data structure used to represent relationships and connections in various domains, such as social networks, transportation systems, and computer networks.
Graphs can be represented in several ways:
Adjacency Matrix:
Adjacency List:
Here’s a simple C++ implementation of a graph using an adjacency list:
#include <iostream>
#include <vector>
using namespace std;
class Graph {
private:
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list
public:
Graph(int v) : V(v), adj(v) {}
void addEdge(int u, int v) {
adj[u].push_back(v); // Add edge from u to v
// If undirected, uncomment the next line:
// adj[v].push_back(u); // Add edge from v to u
}
void printGraph() {
for (int i = 0; i < V; ++i) {
cout << "Vertex " << i << ":";
for (int j : adj[i]) {
cout << " -> " << j;
}
cout << endl;
}
}
};
int main() {
Graph g(5); // Create a graph with 5 vertices
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph(); // Display the graph
return 0;
}
Two fundamental algorithms for traversing graphs are:
Depth-First Search (DFS):
Breadth-First Search (BFS):
Here’s a basic implementation of DFS using the previous graph representation:
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true; // Mark the current vertex as visited
cout << v << " "; // Process the current vertex
for (int i : adj[v]) {
if (!visited[i]) {
DFSUtil(i, visited); // Recur for all adjacent vertices
}
}
}
void DFS() {
vector<bool> visited(V, false);
for (int i = 0; i < V; ++i) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
}
Space Complexity:
Time Complexity:
Graphs are a powerful data structure that can model complex relationships and interactions. Understanding how to represent and traverse graphs is crucial for solving many computational problems, especially in network analysis, data organization, and algorithm design. Mastery of graph concepts enables developers to create efficient solutions in various real-world applications.
Open this section to load past papers