A dynamic array is an array that can grow, resize itself, contains a dynamic table, which is mutable in nature, or an array list is randomly accessible, the variable-size list data structure that allows elements to be added or removed.
Suppose we want to create a class for Graph. The class stores the adjacency matrix representation of the graph.
Example:
// C++ program to demonstrate class of graphs
class Graph
{
int V;
int adj[V][V]; // This line doesn't work
/* Rest of the members */
};
int main()
{
}
Output :
error: invalid use of non-static data member 'Graph::V'.
Even if we make V static, we get the error “array bound is not an integer constant”.
C++ doesn’t allow to creation of a stack-allocated array in a class whose size is not constant. So we need to dynamically allocate memory. Below is a simple program to show how to dynamically allocate a 2D array in a C++ class using a class for Graph with adjacency matrix representation.
// C++ program to demonstrate
// how to allocate dynamic 2D
// array in a class using a Graph
#include <bits/stdc++.h>
using namespace std;
// A Class to represent directed graph
class Graph {
int V; // No. of vertices
// adj[u][v] would be true if there is an edge
// from u to v, else false
bool** adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v) { adj[u][v] = true; }
void print();
};
Graph::Graph(int V)
{
this->V = V;
// Create a dynamic array of pointers
adj = new bool*[V];
// Create a row for every pointer
for (int i = 0; i < V; i++) {
// Note : Rows may not be contiguous
adj[i] = new bool[V];
// Initialize all entries as false to indicate
// that there are no edges initially
memset(adj[i], false, V * sizeof(bool));
}
}
// Utility method to print adjacency matrix
void Graph::print()
{
for (int u = 0; u < V; u++) {
for (int v = 0; v < V; v++)
cout << adj[u][v] << " ";
cout << endl;
}
}
// Driver method
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.print();
return 0;
}
Output :
0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1
Note: memset() is used separately for individual rows. We can’t replace these calls with one call because rows are allocated at different addresses and making a memset call would be disastrous.
Example:
// Wrong!! (Rows of matrix at different addresses) memset(adj, false, V*V*sizeof(bool));
Australia
UK
UAE
Singapore
Canada
New
Zealand
Malaysia
USA
India
South
Africa
Ireland
Saudi
Arab
Qatar
Kuwait
Hongkong
Copyright 2016-2023 www.programmingshark.com - All Rights Reserved.
Disclaimer : Any type of help and guidance service given by us is just for reference purpose. We never ask any of our clients to submit our solution guide as it is, anywhere.