In this guide, we will explore a C++ code to build graphs under specific constraints.
Fundamental data structures known as graphs are utilized to illustrate the connections between different elements. Creating graphs that meet specific conditions or criteria is essential in various scenarios. These criteria could involve factors such as edge weights, structural limitations, or connectivity prerequisites. The objective of this C++ code is to generate a graph that meets the defined criteria. The requirements may be linked to aspects like the number of vertices, specific edges presence, or characteristics such as acyclicity or connectivity. Depending on the constraints and specifications, the program might utilize techniques like adjacency matrices and adjacency lists for graph representation.
Suppose we have two numbers, N and K . Consider the case of an undirected graph with N elements. N vertices satisfy the following conditions. It has the following conditions:
- The graph is simple and linked.
- The vertices have numbers ranging from 1 to N.
- Let M be the number of edges in the graph. For the edges, a number goes from 1 to M, which is the length of the Edge. Additionally, Edge i connects Vertex V[i] and Vertex U[i] .
- There are pairs where i < j and their shortest distance is 2 for each K pairs of vertices (i, j).
Example 1:
Let's consider an illustration to demonstrate the process of building a graph with specific constraints using C++.
#include <bits/stdc++.h>
using namespace std;
void generateGraph(int numVertices, int numEdges){
if (numEdges > (numVertices - 1) * (numVertices - 2) / 2){
cout << "Cannot generate graph with " << numEdges << " edges for " << numVertices << " vertices." << endl;
return;
}
cout << "Number of edges: " << (numVertices - 1) * (numVertices - 2) / 2 - numEdges + numVertices - 1 << '\n';
for (int i = 1; i < numVertices; i++){
cout << "Edge: 1 -> " << i + 1 << '\n';
}
int count = (numVertices - 1) * (numVertices - 2) / 2 - numEdges;
for (int i = 2; i <= numVertices; i++){
for (int j = i + 1; j <= numVertices; j++){
if (count <= 0){
return;
}
cout << "Edge: " << i << " -> " << j << '\n';
count--;
}
}
}
int main(){
int numVertices = 7;
int numEdges = 10;
generateGraph(numVertices, numEdges);
return 0;
}
Output:
Number of edges: 11
Edge: 1 -> 2
Edge: 1 -> 3
Edge: 1 -> 4
Edge: 1 -> 5
Edge: 1 -> 6
Edge: 1 -> 7
Edge: 2 -> 3
Edge: 2 -> 4
Edge: 2 -> 5
Edge: 2 -> 6
Edge: 2 -> 7
Example 2:
Let's consider another instance to demonstrate the process of building a graph with specific constraints in C++.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) {
V = vertices;
adj.resize(V);
}
void addEdge(int src, int dest) {
adj[src].push_back(dest);
adj[dest].push_back(src); // for undirected graph
}
bool isConnected() {
vector<bool> visited(V, false);
queue<int> q;
q.push(0);
visited[0] = true;
while (!q.empty()) {
int current = q.front();
q.pop();
for (int i = 0; i < adj[current].size(); ++i) {
int adjacentVertex = adj[current][i];
if (!visited[adjacentVertex]) {
visited[adjacentVertex] = true;
q.push(adjacentVertex);
}
}
}
for (int i = 0; i < V; ++i) {
if (!visited[i])
return false; // Graph is not connected
}
return true; // Graph is connected
}
void printGraph() {
cout << "Generated Graph:" << endl;
for (int i = 0; i < V; ++i) {
cout << "Vertex " << i << " -> ";
for (int j = 0; j < adj[i].size(); ++j)
cout << adj[i][j] << " ";
cout << endl;
}
}
};
int main() {
int V, E;
cout << "Enter number of vertices: ";
cin >> V;
cout << "Enter number of edges: ";
cin >> E;
Graph g(V);
// Constructing a connected graph
for (int i = 0; i < E; ++i) {
int src, dest;
cout << "Enter edge " << i+1 << " (source destination): ";
cin >> src >> dest;
g.addEdge(src, dest);
}
if (g.isConnected()) {
cout << "Graph is connected." << endl;
g.printGraph();
} else {
cout << "Cannot construct a connected graph with the given inputs." << endl;
}
return 0;
}
Output:
Enter number of vertices: 4
Enter number of edges: 3
Enter edge 1 (source destination): 0 1
Enter edge 2 (source destination): 1 2
Enter edge 3 (source destination): 2 3
Graph is connected.
Generated Graph:
Vertex 0 -> 1
Vertex 1 -> 0 2
Vertex 2 -> 1 3
Vertex 3 -> 2
