# Directed and Undirected Graphs (Implementation)

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 a[i][j] = 1, if there’s an edge between vertices i and j. Also a[i][j] = 0, if there is no edge between vertices (i & j).

###### 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