Graphs are essential data structures used to model relationships between entities. In this article you will learn to write a C++ program to Implement a Graph Using Adjacency Matrix. Graphs are widely used in various applications, including computer networks, social networks, transportation systems, and more.

## Prerequisites

Before we dive into the examples, it’s important to understand the following concepts:

**Graph**: A collection of nodes (vertices) and edges connecting some or all of them.**Adjacency Matrix**: A 2D array where each element at row`i`

and column`j`

represents the presence (and sometimes the weight) of an edge between vertex`i`

and vertex`j`

.**Directed and Undirected Graphs**: In a directed graph, edges have a direction, while in an undirected graph, edges do not.

Familiarity with C++ programming, including standard libraries like `<iostream>`

and basic array operations, will be beneficial.

## Implementing a Graph Using Adjacency Matrix

To represent a graph using an adjacency matrix in C++, we typically use a 2D array (or a vector of vectors). Each element in the matrix indicates whether an edge exists between two vertices and can also store the weight of the edge.

### Pseudocode for Graph Representation

- Define a class for the graph.
- Initialize a 2D array (or vector of vectors).
- Implement methods to add edges and display the graph.

## Examples

### Example 1: Simple Undirected Graph

#### Graph Representation

Consider a simple undirected graph with four vertices:

```
(A)---(B)
| |
(C)---(D)
```

#### C++ Program

```
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V; // Number of vertices
vector<vector<int>> adjMatrix;
public:
Graph(int V);
void addEdge(int v, int w);
void printGraph();
};
Graph::Graph(int V) {
this->V = V;
adjMatrix.resize(V, vector<int>(V, 0));
}
void Graph::addEdge(int v, int w) {
adjMatrix[v][w] = 1;
adjMatrix[w][v] = 1; // For undirected graph
}
void Graph::printGraph() {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.printGraph();
return 0;
}
```

#### Output

```
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
```

### Example 2: Directed Graph

#### Graph Representation

Consider a directed graph with four vertices:

```
(A)---->(B)
^ /|
| / |
(C)<--/ |
\ v
->(D)
```

#### C++ Program

```
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjMatrix;
public:
Graph(int V);
void addEdge(int v, int w);
void printGraph();
};
Graph::Graph(int V) {
this->V = V;
adjMatrix.resize(V, vector<int>(V, 0));
}
void Graph::addEdge(int v, int w) {
adjMatrix[v][w] = 1;
}
void Graph::printGraph() {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(1, 3);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(3, 2);
g.printGraph();
return 0;
}
```

#### Output

```
0 1 0 0
0 0 1 1
1 0 0 0
0 0 1 0
```

### Example 3: Graph with Weighted Edges

#### Graph Representation

Consider a graph with weighted edges:

```
(A)--2--(B)
| /|
4| 3 |
| / |
(C)--5--(D)
```

#### C++ Program

```
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjMatrix;
public:
Graph(int V);
void addEdge(int v, int w, int weight);
void printGraph();
};
Graph::Graph(int V) {
this->V = V;
adjMatrix.resize(V, vector<int>(V, 0));
}
void Graph::addEdge(int v, int w, int weight) {
adjMatrix[v][w] = weight;
adjMatrix[w][v] = weight;
}
void Graph::printGraph() {
for (int i = 0; i < V; ++i) {
for (int j = 0; j < V; ++j) {
cout << adjMatrix[i][j] << " ";
}
cout << endl;
}
}
int main() {
Graph g(4);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 4);
g.addEdge(1, 3, 3);
g.addEdge(2, 3, 5);
g.printGraph();
return 0;
}
```

#### Output

```
0 2 4 0
2 0 0 3
4 0 0 5
0 3 5 0
```

## Conclusion

Implementing a graph using an adjacency matrix in C++ is a straightforward and efficient way to represent and manipulate graphs, especially when the graph is dense