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

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

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 a[n] is an array of n linked lists, where linked list a[i] represent the vertices connecting the vertex i. For instance,
a (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,

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

//
//  main.cpp
//
//  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

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}};

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

//
//  main.cpp
//
//  Created by Himanshu on 26/11/22.
//

#include <iostream>
#include <vector>
using namespace std;
#define N 5

//N = number of nodes in graph

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.push_back(2);
graph.push_back(1);
graph.push_back(4);
graph.push_back(4);
graph.push_back(5);
graph.push_back(2);
graph.push_back(3);
graph.push_back(5);
graph.push_back(3);
graph.push_back(4);

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