A graph consists of two sets, namely **V** (vertices) and **E** (Edges). **V** represents a non-empty sets of vertices present in the graph. While **E**, represents the set of edges (joining two vertices) in the graph.

###### Implementation

The two most common ways to represent a graph are:

- Adjacency Matrix
- Adjacency List

Consider the following graph and its representation in Adjacency Matrix and Adjacency List:

###### Adjacency Matrix

Adjacency Matrix ** a[n][n]** is an

**nxn matrix**, where

**, if there’s an edge between vertices i and j. Also**

`a[i][j] = 1`

**, if there is no edge between vertices (i & j).**

`a[i][j] = 0`

###### Adjacency List

Adjacency List **a[n]** is an array of **n linked lists**, where linked list **a[i]** represent the vertices connecting the vertex i. For instance,

a[0] (Vertex 1) is connected to the node 2, since there’s an edge between vertex 1 and vertex 2. **Note:** We could also use an array of C++ Vector class instead of a linked list.

###### Directed Graph

In a Directed graph, each edge ie. pair **<V1, V2>** represent that there’s an edge from V1 to V2 where V1 is the tail and V2 is the head. For instance,

**Corresponding Adjacency Matrix & Adjacency List**

###### Undirected Graph

In an Undirected graph, each edge ie. pair **<V1, V2>** represent that there’s an edge between vertices V1 & V2. This implies that both **pair <V1, V2> **and **pair <V2, V1>** are same and both represent that there’s an edge between V1 & V2.

Undirected graph’s representation is shown in Fig.1 and Fig. 2.

###### Adjacency Matrix Implementation

```
//
// main.cpp
// Adjacency Matrix
//
// Created by Himanshu on 26/11/22.
//
#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#define N 5
using namespace std;
//N = number of nodes in graph
void printAdjacencyMatrix(int G[][N]) {
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cout<<G[i][j]<<" ";
}
cout<<endl;
}
}
int main() {
int G[N][N] = {{0, 1, 0, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}};
cout<<"Graph G (Adjacency Matrix):"<<endl;
printAdjacencyMatrix(G);
return 0;
}
```

**Output**

Graph G (Adjacency Matrix): 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0

Here’s a working example: Adjacency Matrix

###### Adjacency List Implementation

```
//
// main.cpp
// Adjacency List
//
// Created by Himanshu on 26/11/22.
//
#include <iostream>
#include <vector>
using namespace std;
#define N 5
//N = number of nodes in graph
void printAdjacencyList (vector<int> graph[N+1]) {
for (int i=1; i<=N; i++) {
cout<<i<<": ";
for (int j=0; j<graph[i].size(); j++) {
cout<<graph[i][j]<<" ";
}
cout<<endl;
}
}
int main() {
vector<int> graph[N+1];
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(4);
graph[3].push_back(4);
graph[3].push_back(5);
graph[4].push_back(2);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(3);
graph[5].push_back(4);
cout<<"Graph G (Adjacency List):"<<endl;
printAdjacencyList(graph);
return 0;
}
```

**Output**

Graph G (Adjacency List): 1: 2 2: 1 4 3: 4 5 4: 2 3 5 5: 3 4

Here’s a working example: Adjacency List