C++ Graphs
Graphs are fundamental data structures used to model relationships between entities. In C++, graphs are typically implemented using adjacency lists or adjacency matrices. Here’s an overview of graph concepts, representations, and algorithms.
Graph Basics
- Vertices (Nodes): The fundamental units of a graph.
- Edges: Connections between vertices. They can be directed (one-way) or undirected (two-way).
- Weighted Edges: Edges with associated weights or costs.
- Unweighted Edges: Edges without weights.
- Directed Graph (Digraph): Edges have a direction.
- Undirected Graph: Edges have no direction.
- Cyclic Graph: Contains cycles (paths that start and end at the same vertex).
- Acyclic Graph: No cycles are present.
Graph Representations
1. Adjacency Matrix
A 2D array where each cell (i, j) indicates whether there is an edge between vertex i and vertex j. For weighted graphs, it stores the weight of the edge.
Advantages:
- Easy to check if an edge exists.
- Simple to implement.
Disadvantages:
- Space complexity is (where is the number of vertices), which can be inefficient for sparse graphs.
Example:
cpp#include int>> adjMatrix(V, std::vector<int>(V, 0));
// Add edges
adjMatrix[0][1] = 1;
adjMatrix[1][2] = 1;
adjMatrix[2][3] = 1;
adjMatrix[3][0] = 1;
// Print adjacency matrix
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
std::cout << adjMatrix[i][j] << " ";
}
std::cout << std::endl;
}
return 0;
}
2. Adjacency List
A list of lists (or arrays) where each list contains the vertices adjacent to a particular vertex. For weighted graphs, each list entry can store a pair of the adjacent vertex and the edge weight.
Advantages:
- Space complexity is (where is the number of edges), which is efficient for sparse graphs.
- Efficient for iterating over edges.
Disadvantages:
- Checking for the existence of a particular edge can be slower.
Example:
cpp#include int>> adjList(V);
// Add edges
adjList[0].push_back(1);
adjList[1].push_back(2);
adjList[2].push_back(3);
adjList[3].push_back(0);
// Print adjacency list
for (int i = 0; i < V; ++i) {
std::cout << "Vertex " << i << ":";
for (const int& vertex : adjList[i]) {
std::cout << " -> " << vertex;
}
std::cout << std::endl;
}
return 0;
}
Graph Algorithms
1. Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack.
Example:
cpp#include int >>& adjList, std::vector<bool>& visited) {
visited[v] = true;
std::cout << v << " ";
for (const int& neighbor : adjList[v]) {
if (!visited[neighbor]) {
DFS(neighbor, adjList, visited);
}
}
}
int main() {
const int V = 4; // Number of vertices
std::vectorint>> adjList(V);
// Add edges
adjList[0].push_back(1);
adjList[1].push_back(2);
adjList[2].push_back(3);
adjList[3].push_back(0);
std::vector<bool> visited(V, false);
// Perform DFS
std::cout << "DFS traversal starting from vertex 0: ";
DFS(0, adjList, visited);
std::cout << std::endl;
return 0;
}
2. Breadth-First Search (BFS)
BFS explores all neighbors at the present depth level before moving on to nodes at the next depth level. It uses a queue to keep track of the vertices to be explored.
Example:
cpp#include int >>& adjList) {
std::vector<bool> visited(adjList.size(), false);
std::queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
std::cout << v << " ";
for (const int& neighbor : adjList[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
const int V = 4; // Number of vertices
std::vectorint>> adjList(V);
// Add edges
adjList[0].push_back(1);
adjList[1].push_back(2);
adjList[2].push_back(3);
adjList[3].push_back(0);
// Perform BFS
std::cout << "BFS traversal starting from vertex 0: ";
BFS(0, adjList);
std::cout << std::endl;
return 0;
}
3. Dijkstra’s Algorithm
Dijkstra’s algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative weights.
Example:
cpp#include int , int>>>& adjList) {
int V = adjList.size();
std::vector<int> dist(V, INT_MAX);
dist[source] = 0;
using pii = std::pair<int, int>; // Pair of (distance, vertex)
std::priority_queue, std::greater> pq;
pq.push({0, source});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& edge : adjList[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
// Print distances
for (int i = 0; i < V; ++i) {
std::cout << "Distance from " << source << " to " << i << " is " << dist[i] << std::endl;
}
}
int main() {
const int V = 5; // Number of vertices
std::vectorint, int>>> adjList(V);
// Add edges (vertex, weight)
adjList[0].emplace_back(1, 10);
adjList[0].emplace_back(4, 3);
adjList[1].emplace_back(2, 2);
adjList[1].emplace_back(4, 4);
adjList[2].emplace_back(3, 9);
adjList[3].emplace_back(2, 7);
adjList[4].emplace_back(1, 1);
adjList[4].emplace_back(2, 8);
adjList[4].emplace_back(3, 2);
// Perform Dijkstra's algorithm
std::cout << "Dijkstra's Algorithm starting from vertex 0:" << std::endl;
Dijkstra(0, adjList);
return 0;
}
Key Points
- Representation: Use adjacency matrices for dense graphs and adjacency lists for sparse graphs.
- Algorithms: Different algorithms solve various graph-related problems (e.g., shortest paths, connectivity).
- Complexity: Understand the time and space complexities of different representations and algorithms to choose the most appropriate one for your needs.
Graphs are a versatile data structure used in a wide range of applications, from network routing to social networks. Understanding their representations and algorithms will help you effectively solve problems involving complex relationships between entities.