Graphs are a fundamental data structure used to represent a collection of nodes (or vertices) and edges connecting them. They are widely used to solve problems related to networks, paths, and connections.
Graphs can be represented in multiple ways:
An adjacency matrix is a 2D array where the element at row i and column j is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.
#include
#include
class Graph {
public:
int V; // Number of vertices
std::vector> adjMatrix;
Graph(int V) {
this->V = V;
adjMatrix = std::vector>(V, std::vector(V, 0));
}
void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // For undirected graph
}
void printGraph() {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
std::cout << adjMatrix[i][j] << " ";
}
std::cout << std::endl;
}
}
};
int main() {
Graph g(5);
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();
return 0;
}
An adjacency list is an array of lists. The index of the array represents a vertex, and each element in the list represents the vertices adjacent to the vertex at that index.
#include
#include
#include
class Graph {
public:
int V;
std::vector> adjList;
Graph(int V) {
this->V = V;
adjList = std::vector>(V);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // For undirected graph
}
void printGraph() {
for (int i = 0; i < V; ++i) {
std::cout << "Vertex " << i << ":";
for (int v : adjList[i]) {
std::cout << " -> " << v;
}
std::cout << std::endl;
}
}
};
int main() {
Graph g(5);
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();
return 0;
}
Two primary graph traversal algorithms are:
DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.
#include
#include
class Graph {
public:
int V;
std::vector> adjList;
Graph(int V) {
this->V = V;
adjList = std::vector>(V);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // For undirected graph
}
void DFSUtil(int v, std::vector& visited) {
visited[v] = true;
std::cout << v << " ";
for (int i : adjList[v]) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
}
void DFS(int v) {
std::vector visited(V, false);
DFSUtil(v, visited);
}
};
int main() {
Graph g(5);
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);
std::cout << "Depth First Traversal starting from vertex 0:\n";
g.DFS(0);
return 0;
}
BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root node and explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.
#include
#include
#include
#include
class Graph {
public:
int V;
std::vector> adjList;
Graph(int V) {
this->V = V;
adjList = std::vector>(V);
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // For undirected graph
}
void BFS(int s) {
std::vector visited(V, false);
std::queue queue;
visited[s] = true;
queue.push(s);
while (!queue.empty()) {
s = queue.front();
std::cout << s << " ";
queue.pop();
for (auto adj : adjList[s]) {
if (!visited[adj]) {
visited[adj] = true;
queue.push(adj);
}
}
}
}
};
int main() {
Graph g(5);
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);
std::cout << "Breadth First Traversal starting from vertex 0:\n";
g.BFS(0);
return 0;
}
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights
#include
#include
#include
#include
class Graph {
public:
int V;
std::vector>> adjList;
Graph(int V) {
this->V = V;
adjList = std::vector>>(V);
}
void addEdge(int u, int v, int weight) {
adjList[u].push_back({v, weight});
adjList[v].push_back({u, weight}); // For undirected graph
}
void dijkstra(int src) {
std::vector dist(V, std::numeric_limits::max());
std::set> setds;
dist[src] = 0;
setds.insert({0, src});
while (!setds.empty()) {
int u = setds.begin()->second;
setds.erase(setds.begin());
for (auto i = adjList[u].begin(); i != adjList[u].end(); ++i) {
int v = (*i).first;
int weight = (*i).second;
if (dist[v] > dist[u] + weight) {
if (dist[v] != std::numeric_limits::max()) {
setds.erase(setds.find({dist[v], v}));
}
dist[v] = dist[u] + weight;
setds.insert({dist[v], v});
}
}
}
std::cout << "Vertex Distance from Source\n";
for (int i = 0; i < V; ++i) {
std::cout << i << "\t\t" << dist[i] << std::endl;
}
}
};
int main() {
Graph g(9);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.dijkstra(0);
return 0;
}